[이산수학] 집합의 서로소, 분할, 멱집합 개념

📌 1. 서로소 집합 (Disjoint Sets)

정의:

두 집합이 공통 원소를 전혀 갖지 않으면, 서로소(disjoint)라고 한다.

 

예시:

• A={1,2,3}, B={4,5}
  • 공통 원소 없음 → 서로소
• C={2,3}, D={3,4}
  • 공통 원소 {3} 있음 → 서로소 아님

 

📌 2. 집합의 분할 (Partition)

정의:

어떤 집합 A를 겹치지 않는 부분집합들로 나누되, 그 부분집합들을 모두 합치면 원래의 집합 A가 되는 경우, 이를 분할이라 한다.

 

조건:

1. 모든 부분집합은 공집합이 아님.
2. 부분집합들은 서로소.
3. 부분집합들을 합치면 원래 집합과 같음.

예시:

• A={1,2,3}
  • 분할 예: { {1}, {2,3} }
  • 또 다른 분할 예: { {1,2}, {3} }
  • 틀린 예: { {1,2}, {2,3} } → 2가 중복됨

 

📌 3. 멱집합 (Power Set)

정의:

어떤 집합의 모든 부분집합들을 원소로 가지는 집합을 멱집합이라고 한다. 공집합도 포함한다.

 

멱집합의 원소 개수:

집합 A의 원소 개수가 n개이면, 멱집합 P(A)의 원소는 2ⁿ개다.

 

예시:

• A={x,y}
  • 부분집합:
    ∅, {x}, {y}, {x,y}
  • 따라서
    P(A) = { ∅, {x}, {y}, {x,y} }