논리합(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번은 논리적 동치에 해당할 수 있음.
