논리학과 집합론
- p(x) ∨ q(x) => A∪B => 합집합
- p(x) ∧ q(x) => A ∩ B => 교집합
집합과 원소
- 무정의 용어
- 정의 없이 사용하는 용어
- 직관적으로 이해할 수 있으나 다른 용어로 정의하기 힘든 대상을 표현하기 위해 사용
집합의 표시법
- S가 하나의 집합. a를 S의 원소이고, b를 S의 원소가 아니라고 할 때
→ : a ∈ S, b ∉ S
- 집합의 표기 방법
- S는 중괄호{ }로 표기함
- 원소 나열법. ex) S = {1,2,3}
-
| 조건 나열법. ex) S = { x |
0 < x < 4인 자연수 }
|
-
부분집합
- A의 모든 원소가 B의 원소라면 A는 B의 부분 집합
- A⊆B 또는 A⊂B로 표기한다.
- ≡ (∀x)[(x ∈ A) → (x ∈ B)]
- 진부분집합
- A⊆B, B⊄A. B가 더 크고 A는 그 안에 속함
- 상동
- A⊆B, B⊆A. A와 B가 같음. 서로가 서로의 부분집합
서로소
- 교집합이 공집합 일 때
- A ∩ B = ∅
- 쌍으로 서로소 = 여러개의 집합이 모두 교집합이 없을
분할
- 집합 A를 ∅이 아닌 부분집합들로 나눌 때 A의 모든 원소들이 각각 나누어진 부분집합들 중 하나에만 포함 될 경우 (쌍으로 서로소)
- 부분집합들 전체의 집합을 A의 분할이라고 함
멱집합
- 집합 A의 모든 부분집합들의 집합을 A의 멱집합이라고 함
- P(A)
-
| 멱집합의 원소 수 : |
S |
= n → |
P(S) |
= 2²
|
집합 연산
- 합집합
-
| A ∩ B = {x |
(x∈A) ∨ (x∈B) }
|
- 교집합
-
| A ∩ B = {x |
(x∈A) ∧ (x∈B) }
|
- 차집합
-
| A - B = {x∈U |
(x∈A) ∧ (x⊄B) }
|
- 여집합
-
| Ac = U - A = {x∈U |
(x∈U) |
(x⊄A) }
|
- 대칭집합
-
| {x∈U |
(x ∈ A∪B) ∧ (x ⊄ A∩B) }
|
- 곱집합
집합의 대수법칙
- 집합의 크기에 관한 성질
- 포함관계 및 항등식
- 교집합, 합집합, 포함관계의 이행성
- 교집합 보다는 각각의 부분 집합이 크다
- 각각의 부분 집합 보다는 합집합이 크다
- A⊆B이고 B⊆C이면 A⊆C 이다
- 원소 논증
- A⊆B에 대해 증명하고자 할때 ∀x∈A → x∈B임을 보인다
- 교환법칙 : A∪B = B∪A
- 결합법칙 : (A∪B)∪C=A∪(B∪C)
- 분배법칙 : A∩(B∪C)=(A∩B)∪(A∩C)
- 항등법칙 : A∪U=U, A∩Ø=Ø
- 보수법칙 : A∪A∁ = U
- 이중보수법칙 : (A∁)∁ = A
- 멱등법칙 : A∪A = A
- 드모르간법칙 : (A ∪ B)∁ = A∁ ∩ B∁
- 흡수법칙 : A∪(A∩B)=A
- 차집합법칙 : A-B = A ∩ B∁
