Total
Search
1. 기본사항
1.1. 논리학과 집합론
•
𝒑(𝒙) ∨ 𝒈(𝒙) → 𝑨 ∪ B
•
𝒑(𝒙) ∧ 𝒈(𝒙) → 𝑨 ∩ B
1.2. 집합과 원소
•
무정의 용어
◦
정의 없이 사용하는 용어
◦
직관적으로 이해할 수 있으나 다른 용어로 정의하기 힘든 대상을 표현하기 위해 사용
1.3. 집합의 표기법
•
𝒂를 S의 원소이고, b를 S의 원소가 아니라고 할 때,
◦
𝒂 ∈ 𝑺, 𝒃 ∉ 𝑺
•
집합의 표기 방법
◦
S는 중괄호( { , } )로표시함
1.
원소나열법 (예) S = {1, 2, 3}
2.
조건나열법 (예) S = { 𝒙｜𝟎 < 𝒙 < 𝟒 인 자연수}
1.4. 부분집합
•
부분집합
◦
A의 모든 원소가 B의 원소이면 A는 B의 부분집합이라 하고
◦
𝑨 ⊆ 𝑩 또는 𝐀 ⊂ 𝑩로 표기한다.
◦
즉, 𝑨 ⊆ 𝑩 ⇔ ∀𝒙 ( 𝒙 ∈ 𝑨 → 𝒙 ∈ 𝑩 )
•
진부분집합
◦
𝑨는 𝑩의 진부분집합
◦
⇔ 𝑨 ⊆ 𝑩, 𝑩 ⊆ 𝑨
⇔ 𝑨 ⊆ 𝑩, 𝑨 ≠ 𝑩
•
상동
◦
𝑨 = 𝑩 ⇔ 𝑨 ⊆ 𝑩 𝒂𝒏𝒅 𝑩 ⊆ 𝑨
1.5. 서로소
•
집합이 서로 중복되는 부분이 없을때. 교집합이 공집합일때
•
집합 A와 B는 서로소(disjoint) ⟺ 𝑨 ∩ 𝑩 = ∅
•
n개의 집합 𝑨𝟏, 𝑨𝟐, ⋯ ,𝑨𝒏은 쌍으로 서로소(pairwise disjoint)
1.6. 분할
•
집합 A를 ∅이 아닌 부분집합들로 나눌 때 A의 모든 원소들이 각각 나누어진 부분집합들 중 하나에만 포함될 경우 이 부분집합들 전체의 집합을 A의 분할이라고 함.
•
집합 𝑷 = {𝑨𝟏, 𝑨𝟐, ⋯ , 𝑨𝒏}이 집합 A의 분할
예제
1.7. 멱집합
•
집합 A의 모든 부분집합들의 집합을 A의 멱집합이라고 함
•
P(A)로 표기
•
공집합도 반드시 들어가야함
예제
2. 집합연산
2.1. 합집합
•
U: 전체집합, 𝑨 ⊂ 𝑼, 𝑩 ⊂ 𝑼라 할 때
•
𝑨 ∪ 𝑩 = {𝒙 ∈ 𝑼｜𝒙 ∈ 𝑨 ∨ 𝒙 ∈ 𝑩}
2.2. 교집합
•
U: 전체집합, 𝑨 ⊂ 𝑼, 𝑩 ⊂ 𝑼라 할 때
•
𝑨 ∩ 𝑩 = {𝒙 ∈ 𝑼｜𝒙 ∈ 𝑨 ∧ 𝒙 ∈ 𝑩}
2.3. 차집합
•
U: 전체집합, 𝑨 ⊂ 𝑼, 𝑩 ⊂ 𝑼라 할 때
•
𝑨 − 𝑩 = {𝒙 ∈ 𝑼｜𝒙 ∈ 𝑨 ∧ 𝒙 ∉ 𝑩}
2.4. 여집합 (보집합)
•
U: 전체집합, 𝑨 ⊂ 𝑼, 𝑩 ⊂ 𝑼라 할 때
•
𝑨^𝒄 = 𝑼 − 𝑨 = {𝒙 ∈ 𝑼｜𝒙 ∉ 𝑨}
2.5. 대칭차집합
•
U: 전체집합, 𝑨 ⊂ 𝑼, 𝑩 ⊂ 𝑼라 할 때
•
𝑨⨁𝑩 = {𝒙 ∈ 𝑼｜𝒙 ∈ 𝑨 ∪ 𝑩 ∧ 𝒙 ∉ 𝑨 ∩ 𝑩}
2.6. 곱집합
•
A와 B의 곱집합
•
𝑼를 전체집합, 𝑨 ⊂ 𝑼, 𝑩 ⊂ 𝑼라 할 때
•
𝑨의 원소 𝒂와 𝑩의 원소 𝒃로 만들어지는 순서쌍 (𝒂, 𝒃)들의 집합
•
𝑨 × 𝑩 = { (𝒂, 𝒃) | 𝒂 ∈ 𝑨, 𝒃 ∈ 𝑩 }
2.7. 집합 연산 예제
예제
3. 집합의 대수법칙 (1) 집합의 크기에 관한 성질
3.1. 합집합의 크기
•
집합 A, B가 유한집합이면 다음이 성립한다.
•
𝑨 ∪ 𝑩 = 𝑨 + 𝑩 − | 𝑨 ∩ 𝑩 |
증명
3.2. 합집합의 크기 따름 정리
•
집합 A, B, C가 유한집합이면
•
| 𝑨 ∪ 𝑩 ∪ 𝑪 | = |𝑨| + |𝑩| + |𝑪|
− | 𝑨 ∩ 𝑩 | − | 𝑨 ∩ 𝑪 | − | 𝑩 ∩ 𝑪 | + | 𝑨 ∩ 𝑩 ∩ 𝑪 |
3.3. 서로소인 집합의 합집합의 크기
•
집합 A, B가 유한집합이면서 서로소이면
| 𝑨 ∪ 𝑩 | = |𝑨| + |𝑩| 이다.
•
증명
◦
| 𝑨 ∪ 𝑩 | = |𝑨| + |𝑩| − |𝑨 ∩ 𝑩| (합집합의 크기 정리)
◦
그런데 A와 B는 서로소이므로 |𝑨 ∩ 𝑩| = 𝟎이다.
◦
따라서 | 𝑨 ∪ 𝑩 | = |𝑨| + |𝑩| 이다.
4. 집합의 대수법칙 (2) 포함관계
4.1. 교집합, 합집합, 포함관계의 이행성
•
모든 집합 A, B, C에 대해서 다음을 만족한다.
•
교집합
◦
(𝑨 ∩ 𝑩) ⊆ 𝑨
◦
𝑨 ∩ 𝑩 ⊆ 𝑩
•
합집합
◦
𝑨 ⊆ (𝑨 ∪ 𝑩)
◦
𝑩 ⊆ (𝑨 ∪ 𝑩)
•
이행성
◦
만약 𝑨 ⊆ 𝑩이고 𝑩 ⊆ 𝑪이면, 𝑨 ⊆ 𝑪이다.
•
cf) 원소 논증
◦
집합 𝑿, 𝒀에 대해 𝑿 ⊆ 𝒀를 증명하고자 할 때
∀𝒙 ∈ 𝑿 → 𝒙 ∈ 𝒀 임을 보인다.
◦
예: 𝑨 ∩ 𝑩 ⊆ 𝑩의 증명
▪
𝒙 ∈ 𝑨 ∩ 𝑩
→ 𝒙 ∈ 𝑨 ∧ 𝒙 ∈ 𝑩
→ 𝒙 ∈ 𝑩
4.2. 포함관계에 대한 동치
•
U : 전체집합, A, B ⊂ U 라 할 때, 다음은 모두 동치이다.
•
𝑨 ⊆ 𝑩
•
𝑩^𝒄 ⊆ 𝑨^𝒄
•
𝑨 ∪ 𝑩 = 𝑩
•
𝑨 ∩ 𝑩 = 𝑨
•
𝑨^𝒄 ∪ 𝑩 = 𝑼
•
𝑨 ∩ 𝑩^𝒄 = ∅
•
𝑨 − 𝑩 = ∅
5. 집합의 대수법칙 (3) 항등식
U : 전체집합, A,B,C ⊂ U 라 하자.
5.1. 분배법칙
•
A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
•
A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
5.2. 항등법칙
•
A ∪ ∅ = A
•
A ∩ U = A
5.3. 보수법칙
•
A ∪ A^c = U
•
A ∩ A^c = ∅
5.4. 이중보수법칙
•
(A^c)^c = A
5.5. 멱등법칙
•
A ∪ A = A
•
A ∩ A = A
5.6. 전체한계법칙
•
A ∪ U = U
•
A ∩ ∅ = ∅
5.7. 드모르간의 법칙
•
(A ∪ B)^c = A^c ∩ B^c
•
(A ∩ B)^c = A^c ∪ B^c
5.8. 흡수법칙
•
A ∪ (A ∩ B) = A
•
A ∩ (A ∪ B) = A
5.9. 전체집합과 공집합의 여집합
•
U^c = ∅
•
∅^c = U
5.10. 차집합법칙
•
A - B = A ∩ B^c