3장. 집합

이산수학

3장. 집합

이산수학

출처

본 강좌 자료는 이산수학 (2학년 / 3학점/ 3시간 / 이론) 수업에서 사용한 교재 [이산수학 (수학으로 이해하는 디지털 논리), 한빛

아카데미 출판사] 의 내용 등을 출처로 작성하였음을 알리는 바입니다.

이산수학

학습 목표

■ 컴퓨터 관련분야에서 자료의 수집, 분류와 결합은 정보 생성에 반드시 필요한 과정으로 효율적으로 정보 관리

■ 데이터베이스는 논리적으로 연관된 자료들의 집합으로 구성

■ 집합에 관련한 기본 개념과 표현 방법을 이해할 수 있다.

■ 집합에서 사용되는 연산을 이해할 수 있다.

이산수학

학습 내용

■ 집합의 개념과 종류

■ 집합 연산 이해

■ 집합의 대수법칙

이산수학

집합(Set)

■ 집합

◻명확한 기준에 의해 분류

◻공통의 성질을 갖는다

◻ 중복되지 않는 원소(element, member)의 모임

■ 집합의 표기 형식

◻ 원소나열법 : 집합 원소들을 콤마(,)로 구분하여 나열

◻ 조건제시법: 집합 원소의 공통적인 성질을 조건식으로 표현

■ 집합 𝐴의 크기

◻ 집합의 원소의 수

◻ |𝐴|

이산수학

예제

■ 다음 조건제시법으로 표기된 것을 원소나열법으로 표기하여라.

(1) 𝐵 = {b│b²=16, b∈𝑁} (2) 𝐶 = {c│c= ^𝑘

3, k∈𝑍}

(풀이) (1) 𝐵={4}

(2) 𝐶={…, − ⁵

3 , − ⁴

3 , − ³

3 , − ²

3 , − ¹

3 , −⁰

3 , ¹

3, ²

3, ³

3, ⁴

3, ⁵

3 , … }

이산수학

집합과 원소 관계

■ 𝑎가 집합 𝐴의 원소 ↔ 𝑎 ∈ 𝐴

■ 𝑎가 집합 𝐴의 원소가 아니다 ↔ 𝑎 ∉ 𝐴 (Ex)

1 𝑁 : 자연수의 집합 ⇒ 0 ∉ 𝑁

(2) Z : 정수의 집합 ⇒ 0.5 ∉ 𝑍, 0 ∈ 𝑍

이산수학

집합 상등

■ 두 집합 𝐴, 𝐵의 상등 관계

◻ ∀ 𝑥 ∈ 𝐴 ↔ ∀ 𝑥 ∈ 𝐵

■ 집합 𝐴 = * 𝑥│𝑥 ≤ −4, 𝑥 는 양의 정수}, 집합 𝐵 = *1,2,3,4+ 라 할 때 두 집합은 어떤 관계인가?

(풀이)

𝐴 = * 𝑥│𝑥 ≤ −4, 𝑥 는 양의 정수}={1, 2, 3, 4}= 𝐵 ∴ 집합 𝐴와 𝐵은 상등관계.

이산수학

집합의 종류

■ 전체 집합(Universal set)

◻ 논의 대상이 되는 원소 전체를 포함하는 집합

◻ 𝑈

■ 공집합(Empty set)

◻ 하나의 원소도 포함하지 않는 집합

◻ _, ∅

■ 부분집합 (Subset)

◻ 집합 𝐴, 𝐵에 대하여 ∀𝑥 ∈ 𝐴 ⇒ 𝑥 ∈ 𝐵

◻ 𝐴 ⊆ 𝐵

이산수학

집합 간의 포함관계 성질

■ Let 𝐴 be a set.

◻ 𝐴 ⊆ 𝐴

◻ ∅ ⊆ 𝐴

◻ 𝐴 ⊆ 𝑈

■ Let 𝐴, 𝐵, 𝐶 be sets

◻ 𝐴 ⊆ 𝐵 and 𝐵 ⊆ 𝐶 ⇒ 𝐴 ⊆ 𝐶

■ Let 𝐴, 𝐵 be sets

◻ 𝐴 = 𝐵 ⇔ 𝐵 ⊆ 𝐴 𝑎𝑛𝑑 𝐴 ⊆ 𝐵

이산수학

집합의 연산 : 합집합

■ 합집합 ( Union, ∪)

◻ 두 집합 𝐴, 𝐵가 있을 때, 집합 𝐴에 속하거나 𝐵에 속하는 원소들의 집합

◻ 𝐴 ∪ 𝐵 = * 𝑥│ 𝑥 ∈ 𝐴 ∨ 𝑥 ∈ 𝐵+

이산수학

집합의 연산 : 교집합

■ 교집합 ( Intersection, ∩)

◻ 두 집합 𝐴, 𝐵가 있을 때, 집합 𝐴와 𝐵에 모두 속하는 원소들의 집합

◻ 𝐴∩𝐵 = * 𝑥│ 𝑥 ∈ 𝐴 ∧ 𝑥 ∈ 𝐵+

■ 서로소(Disjoint)

◻두 집합 A와 B의 교집합이 공집합이면 두 집합은 서로소이다.

이산수학

합집합과 교집합의 기수

■ 기수 (Cardinal number)

◻집합의 크기를 나타내는 척도

■ 집합 𝐴의 크기 : |𝐴|

■ │𝐴 ∪ 𝐵│ = │𝐴│ + │𝐵│ − │𝐴 ∩ 𝐵│

■ │𝐴 ∪ 𝐵 ∪ 𝐶│ = │𝐴│ + │𝐵│ + │𝐶│ − │𝐴 ∩ 𝐵│ − │𝐴 ∩ 𝐶│ − │𝐵 ∩ 𝐶│ + │𝐴 ∩ 𝐵 ∩ 𝐶│

■ │𝐴 ∩ 𝐵│ = │𝐴│ + │𝐵│ − │𝐴 ∪ 𝐵│

■ 𝐴 ∩ 𝐵 = Ø인 경우, │𝐴 ∪ 𝐵│ = │𝐴│ + │𝐵│

이산수학

집합의 연산 : 여집합

■ 집합 𝐴의 여집합 (Complementary set)

◻ 전체집합 𝑈가 정의되어 있을 때, 전체집합 𝑈에 속하면서 집합 𝐴에는 속하지 않는 원소의 집합

◻ 𝐴^𝐶 = {𝑥|𝑥 ∈ 𝑈 ˄ 𝑥 ∉ 𝐴} = 𝑈 − 𝐴

◻ (𝐴 𝑈 𝐵)^𝐶 = 𝐴 ^𝐶 ∩ 𝐵𝐶

𝐴^𝐶 𝐴

𝑈

이산수학

집합의 연산 : 차집합

■ 집합 𝐵에서 집합 𝐴의 차집합 (Difference set)

◻집합 𝐵의 원소에서 집합 𝐴의 원소를 뺀 집합

◻ 𝐵 − 𝐴 = { 𝑥 ∈ 𝐵 | 𝑥 ∉ 𝐴}

이산수학

집합의 연산 : 곱집합

■ 두 집합 𝑋와 𝑌의 곱집합 (Cartesian Product)은 집합 𝐴와 𝐵의 순서쌍들의 집합

■ 𝑋 × 𝑌 = 𝑥, 𝑦 | ∀𝑥 ∈ 𝑋, ∀𝑦 ∈ 𝑌

■ | 𝑋 × 𝑌 |=|𝑋|∙| 𝑌|

■ _𝛼∈𝐼 𝑋_𝛼 = 𝑓: 𝐼 → _𝛼∈𝐼𝑋_𝛼 | 𝑓 𝛼 𝜖 𝑋_𝛼 ∀𝛼 ∈ 𝐼 , 𝐼은 임의의 집합

이산수학

집합의 연산 : 멱집합

■ 집합 𝑆의 멱집합(Power set)

■ 집합 𝑆의 모든 부분집합을 모은 집합을 말한다.

■ 𝑃 𝑆 , 2^𝑆, {0, 1}^𝑆 등을 사용

■ | 𝑃 𝑆 | = 2^|𝑆|

이산수학

예제

■ 집합 𝑆 = * 𝑥, 𝑦, 𝑧+이라 하자. 집합 𝑆의 멱집합을 구하시오.

(풀이)

집합 𝑆의 모든 부분 집합:

∅, 𝑥 , 𝑦 , *𝑧+, *𝑥, 𝑦+, *𝑥, 𝑧+, *𝑦, 𝑧+, *𝑥, 𝑦, 𝑧+

∴ 𝑃(𝑆) = *∅, *𝑥+, *𝑦+, *𝑧+, *𝑥, 𝑦+, *𝑥, 𝑧+, *𝑦, 𝑧+, *𝑥, 𝑦, 𝑧++

이산수학

집합의 대수법칙

이산수학

예제

■ 드모르간의 법칙 (𝐴 ∪ 𝐵) = 𝐴 ∩ 𝐵을 증명하시오.

(풀이)

𝑥 ∈ (𝐴 ∪ 𝐵) ⇔ 𝑥 ∉ 𝐴 ∪ 𝐵 ⇔ 𝑥 ∉ 𝐴 ∧ 𝑥 ∉ 𝐵 ⇔ 𝑥 ∈ 𝐴 ∧ 𝑥 ∈ 𝐵 ⇔ 𝑥 ∈ 𝐴 ∩ 𝐵

이산수학

예제

■ 𝐴 ∩ (𝐴 ∪ 𝐵) = 𝐴 을 증명하시오.

(풀이)

𝐴 ∩ (𝐴 ∪ 𝐵) = (𝐴 ∪ ∅) ∩ ( 𝐴 ∪ 𝐵 ) ∵ 항등법칙 = 𝐴 ∪ (∅ ∩ 𝐵) ∵ 분배법칙 = 𝐴 ∪ ∅ ∵ 지배법칙 = 𝐴 ∵ 항등법칙

이산수학

예제

■ 𝐴 – 𝐵 = 𝐴 ∩ 𝐵 을 증명하시오.

(풀이)

𝑥 ∈ 𝐴 – 𝐵 ⇔ 𝑥 ∈ (𝐴 ∩ 𝑈) − 𝐵

⇔ 𝑥 ∈ (𝐴 ∩ 𝑈) ∧ 𝑥 ∈ (𝑈 − 𝐵) ⇔ 𝑥 ∈ 𝐴 ∩ 𝐵

이산수학

예제

■ 𝐴 ∩ 𝐴 = ∅ 을 증명하시오.

(풀이)

𝑥 ∈ 𝐴 ∩ 𝐴 ⇔ 𝑥 ∈ 𝐴 ∧ 𝑥 ∈ 𝐴 ⇔ 𝑥 ∈ 𝐴 ∧ 𝑥 ∉ 𝐴

⇔ ∄ 𝑥 i.e., ∅

이산수학

예제

■ 𝐴 × (𝐵 ∩ 𝐶) = (𝐴 × 𝐵) ∩ (𝐴 × 𝐶)을 증명하시오.

(풀이)

𝐴 × 𝐵 ∩ 𝐶

⇔ 𝑥 ∈ 𝐴 ∧ 𝑦 ∈ (𝐵 ∩ 𝐶 ) ∵ 곱집합의 정의 ⇔ 𝑥 ∈ 𝐴 ∧ (𝑦 ∈ 𝐵 ∧ 𝑦 ∈ 𝐶 ) ∵ 교집합의 정의 ⇔ (𝑥 ∈ 𝐴 ∧ 𝑦 ∈ 𝐵 ) ∧ (𝑥 ∈ 𝐴 ∧ 𝑦 ∈ 𝐶 ) ∵ 분배법칙

⇔ ,(𝑥, 𝑦) ∈ 𝐴 × 𝐵- ∧ ,(𝑥, 𝑦) ∈ 𝐴 × 𝐶 - ∵ 곱집합의 정의 ⇔ (𝑥. 𝑦) ∈ (𝐴 × 𝐵 ) ∩ (𝐴 × 𝐶 ) ∵ 교집합의 정의

이산수학

예제

■ 집합의 대수법칙을 사용하여 (𝐴 ∩ 𝐵) ∪ (𝐴 ∩ 𝐵)∪(𝐴 ∩ 𝐵 ) 을 간략화하시오.

(풀이)

(𝐴 ∩ 𝐵) ∪ (𝐴 ∩ 𝐵)∪(𝐴 ∩ 𝐵 )

= (𝐴 ∩ 𝐵) ∪ [(𝐴 ∩ 𝐵)∪(𝐴 ∩ 𝐵 ) ] ∵ 결합법칙 = (𝐴 ∩ 𝐵 ) ∪[𝐴 ∩ (𝐵∪𝐵 )] ∵ 분배법칙 = (𝐴 ∩ 𝐵 )∪[𝐴 ∩ 𝑈 ] ∵ 보법칙

= (𝐴 ∩ 𝐵 )∪𝐴 ∵ 항등법칙

= (𝐴 ∪ 𝐴 ) ∩ (𝐵 ∪𝐴 ) ∵ 분배법칙

= 𝑈 ∩ (𝐵 ∪𝐴 ) ∵ 보법칙

= 𝐵 ∪𝐴 ∵ 항등법칙

= 𝐴 ∪𝐵 ∵ 교환법칙

이산수학

예제

■ 집합의 대수법칙을 사용하여 (𝐴 ∪ 𝐵 ) – (𝐴 ∩ 𝐵) = 𝐴 ∩ 𝐵 을 간략화하시오.

(풀이)

(𝐴 ∪ 𝐵 ) – (𝐴 ∩ 𝐵) = (𝐴 ∩ 𝐵 ) - (𝐴 ∩ 𝐵) ∵ 드모르간의 법칙 = (𝐴 ∩ 𝐵 ) − (𝐴 ∩ 𝐵) ∵ 이중 보법칙 = (𝐴 ∩ 𝐵 )∩(𝐴 ∪ 𝐵) ∵ 𝐴 − 𝐵 = 𝐴 ∩ 𝐵 = (𝐴 ∩ 𝐵 ) ∩(𝐴 ∩ 𝐵 ) ∵ 드모르간의 법칙 = (𝐴 ∩ 𝐵 ) ∩ (𝐴 ∪ 𝐵 ) ∵ 이중 보법칙 = 𝐴 ∩ ,𝐵 ∩ (𝐴 ∪ 𝐵 ) ∵ 결합법칙 = 𝐴 ∩ ,(𝐵 ∩ 𝐴 ) ∪ (𝐵 ∩ 𝐵 ) ∵ 분배법칙 = 𝐴 ∩ ,𝐵 ∩ 𝐴 ∪ ∅) ∵ 보법칙 = 𝐴 ∩ (𝐵 ∩ 𝐴) ∵ 항등법칙 = 𝐴 ∩ 𝐵 ∵ 멱등법칙

26

이산수학

집합의 분할

■ 공집합이 아닌 임의의 집합 𝑋를 서로소인 공집합이 아닌 부분집합으로 분할

■ 집합 𝑋의 멱집합의 부분집합 𝑃 의 분할의 성질 1. ∅ ∉ 𝑃

2. _𝐴∈𝑃 𝐴 = 𝑋

3. If A, B ∈ 𝑃 𝑎𝑛𝑑 𝐴 ≠ 𝐵 𝑡ℎ𝑒𝑛 𝐴 ∩ 𝐵 = ∅

이산수학

분할의 성질

■ 모든 singleton 집합 𝑥 은 정확히 한개의 분할을 갖는다. 즉, 𝑥

■ 공집합이 아닌 임의의 집합 𝑋에 대해, 𝑃 = 𝑋 은 집합𝑋의 분할이다.

■ 공집합이 아닌 임의의 집합 𝑋 ⊂ 𝑈에 대해, 𝑃 = 𝑋, 𝑋 은 집합 𝑈의 분할이다.

이산수학

분할의 개수

■ 집합 𝑁 = 1, 2, 3, ⋯ , 𝑛 , 𝑁 = 𝑛 의 분할의 개수

■ Bell number (𝐵_𝑛)

◻ 𝐵₀ =1, 𝐵₁ =1, 𝐵₂ =2, 𝐵₃ =5, 𝐵₄ =15 등

◻ 𝐵_𝑛+1 = ^𝑛_𝑘=0 ^𝑛_𝑘 𝐵_𝑘

◻ 1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, …

이산수학

예제

■ 집합 𝑋 = 1, 2, 3 의 모든 분할 𝑃을 구하시오.

(풀이) 총 분할의 수 = 𝐵₃ =5 (1) 𝑃 = **1+, *2+, *3++

(2) 𝑃 = **1, 2+, *3++

(3) 𝑃 = **1, 3+, *2++

(4) 𝑃 = **3, 2+, *1++

(5) 𝑃 = **1, 2,3++