[이산수학] 집합론

 

✔ 논리학과 집합론

논리합 p(𝑥) g(𝑥)  =  합집합 A ⋃ B

 

논리곱 p(𝑥) g(𝑥)  =  교집합 A B

 

 

✔ 집합과 원소

무정의 용어

  • 정의 없이 사용하는 용어
  • 직관적으로 이해할 수 있으나 다른 용어로 정의하기 힘든 대상을 표현하기 위해 사용

Georg Cantor의 집합 : 우리의 직관이나 사고로부터 한정적이고 분리된 객체들의 전체 M에서의 수집

 

 

✔ 집합의 표기법

S가 하나의 집합이라고 한다.

> a를 S의 원소이고, b를 S의 원소가 아니라고 할 때 : a ∈ S,   b ∉ S

 

집합의 표기 방법

S는 중괄호 ( {, } )로 표시함

  1. 원소나열법
  2. 조건나열법

집합의 크기 : | 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}

 

대칭차집합

AB = {𝑥 ∈ U | 𝑥 ∈ A U B ∧ 𝑥 ∉ A ⋂ B }

 

곱집합(Cartesian product)

U를 전체집합, A ⊂ U, B ⊂ U라 할 때 A의 원소 a와 B의 원소 b로 만들어지는 순서쌍 (a, b)들의 집합

AxB = { (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 = ∅