[이산수학] 집합, 합집합, 교집합, 집합의 대수법칙

˚ 집합

집합이란? 영어 대문자(A, B, C, D, … )로 표기하며 어떤 조건들에 의해 분류되서 모인 요소들의 모임.

집합의 표기방식

1) 원소나열법 : 집합에 포함되는 원소를 일일이 나열하는 방법

ex) A={1,2,3,4}

2) 조건제시법 : 집합에 포함되는 원소의 공통적인 성질을 조건식으로 제시하는 방법

ex) A={x|x<5, x∈N}

집합과 원소의 포함관계 : 1 ∈ A 또는 5 ∉ A

기수(Cardinality) : 집합 A가 포함하는 원소의 수    |A| = 4

상등(Equal) : 두 개의 집합의 원소가 동일할 때 '상등'한다고 한다.    A=B⇔(a∈A∧a∈B)

 

˚ 집합의 종류

1) 전체집합(Universal Set) U : 논의 대상이 되는 원소 전체를 포함하는 집합

2) 공집합(Empty Set) { } or ∅ : 원소를 포함하지 않은 집합, |∅|=0

3) 부분집합(Subset) A⊆B : A의 모든 원소가 B에 포함되는 경우, |A|≤|B|

4) 진부분집합(Proper Subset) A⊂B : B에 대하여 A의 요소 모두는 포함되어 있지 않은 부분 집합, |A|<|B|

 

˚ 집합의 연산

1) 합집합(Union) : 집합 A,B에 대하여 A에 속하거나 B에 속하는 원소로 되는 집합.

A∪B={x|x∈A∨x∈B}

2) 교집합(Intersection) : 집합 A,B에 대하여 A와 B에 동시에 속하는 원소로 되는 집합.

A∩B={x|x∈A∧x∈B}

3) 여집합 또는 보집합(Complement) : 전제집합에 속하지만 A를 제외 한 나머지.

A′={x|x∈U∧x∉A}=U-A

4) 차집합(Difference) : 집합 A,B에 대하여 A에 속하지만 B에 속하지 않는 집합.

A-B={x|x∈A∧x∉B}

5) 대칭차집합(Symmetric Difference) : 집합 A,B에 대하여 A-B 또는 B-A에 속하는 집합.

A⊕B={x|(x∈A∧x∉B)∨(x∈A∧x∉B)}={x|(x∈A-B)∨(x∈B-A)}

6) 서로소(Disjoint) : 집합 A,B에 대하여 공통으로 속하는 원소가 하나도 없는 경우.

A∩B=∅

 

˚집합의 대수법칙

집합	대수법칙
A∪∅=A,      A∩U=A	항등법칙(Identity Law)
A∪U=U,      A∩∅=∅	지배법칙(Domination Law)
A∪A=A,      A∩A=A	멱등법칙(Idempotent Law)
A∪B=B∪A, A∩B=B∩A	교환법칙(Communitive Law)
A∪(B∪C)=(A∪B)∪C A∩(B∩C)=(A∩B)∩C	결합법칙(Associative Law)
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)	분배법칙(Distribute Law)
(A′)′	이중 보법칙(Double negation Law)
A∪A′=U,      A∩A′=∅ ∅′=U,          U′=∅	보법칙(Complement Law)
(A∪B)′=A′∩B′,  (A∩B)′=A′∪B′	드모르간의 법칙(De Morgan's Law)
A∪(A∩B)=A,   A∩(A∪B)=A	흡수법칙(Absorption Law)

* 흡수법칙 증명

A∪(A∩B) = (A∪∅)∩(A∪B)    항등법칙

  = A∪(∅∩B)            분배법칙

  = A∪∅                  지배법칙

  = A                        항등법칙