✔ 논리학과 집합론
논리합 p(𝑥) ∨ g(𝑥) = 합집합 A ⋃ B
논리곱 p(𝑥) ∧ g(𝑥) = 교집합 A ⋂ B
✔ 집합과 원소
무정의 용어
- 정의 없이 사용하는 용어
- 직관적으로 이해할 수 있으나 다른 용어로 정의하기 힘든 대상을 표현하기 위해 사용
Georg Cantor의 집합 : 우리의 직관이나 사고로부터 한정적이고 분리된 객체들의 전체 M에서의 수집
✔ 집합의 표기법
S가 하나의 집합이라고 한다.
> a를 S의 원소이고, b를 S의 원소가 아니라고 할 때 : a ∈ S, b ∉ S
집합의 표기 방법
S는 중괄호 ( {, } )로 표시함
- 원소나열법
- 조건나열법
집합의 크기 : | S |
✔ 부분집합
부분집합(subset)
A의 모든 원소가 B의 원소이면 A는 B의 부분집합이라 하고 A ⊆ B 또는 A ⊂ B로 표기한다.
즉, A ⊆ B ↔ ∀𝑥 ( 𝑥 ∈ A → 𝑥 ∈ B )
진부분집합(proper subset)
A는 B의 진부분집합 ↔ A ⊆ B, B ⊈ A
↔ A ⊆ B, B ≠ A
상동(equal)
A = B ↔ A ⊆ B and B ⊆ A
✔ 서로소
서로소(disjoint), 쌍으로 서로소
> 집합 A와 B는 서로소(disjoint) ↔ A ⋂ B = ∅
> n개의 집합 A1, A2 ..., An 은 쌍으로 서로소(pairwise disjoint)
✔ 분할
분할(partition)
집합 A를 ∅이 아닌 부분집합들로 나눌 때 A의 모든 원소들이 각각 나누어진 부분집합들 중 하나에만 포함될 경우 이 부분집합들 전체 집합을 A의 분할이라고 함
✔ 멱집합
멱집합(power set)
집합 A의 모든 부분집합들의 집합을 A의 멱집합이라 하고 P(A)로 표기한다.
멱집합의 원소 수
| S | = n > | P(S) | = 2ⁿ
✔ 집합연산
합집합
A ⋃ B = {𝑥 ∈ U | 𝑥 ∈ A ∨ 𝑥 ∈ B}
교집합
A ⋂ B = {𝑥 ∈ ⋂ | 𝑥 ∈ A ∧ 𝑥 ∈ B}
차집합
A - B = {𝑥 ∈ U | 𝑥 ∈ A
여집합(보집합)
A∁ = U - A = { 𝑥 ∈ U | 𝑥 ∉ A}
대칭차집합
A⊕B = {𝑥 ∈ U | 𝑥 ∈ A U B ∧ 𝑥 ∉ A ⋂ B }
곱집합(Cartesian product)
U를 전체집합, A ⊂ U, B ⊂ U라 할 때 A의 원소 a와 B의 원소 b로 만들어지는 순서쌍 (a, b)들의 집합
AｘB = { (a, b) | a ∈ A. b ∈ B }
✔ 집합의 대수법칙
집합의 크기에 관한 성질
합집합의 크기
집합 A, B가 유한집합이면 다음이 성립한다.
| A ⋃ B | = |A| + |B| - | A ⋂ B |
따름정리
집합 A, B, C가 유한집합이면
| A ⋃ B ⋃ C | = |A| + |B| + |C|
- |A ⋂ B| - |A ⋂ C| - |B ⋂ C|
+ |A ⋂ B ⋂ C|
서로소인 집합의 합집합의 크기
집합 A, B가 유한집합이면서 서로소이면
| A ⋃ B | = |A| + |B| 이다.
포함관계 및 항등식
교집합, 합집합, 포함관계의 이행성
모든 집합 A, B, C에 대해서 다음을 만족한다. (논리학과 같이 생각해볼 수 있다.)
- 교집합
1. (A ⋂ B) ⊆ A
2. (A ⋂ B) ⊆ B - 합집합
1. A ⊆ (A ⋃ B)
2. B ⊆ (A ⋃ B) - 이행성
만약 A ⊆ B이고 B ⊆ C 이면, A ⊆ C 이다.
원소 논증
집합 X, Y에 대해 X ⊆ Y를 증명하고자 할 때
∀𝑥 ∈ X → 𝑥 ∈ Y임을 보인다.
집합의 항등식
U: 전체집합, A, B, C ⊂ U라 하자.
1. 교환법칙
(a) A ⋃ B = B ⋃ A / (b) A ⋂ B = B ⋂ A
2. 결합법칙
(a) ( A ⋃ B ) ⋃ C = A ⋃ (B ⋃ C )
(b) ( A ⋂ B ) ⋂ C = A ⋂ (B ⋂ C )
3. 분배법칙
(a) A ⋃ ( B ⋂ C ) = ( A ⋃ B ) ⋂ ( A ⋃ C )
(b) A ⋂ ( B ⋃ C ) = ( A ⋂ B ) ⋃ ( A ⋂ C )
4. 항등법칙
(a) A ⋃ ∅ = A / (b) A ⋂ U = A
5. 보수법칙
(a) A ⋃ A∁ = U / (b) A ⋂ A∁ = ∅
6. 이중보수법칙
(A∁)∁ = A
7. 멱등법칙
(a) A ⋃ A = A / (b) A ⋂ A = A
8. 전체한계법칙
(a) A ⋃ U = U / (b) A ⋂ ∅ = ∅
9. 드모르간의 법칙
(a) ( A U B )∁ = A∁ ⋂ B∁
(b) ( A ⋂ B)∁ = A∁ ⋃ B∁
10. 흡수법칙
(a) A ⋃ ( A ⋂ B ) = A
(b) A ⋂ ( A ⋃ B ) = A
11. U와 ∅의 여집합
(a) U∁ = ∅ / (b) ∅∁ = U
12. 차집합법칙
A - B = A ⋂ B∁
포함관계에 대한 동치
U: 전체집합 A, B ⊂ U라 할 때, 다음은 모두 동치이다.
A ⊆ B / B∁ ⊆ A∁ / A ⋃ B = B / A ⋂ B = A / A∁ ⋃ B = U A ⋂ B∁ = ∅ / A - B = ∅