집합
- 명확한 기준에 의해 분류되어 공통된 성질을 가지며 중복되지 않는 원소의 모임
- 원소나열법: 집합에 포함되는 원소들을 일일이 나열하는 방법
- 조건제시법: 집합에 포함되는 원소들의 공통적인 성질을 조건식으로 제시하는 방법
- 벤다이어그램: 집합과 원소의 포함관계를 그림으로 보여주는 방법
- 기수(Cardinality): 집합에 포함되는 원소의 개수 (e.g. 집합 A의 기수 = | A |)
- 전체집합: 논의 대상이 되는 원소 전체를 포함하는 집합
- 공집합: 원소를 하나도 포함하지 않는 집합으로 기수가 0인 집합
- 상등: 두 집합에 속하는 원소가 모두 동일한 경우
- 부분집합: 집합 A의 원소가 집합 B에 포함되는 경우, |A| ≤ |B|
- 진부분집합: 집합 A의 원소가 집합 B에 포함되지만 집합 A와 B가 상등이 아닌 경우
집합 간의 포함 관계
- 모든 집합 A에 대해 A⊆A
- 집합 A에 속하는 모든 원소 a에 대해 a∈A가 성립함
- 따라서 A⊆A 성립함
- ∴ 모든 집합은 자기 자신의 부분집합이 됨
- 모든 집합 A에 대해 ∅⊆A
- ∅⊆A를 증명하기 위해, 어떤 원소 a에 대해 a∈∅ → a∈A를 증명
- 공집합에는 원소가 존재할 수 없기 때문에 a∈∅는 거짓
- 조건이 거짓인 함축명제는 항상 참이므로 a∈∅ → a∈A는 참
- 따라서 ∅⊆A는 참
- ∴ 공집합은 모든 집합의 부분집합
- 모든 집합 A에 대해 A⊆U
- A⊆U를 증명하기 위해, 어떤 원소 a에 대해 a∈A → a∈U를 증명
- 전체집합 U는 논의영역의 모든 원소를 포함
- 따라서 a∈A이면 a∈U가 성립
- ∴ 모든 집합은 전체집합 U의 부분집합
- 집합 A, B, C에 대해 A⊆B이고, B⊆C이면 A⊆C
- 어떤 원소 a에 대해 a∈A이면, A⊆B에 의해 a∈B
- a∈B이면, B⊆C에 의해 a∈C
- 결국 a∈A이면 a∈C
- 따라서 A⊆C는 참
- 집합 A, B에 대해 A=B ↔ (A⊆B ∧ B⊆A)
- 어떤 원소 a에 대해 A⊆B인 것은 a∈A이면 a∈B
- 또한 B⊆A인 것은 a∈B면 a∈A
- 어떤 원소 a는 집합 A의 원소면서 집합 B의 원소
- 따라서 A=B ↔ (A⊆B ∧ B⊆A)는 참
- ∴ 집합 A와 B가 상등이면 집합 A와 집합 B는 서로의 부분집합
집합의 연산
- 합집합(Union): 집합 A, B가 있을 때 집합 A와 B에 모두 속하거나, 둘 중 한 집합에 속하는 원소들로 만들어진 집합
- 교집합(Intersection): 집합 A, B가 있을 떄 집합 A와 B에 모두 속하는 원소들의 집합
- 서로소(Disjoint): 집합 A, B가 있을 떄 집합 A와 B 사이에 공통으로 속하는 원소가 하나도 없는 경우
- 차집합(Difference): 집합 A, B가 있을 떄 집합 A에는 속하지만 집합 B에는 속하지 않는 원소로 구성되는 집합
- 대칭차집합(Symmetric Difference): 집합 A, B가 있을 때 A-B에 속하거나 B-A에 속하는 원소로 구성되는 집합
- 여집합(Complement): 전체집합 U에는 속하지만 집합 A에는 속하지 않는 원소들로 구성된 집합
- 곱집합(Cartesian Product): 집합 A, B에 대하여 a∈A, b∈B일 때, 순서쌍 (a, b)의 집합
- 멱집합(Power Set): 하나의 집합에서 발생할 수 있는 모든 부분집합을 집합으로 구한 것
- 공집합은 모든 집합의 부분집합이고, 집합 자기 자신도 부분집합
- n개의 원소를 갖는 집합 A의 멱집합 P(A)에 대해 | P(A) | = 2ⁿ
집합의 대수법칙
| 집합 | 대수법칙 |
| A∪∅ = A, A∩U = A | 항등법칙 |
| A∪U = U, A∩∅ = ∅ | 지배법칙 |
| A∪A = A, A∩A = A | 멱등법칙 |
| A∪B = B∪A, A∩B = B∩A | 교환법칙 |
| A∪(B∪C) = (A∪B)∪C A∩(B∩C) = (A∩B)∩C |
결합법칙 |
| A∪(B∩C) = (A∪B)∩(A∪C) A∩(B∪C) = (A∩B)∪(A∩C) A×(B∩C) = (A×B)∩(A×C) A×(B∪C) = (A×B)∪(A×C) |
분배법칙 |
| A'' = A | 이중 보법칙 |
| A∪A' = U, A∩A' = ∅, ∅' = U, U' = ∅ | 보법칙 |
| (A∪B)' = A'∩B', (A∩B)' = A'∪B' | 드모르간의 법칙 |
| A∪(A∩B) = A, A∩(A∪B) = A | 흡수법칙 |
드모르간의 법칙 증명
- x∈(A∪B)' ↔ x∈(A'∩B')
- ↔ ∉(A∪B)
- ↔ x∉A ∧ x∉B
- ↔ x∈A' ∧ x∈B'
- ↔ x∈(A'∩B')
흡수법칙 증명
- A∩(A∪B) = (A∪∅)∩(A∪B) 항등법칙
- = A∪(∅∩B) 분배법칙
- = A∪∅ 지배법칙
- = A 항등법칙
- ∴ A∩(A∪B) = A
분배법칙 증명
- A×(B∩C) = (A×B)∩(A×C)임을 보이기 위해 (x, y)∈A×(B∩C) ↔ (x, y)∈(A×B)∩(A×C)를 증명
- (x, y)∈A×(B∩C) ↔ x∈A ∧ y∈(B∩C) 곱집합의 정의
- ↔ x∈A ∧ (y∈B ∧ y∈C) 교집합의 정의
- ↔ (x∈A ∧ y∈B) ∧ (x∈A ∧ y∈C) 논리연산의 분배법칙
- ↔ [(x, y)∈A×B] ∧ [(x, y)∈A×C] 곱집합의 정의
- ↔ (x, y)∈(A×B)∩(A×C)
- ∴ A×(B∩C) = (A×B)∩(A×C)이 성립
집합의 분할
- 공집합이 아닌 임의의 집합 A를 서로소이면서 공집합이 아닌 하나 이상의 부분집합(A₁, A₂, ... , Aₙ)으로 나누는 것으로 집합 A가 있을 때 다음과 같은 성질을 만족해야 함 (i = 1, 2, ... , n)
- ① Aᵢ ⊆ A
- ② Aᵢ = ∅
- ③ A = A₁ ∪ A₂ ∪ ... ∪ Aₙ
- ④ i ≠ j이면 Aᵢ ∩ Aⱼ = ∅
- 집합류: 집합 A에 포함되는 분할된 부분집합
