[이산수학] 4강 - 집합론

✅ 1. 기본사항

(0) 학습 목표

(1) 논리학과 집합론

• 논리합(OR): 합집합으로 표현이 가능하며, 둘 중 하나만 참, 둘 다 참인 경우 다 참으로 모두 포괄하는 합집합의 형태임.
• 논리곱(AND): 교집합으로 표현이 가능하며, 둘 다 참인 경우에만 참으로 한정적으로 포괄하는 교집합의 형태임.
• 이와 같이 논리학과 집합론의 관계를 알 수 있음.

(2) 집합과 원소

• 집합 자체의 용어는 무정의 용어이며, 무정의 용어는 정의 없이 사용하는 용어를 의미함.

(3) 집합의 표기법

• S가 하나의 집합일 때 a ∈ S: a는 집합 S의 원소임을 나타냄.
• S가 하나의 집합일 때 b ∉ S: b는 집합 S의 원소가 아님을 나타냄.
• 집합 S: 중괄호 { , } 로 표기를 함.
• 원소나열법: S = {1, 2, 3} 형식으로 나열을 표기함.
• 조건나열법: 조건을 줌으로써, 숫자를 나열하지 않고 표기를 하는 느낌임. ( S = { 0 < x < 4 } 는 결국 S = {1, 2, 3}과 동일 )
• 집합의 크기: |S| 와 같은 절대표기로 집합의 크기를 표현함.

• (1) 집합이 맞음.
• (2) 집합이 아님.
• (3) 집합안에 집합이 있는 구조로 집합이 맞음.
• (4) 동일한 원소는 두 번 사용하지 않기 때문에 집합이 아님.

• 위와 같이 빈 동그라미는 포함이 아니며, 찬 동그라미는 포함으로써 조건제시법으로 표현이 가능함.
• 결과적으로 -3 < x <= 4 인 실수들 모두 집합의 원소로 들어가 있다는 의미로 볼 수 있음.

(4) 부분집합

• 부분집합: A의 모든 원소가 B의 원소이면 A는 B의 부분집합이라함. ( A ⊆ B 또는 A ⊂ B 로 표기함. )
• 모든 x에 대해서 x 가 A의 원소면, x는 B의 원소이다.
• 집합 B = {1,2,3} 일 때, 가능한 부분 집합들 {1}, {1,2}, {2,3}, {1,2,3} 과 같이 여러 부분집합이 나올 수 있음.
• 즉, A가 B의 부분집합이라면, A의 원소 모든게 항상 B에 들어가 있어야 함.

• 진부분집합: 자기 자신을 가지는 전체 부분집합을 제외한 모든 경우의 수를 진부분집합이라함.
• 집합 B = {1,2,3} 일 때, 가능한 부분 집합들 {1}, {1,2}, {2,3}, {1,2,3} 에서 {1,2,3} 자기자신을 제외한 나머지 {1}, {1,2}, {2,3}을 진부분집합 이라고 함. ( 참고로, ∅ 공집합도 진부분집합 포함임 )

• 상동: A가 B의 부분집합이면서, B가 A의 부분집합이 되려면 결국 둘 다 똑같은 집합을 가져야하며, 이것을 상동이라함.
• 즉, 상동은 집합 A = {1,2,3} 일 때, 집합 B도 집합B = {1,2,3} 이렇게 동일한 집합을 가진 상태를 의미한다. ( A = B )

• (1) 부분집합을 의미하는 기호이지, 원소 기호가 아니기 때문에 X
• (2) ∅(공집합)은 모든 집합의 부분집합으로 O
• (3) 집합의 일부를 가지며, 완전 동일하지 않기 때문에 진부분집합으로 볼 수 있기 때문에 O
• (4) 원소를 가지기 때문에 O

(5) 서로소

• 교집합: A에도 속하고, 동시에 B에도 속하는 원소들만 골라낸 집합을 의미한다.
• 철수(A)의 가방: {연필, 지우개, 공책} , 영희(B)의 가방: {공책, 필통, 가위} = A ∩ B = {공책}
• 즉, 공집합은 항상 부분집합으로 존재하기 때문에 집합 A, B의 공집합은 교집합이 될 수 있음. ( A ∩ B = ∅ 성립됨 )
• 서로소: 집합 A, B 에서 공통된 원소가 하나도 없는 상태를 의미하며, 이것은 교집합이 공집합(∅)만을 가지는 경우임.
• 쌍으로 서로소: 여러 개의 대상(숫자나 집합)이 있을 때, 그 중 어떤 두 개를 딱 집어서 비교해도 무조건 서로소인 상태를 의미하며, 반드시 모든 집합의 원소들이 절대적으로 겹치지 않아야 하는 규칙이 있음.
• 반면, 서로소는 모든 집합간의 원소가 동시에 겹치지만 않아도된다는 느슨한 규칙의 차이임. 쉽게 말해, 집합 3개가 있다고 가정하고 집합 1, 2가 서로 원소가 겹치는게 있더라도 3이 겹치지 않으면 서로소가 맞음.

• (1) 집합 A1, A2 는 겹치는 원소가 없기 때문에 교집합이 공집합인 상태로 서로소가 맞음. (O)
• (2) A2와 A3는 서로소가 맞음 (O)
• (3) A1, A2, A3에서 b 부분이 집합 A1, A3는 b원소가 교집합으로 겹치기 때문에 쌍으로 서로소가 아님 (X)

(6) 분할

• 분할: 집합 하나의 여러 원소들을 나눠서 여러 집합으로 만드는 것을 분할이라고 함. ( A집합을 나누면 A의 분할이라함 )
• 분할 조건1: 쪼개진 조각은 최소한 원소 하나는 갖고있어야함. 즉, 공집합이 아니어야 함.
• 분할 조건2: 쌍으로 서로소여야 함. 즉, 조각끼리 겹치는 특성이 교집합이 없어야 함.
• 분할 조건3: 조각들을 다 합집합하면 원래의 집합 S가 되어야함.

• (1) 1번의 공집합은 포함이 되면 안되고, 2번과 3번은 합집합 했을 때, 원래의 집합 S가 되지 않으므로 잘못 된 것임.
• (2) 집합을 분할할 때 통으로 {1, 2, 3} => {{1,2,3}} 으로 분할을 해도 이것도 분할로 봄. (trivial parition)

• 집합 {1,2,3}의 모든 분할을 위와같음.

• 모든 정수의 집합을 Z라고 봄. 즉, 1,2,3,4,5,6,7... 정수의 집합
• Z0는 짝수들의 집합을 의미하고 있음.
• Z1는 홀수들의 집합을 의미하고 있음. 
• Z0 ∪ Z1 = Z 는 Z0과 Z1이 합집합이 되면, 모든 짝수와 모든 홀수 원소의 합집합은 결국 Z(모든 정수의 집합)가 됨.
• Z0 ∩ Z1 = ∅ 은 Z0과 Z1 집합은 서로 겹치는 원소가 없기 때문에 교집합임을 나타냄.
• 즉, 결과적으로 Z0, Z1 은 Z의 분할임을 알 수 있음.

(7) 멱집합

• 멱집합: 집합 A의 모든 부분집합들을 모아서 집합으로 만든것을 멱집합이라고 함.
• 예를들면, A = {1, 2} 인 경우 P(A) = { ∅, {1}, {2}, {1,2} } 이와 같은 멱집합이 만들어 질 수 있음.

• 멱집합은 위와같이 필연적으로 집합 안에 집합이 들어있는 구조로 만들어짐.
• 멱집합의 원소 수는 집합 S의 원소 수가 n이라면, 항상 2^n 개가 됨.

---

✅ 2. 집합연산

(1) 합집합

• 논리합(or, V) 과 합집합의 관계를 나타냄.

(2) 교집합

• 논리곱(and) 과 교집합의 관계를 나타냄.

(3) 차집합

• 차집합: A에는 있지만 B에는 없는 원소들의 집합을 의미한다.
• A = {1,2,3} B = {2,3,4} 두 집합에서 차집합은 A - B = {1} 이 될 수 있음.

(4) 여집합

• 여집합: 전체 집합 기준으로 A 집합의 원소를 뺀 것을 의미한다. ( ~부정과 동일함 )
• 전체집합 U = {1,2,3,4,5} 에서 A 집합이 A = {1,2,3} 이라면, A의 여집합은 Ac = {4,5} 가 될 수 있음.

(5) 대칭차집합

• 대칭차집합: 두 집합에서 겹치는 원소를 아예 뺀 집합을 대칭차집합이라고 함. ( XOR 베타적 논리합과 동일함 )
• A = {1,2,3} B = {3,4,5} 두 집합이 존재할 때, 겹치는 원소 3을 빼게 된다면, A - B = {1,2} B - A = {4,5} 가 될 수 있음.
• 이제 해당 집합을 합치게 되면, {1,2,4,5} 대칭차집합을 얻을 수 있음.

(6) 곱집합

• 곱집합: 두 집합의 모든 순서쌍의 집합을 곱집합 이라고 함.
• A = {1,2} B = {a,b} 두 집합의 곱집합은 A * B = { (1,a),(1,b),(2,a),(2,b) } 가 될 수 있음.

• (1) 합집합: A ∪ B = {1,2,3,4} => 모든 원소의 집합(or 연산)
• (2) 교집합: A ∩ B = {2,3} => 겹치는 원소의 집합(and 연산)
• (3) 차집합: A - B = 1 => A는 가지지만 B는 가지지 못하는 원소의 집합
• (4) 여집합: Ac = {4,5} => 전체 집합에서 A가 가지지 못한 원소의 집합을 나타냄.

• (5) 대칭차집합: A xor B = {1,4} => 두 집합에서 겹치는 수 1,3 을 뺀 나머지 집합은 {1,4}가 됨.

---

✅ 3. 집합의 대수법칙

(1) 집합 크기의 관한 성질

• 합집합의 크기: 집합 A, B를 합집합 할 때, 겹치는 교집합의 원소가 있을 경우 A와 B의 집합을 더한 뒤, A와 B의 교집합을 빼게 되면 합집합의 원소 개수를 알 수 있으며, 이것이 합집합의 크기임.
• 쉽게 말해, 집합 A(10), 집합B(5) 원소를 가지는 집합이 있을 때, A와 B 교집합 원소의 개수는(2)개라고 보면 겹치는 것을 제외한 합집합을 하게 된다면 10 + 5 - 2 = 13개의 합집합의 크기를 얻을 수 있음.

• 따름정리(합집합의 크기): 위의 합집합의 크기 공식이 결국 이미 증명된 정리이기 때문에 따름정리(이미 증명된 정리로부터 아주 쉽고 자연스럽게 유도되는 또 다른 정리)를 통해서 대수법칙을 얻을 수 있음.

• 서로소인 집합의 합집합의 크기: A와 B가 서로소인 경우 교집합이 공집합인 경우이기 때문에 즉, 겹치는게 없기 때문에 단순히 A + B 를 통해서 두 집합의 원소를 더해만 준다면 합집합의 크기를 얻을 수 있음. ( 기출 문제 인듯 )

(2) 포함관계 및 항등식

• 교집합에서의 포함관계: 집합 A, B의 교집합은 겹치는 원소의 집합이므로, 집합 A의 부분집합이 될 수 있음.
• 합집합에서의 포함관계: 집합 A, B의 합집합은 두 집합의 모든 원소를 포괄하는 집합이기 때문에, B는 집합 A, B 합집합의 부분집합이 될 수 있음. 부분집합의 기호 앞이 항상 부분집합이 되고, 뒤가 전체집합이됨.
• 이행성: 관계의 연결을 의미하며, 예를들면, A가 B에 포함되고, B가 C에 포함된다면 A는 C에도 포함이 된다는 논리임.

• 원소 논증: 부분집합 X는 전체집합 Y에 항상 포함이 되어있어야 성립이 되는데, 이것을 증명하고자 할 때 사용하는 방법이며, 집합 전체를 한꺼번에 증명하기 어려울 때 집합 안에 있는 임의의 원소(x)를 하나 뽑아서, 그 원소가 논리적으로 어디에 속하는지 추적하는 방식으로 보면 됨.

• 집합의 항등식(교환법칙): 합집합과 교집합의 교환법칙은 성립됨. ( A, B의 위치를 바꿔도 상관없다는 의미임. )
• 집합의 항등식(결합법칙): 결합법칙 또한 성립이 됨. ( 논리학과의 연결성이 있음. )

• 포함관계에 대한 동치: U가 전체집합이고, A ⊆ B ⊆ C 집합 상태로, A가 B에 완전 포함되고, B는 U에 완전 포함된 형태의 전체집합의 아래 1~7번은 논리적 동치에 해당할 수 있음.
• (1) A는 B의 부분집합이기 때문에 동치임.
• 정리: 논리학과 집합론의 관계에 대해서 연결성을 넣을 수 있음을 알 수 있음.
• 기출문제일듯.