1. 왜 집합 연산이 필요한가
12강에서 집합의 기본 개념(원소, 부분집합, 멱집합)을 익혔다면, 13강에서는 여러 집합을 결합·비교하는 도구를 배운다. 두 개 이상의 집합이 주어졌을 때, 이들을 합치거나(합집합) 공통 부분만 추리거나(교집합) 차이를 보거나(차집합) 하는 등의 연산이 바로 그것이다.
집합 연산은 마치 여러 주머니에 든 물건들을 합치고, 빼고, 공통된 것만 골라내는 작업과 같다.
| 합집합 (∪) | 두 주머니 물건을 한 주머니에 합치기 |
| 교집합 (∩) | 두 주머니에 공통으로 들어 있는 물건만 모으기 |
| 차집합 (−) | 한 주머니에서 다른 주머니에 있는 물건 빼기 |
| 여집합 (¯) | 전체 중 특정 주머니에 없는 것만 모으기 |
13강의 모든 집합 연산은 사실 3강에서 배운 명제 논리 동치 법칙과 본질적으로 같다. ∧→∩, ∨→∪, ¬→¯로 치환하면 그대로 대응된다. 이 통찰은 11번 섹션에서 자세히 정리한다.
2. 합집합 (Union, ∪)
집합 A 또는 B에 속하는 모든 원소의 집합.
A ∪ B = { x | x ∈ A ∨ x ∈ B }
두 개의 주머니에 있는 모든 물건을 하나의 큰 주머니에 합치는 것. 중복은 한 번만 담는다.
| {1, 2, 3} | {3, 4, 5} | {1, 2, 3, 4, 5} |
| {a, b} | {b, c, d} | {a, b, c, d} |
| {1, 2} | ∅ | {1, 2} |
| 교환 법칙 | A ∪ B = B ∪ A |
| 결합 법칙 | A ∪ (B ∪ C) = (A ∪ B) ∪ C |
| 자기 포함 | A ∪ B ⊇ A, A ∪ B ⊇ B |
3. 교집합 (Intersection, ∩)
집합 A와 B 양쪽 모두에 동시에 속하는 원소의 집합.
A ∩ B = { x | x ∈ A ∧ x ∈ B }
두 주머니에 공통으로 들어있는 물건들만 모아 새 주머니에 담기.
| {1, 2, 3} | {3, 4, 5} | {3} |
| {a, b, c} | {x, y, z} | ∅ |
| {1, 2, 3} | {1, 2, 3} | {1, 2, 3} |
| 교환 법칙 | A ∩ B = B ∩ A |
| 결합 법칙 | A ∩ (B ∩ C) = (A ∩ B) ∩ C |
| 자기 포함 | A ∩ B ⊆ A, A ∩ B ⊆ B |
💡 합집합은 확장, 교집합은 축소의 연산이다. A ∪ B는 항상 A보다 크거나 같고, A ∩ B는 항상 A보다 작거나 같다.
4. 차집합 (Difference, −)
집합 A에는 속하지만 B에는 속하지 않는 원소의 집합.
A − B = { x | x ∈ A ∧ x ∉ B }
주머니 A에서 주머니 B에 있는 물건들을 모두 빼내기. A에만 있는 것들만 남는다.
| {1, 2, 3} | {3, 4, 5} | {1, 2} | {4, 5} |
| {a, b, c} | {b} | {a, c} | ∅ |
A − B ≠ B − A (일반적으로)
차집합은 순서가 중요하다.
정수 집합(ℤ) − 자연수 집합(ℕ) = 음의 정수 집합
5. 서로소 (Disjoint)
교집합이 공집합인 두 집합을 서로소라고 한다.
A와 B가 서로소 ⟺ A ∩ B = ∅
두 주머니에 공통으로 들어있는 물건이 전혀 없는 상태.
| 짝수 집합 | 홀수 집합 | ⭕ (교집합 ∅) |
| {1, 2, 3} | {4, 5, 6} | ⭕ |
| 학생 집합 | 교사 집합 | ⭕ (대부분의 경우) |
| {1, 2, 3} | {3, 4, 5} | ❌ (3이 공통) |
💡 응용: 데이터베이스 분할, 분류 시스템, 통계 표본 설계 등에서 "중복되지 않게 그룹을 나누는 것"이 곧 서로소 집합 만들기다.
6. 여집합 (Complement, ¯ 또는 ᶜ) ⭐
여집합을 이해하려면 먼저 전체집합 U 가 필요하다.
전체집합 U: 우리가 논의의 대상으로 삼는 모든 원소를 포함하는 가장 큰 집합
전체집합 U 중에서 집합 A에 속하지 않는 모든 원소의 집합.
Ā = U − A = { x | x ∈ U ∧ x ∉ A }
| Ā (위에 바) | 표준 표기 |
| Aᶜ | complement의 c |
| A ∪ Ā = U | A와 여집합을 합치면 전체 |
| A ∩ Ā = ∅ | A와 여집합은 서로소 |
| 모든 정수 | 짝수 | 홀수 |
| 학급 전체 | 남학생 | 여학생 |
| {1,2,3,4,5,6,7,8,9,10} | {1,3,5,7,9} | {2,4,6,8,10} |
💡 중요 — 전체집합 의존: 여집합은 항상 전체집합 U에 대해 정의된다. U가 바뀌면 여집합도 바뀐다. 시험에서 전체집합을 명시하지 않으면 답이 달라질 수 있으니 주의.
7. 포함-배제의 원리 (Inclusion-Exclusion Principle) ⭐
두 집합의 합집합 원소 개수를 정확히 세는 공식.
|A ∪ B| = |A| + |B| − |A ∩ B|
| 단순 더하기 | |A| + |B| | 교집합이 두 번 계산됨 |
| 보정 | − |A ∩ B| | 한 번 빼서 정확히 1번만 |
어떤 반에서:
- 춤을 잘 추는 학생: 15명
- 노래를 잘하는 학생: 20명
- 춤도 노래도 잘하는 학생: 8명
Q: 춤 잘 추거나 노래 잘하는 학생은 몇 명?
15 + 20 = 35명? ❌ (8명이 두 번 계산됨)
|A ∪ B| = 15 + 20 − 8 = 27명 ✅
A only: 7 공통: 8 B only: 12
┌─────────┬───────┬─────────┐
│ 7 │ 8 │ 12 │
└─────────┴───────┴─────────┘
(A=15) (교집합=8) (B=20)
총 합: 7 + 8 + 12 = 27
공식: 15 + 20 − 8 = 27 ✅💡 확장: 세 집합 이상에도 적용 가능 (단, 공식이 더 복잡해짐). 이산구조 시험에서는 두 집합 공식이 거의 100% 출제된다.
8. 집합 항등 법칙 (Set Identity Laws) ⭐⭐⭐
이제 본격적으로 집합의 14가지 항등 법칙을 정리한다. 3강에서 배운 명제 논리 동치 법칙과 거의 동일한 구조다.
| 1 | 항등 (Identity) | A ∪ ∅ = A, A ∩ U = A |
| 2 | 지배 (Domination) | A ∪ U = U, A ∩ ∅ = ∅ |
| 3 | 멱등 (Idempotent) | A ∪ A = A, A ∩ A = A |
| 4 | 보원 (Complement) | A ∪ Ā = U, A ∩ Ā = ∅ |
| 5 | 여집합 (Complementation) | (Ā)¯ = A |
| 6 | 교환 (Commutative) | A ∪ B = B ∪ A |
| 7 | 결합 (Associative) | (A∪B)∪C = A∪(B∪C) |
| 8 | 분배 (Distributive) ⭐ | A∩(B∪C) = (A∩B)∪(A∩C) |
| 9 | 드모르간 (De Morgan's) ⭐⭐ | (A∪B)¯ = Ā ∩ B̄ |
| 10 | 흡수 (Absorption) | A ∪ (A∩B) = A |
9. 항등 법칙 ① ~ ⑤ — 단일 집합 법칙
"어떤 집합에 ∅이나 U를 적용해도 자기 자신"
| A ∪ ∅ = A | A와 공집합 합쳐도 그대로 |
| A ∩ U = A | 전체 중 A인 것은 결국 A |
"U나 ∅이 너무 강력해서 다른 집합 덮어버림"
| A ∪ U = U | 전체와 합치면 전체 |
| A ∩ ∅ = ∅ | 공집합과 교집합은 공집합 |
"자기 자신과 합쳐도/교차해도 자기 자신"
| A ∪ A = A | A 또는 A는 A |
| A ∩ A = A | A 그리고 A도 A |
"원본과 여집합을 합치면 전체, 교차하면 공집합"
| A ∪ Ā = U | A와 not-A 합치면 전체 |
| A ∩ Ā = ∅ | A와 not-A는 공통 원소 없음 |
"여집합을 두 번 취하면 원래대로"
| (Ā)¯ = A | 여집합의 여집합 = 자기 자신 |
💡 명제 논리와의 대응: 위 5가지 법칙은 3강의 명제 동치 법칙과 완벽히 일대일 대응된다. ∧→∩, ∨→∪, ¬→¯, T→U, F→∅로 치환하면 그대로다.
10. 항등 법칙 ⑥ ~ ⑩ — 두 집합 이상 법칙
"순서를 바꿔도 결과 동일"
| A ∪ B = B ∪ A |
| A ∩ B = B ∩ A |
"괄호 위치를 바꿔도 결과 동일"
| (A ∪ B) ∪ C = A ∪ (B ∪ C) |
| (A ∩ B) ∩ C = A ∩ (B ∩ C) |
"다른 연산자 사이에서 분배 가능"
| A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) |
| A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) |
💡 명제 논리와의 차이: 일반 수학(숫자)에서는 곱셈만 덧셈에 분배되지만, 집합·논리에서는 양방향 모두 분배가 성립한다. ∪도 ∩에 분배 가능.
"여집합이 괄호 안으로 들어가면 ∪과 ∩이 뒤집힘"
| (A ∪ B)¯ = Ā ∩ B̄ | 합집합의 여집합 = 여집합의 교집합 |
| (A ∩ B)¯ = Ā ∪ B̄ | 교집합의 여집합 = 여집합의 합집합 |
"수업과 숙제를 둘 다 안 한 학생은 없다" ¯ = "수업을 했거나 숙제를 한 학생만 있다"
집합으로: ¬(수업 ∩ 숙제) = ¬수업 ∪ ¬숙제
"큰 명제가 작은 명제에 흡수됨"
| A ∪ (A ∩ B) = A |
| A ∩ (A ∪ B) = A |
"과일을 먹거나 (과일과 채소를 모두 먹거나)" = 그냥 "과일을 먹는다" (채소 여부는 무관)
11. 명제 논리 ↔ 집합론 완벽 대응표 ⭐
이 표만 외우면 명제 논리 모든 동치 법칙이 그대로 집합론 항등 법칙이 된다.
| ∧ (AND) | ∩ (교집합) |
| ∨ (OR) | ∪ (합집합) |
| ¬ (NOT) | ¯ (여집합) |
| T (True) | U (전체집합) |
| F (False) | ∅ (공집합) |
| → (함축) | ⊆ (부분집합) |
| ↔ (상호조건) | = (상등) |
💡 학습 효율 극대화: 3강의 동치 법칙을 완벽히 외웠다면, 이 대응표만 알면 13강의 항등 법칙을 따로 외울 필요가 없다. 두 세계가 본질적으로 같다.
12. 집합 증명 방법 ⭐⭐⭐ 시험 단골
두 집합 A와 B가 같음(A = B)을 증명하는 3가지 표준 방법이다.
A = B ⟺ (A ⊆ B) ∧ (B ⊆ A)
이 원리를 활용하는 3가지 방법을 살펴본다.
| ① 상호 부분집합 증명 | Mutual Subset Proof | 양방향 ⊆ 각각 증명 |
| ② 논리적 동치 활용 | Logical Equivalence | 논리식으로 변환 후 증명 |
| ③ 멤버십 표 | Membership Table | 모든 경우의 수를 표로 |
13. 증명 방법 ① — 상호 부분집합 증명 ⭐
A = B를 증명하려면:
- A ⊆ B 증명
- B ⊆ A 증명
- → A = B 결론
증명 대상: A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
| 1 | x ∈ A ∩ (B ∪ C) 가정 | 임의 원소 도입 |
| 2 | x ∈ A 그리고 x ∈ (B ∪ C) | 교집합 정의 |
| 3 | x ∈ A 그리고 (x ∈ B 또는 x ∈ C) | 합집합 정의 |
| 4-1 | Case 1: x ∈ B인 경우 → x ∈ A ∩ B | 교집합 정의 |
| 4-2 | Case 2: x ∈ C인 경우 → x ∈ A ∩ C | 교집합 정의 |
| 5 | 어느 경우든 x ∈ (A ∩ B) ∪ (A ∩ C) | 합집합 정의 |
| 6 | ∴ A ∩ (B ∪ C) ⊆ (A ∩ B) ∪ (A ∩ C) ✅ |
위와 유사한 방식으로 진행 (역방향).
양방향 ⊆ 모두 증명 완료 → A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) ✅
💡 풀이 패턴: "임의의 원소 x를 가정 → 정의 적용 → 경우 분석 → 반대 방향에 속함을 보임"의 흐름이 표준이다.
14. 증명 방법 ② — 논리적 동치 활용 ⭐
집합 연산을 논리 연산으로 변환한 뒤, 명제 논리의 동치 법칙(드모르간 등) 을 적용해 증명.
| x ∈ A ∩ B | x ∈ A ∧ x ∈ B |
| x ∈ A ∪ B | x ∈ A ∨ x ∈ B |
| x ∉ A | ¬(x ∈ A) |
| x ∈ Ā | ¬(x ∈ A) |
증명 대상: (A ∩ B)¯ = Ā ∪ B̄
| 1 | (A ∩ B)¯ = { x | x ∉ A ∩ B } | 여집합 정의 |
| 2 | = { x | ¬(x ∈ A ∧ x ∈ B) } | 교집합 정의 |
| 3 | = { x | ¬(x ∈ A) ∨ ¬(x ∈ B) } | 명제 드모르간 법칙 |
| 4 | = { x | x ∈ Ā ∨ x ∈ B̄ } | 여집합 정의 |
| 5 | = Ā ∪ B̄ ✅ | 합집합 정의 |
💡 핵심 통찰: 집합론의 모든 항등 법칙은 명제 논리의 동치 법칙과 본질적으로 같은 정리다. 한 번 증명되면 다른 쪽도 자동으로 증명된 셈.
15. 증명 방법 ③ — 멤버십 표 (Membership Table) ⭐
명제 논리의 진리표와 동일한 원리로, 원소가 각 집합에 속하면 1, 안 속하면 0 으로 표기하여 모든 경우를 비교.
증명 대상: (A ∪ B) − B = A − B
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 | 0 |
| 1 | 0 | 1 | 1 | 1 |
| 1 | 1 | 1 | 0 | 0 |
마지막 두 열 (A ∪ B) − B와 A − B의 결과가 모든 경우에서 동일하므로 두 집합은 같다 → (A ∪ B) − B = A − B ✅
| 2개 (A, B) | 2² = 4행 |
| 3개 (A, B, C) | 2³ = 8행 |
| n개 | 2ⁿ행 |
💡 시험 활용: 집합 등식 증명 문제에서 "어느 방법으로 증명하시오"를 지정하지 않으면, 멤버십 표가 가장 빠르고 안전하다. 기계적으로 채우면 끝.
16. 세 가지 증명 방법 비교 — 어떤 걸 쓸까?
| 상호 부분집합 | 모든 경우 적용 가능 | 시간 많이 걸림, 서술 길어짐 | 서술형 시험 |
| 논리적 동치 | 명제 논리 익숙하면 빠름 | 변환·역변환 필요 | 단답형 + 논리 익숙할 때 |
| 멤버십 표 | 기계적, 실수 적음 | 집합 많아지면 표 거대해짐 | 2~3개 집합 시 최적 |
| 집합이 2~3개 | 멤버십 표 |
| 명제 논리 동치 익숙 | 논리적 동치 |
| 서술형 답안 요구 | 상호 부분집합 |
📌 한눈에 보는 핵심정리
| 합집합 ∪ | A 또는 B에 속함 |
| 교집합 ∩ | A 와 B 모두에 속함 |
| 차집합 − | A에는 있고 B에는 없음 |
| 서로소 | A ∩ B = ∅ |
| 여집합 ¯ | 전체집합 U에서 A 제외 |
| 포함-배제 원리 | |A ∪ B| = |A| + |B| − |A ∩ B| |
| 항등 법칙 14선 | 명제 논리 동치 법칙과 1:1 대응 |
| 드모르간 법칙 | (A ∪ B)¯ = Ā ∩ B̄ |
| 분배 법칙 | A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) |
| 상등 증명 원리 | A = B ⟺ A ⊆ B ∧ B ⊆ A |
| 증명 방법 3가지 | 상호 부분집합 / 논리적 동치 / 멤버십 표 |
| 명제↔집합 대응 | ∧↔∩, ∨↔∪, ¬↔¯, T↔U, F↔∅ |
🧠 예상문제 2제
문제 1. 포함-배제 원리 응용
어떤 동아리에 50명의 학생이 있다.
- 코딩을 좋아하는 학생: 30명
- 디자인을 좋아하는 학생: 25명
- 코딩과 디자인 둘 다 좋아하는 학생: 10명
둘 중 어느 것도 좋아하지 않는 학생의 수는?
① 5명 ② 10명 ③ 15명 ④ 20명
👉 정답: ①
|A ∪ B| = |A| + |B| − |A ∩ B| = 30 + 25 − 10 = 45명
50 − 45 = 5명 ✅
| 코딩만 좋아함 | 30 − 10 = 20명 |
| 디자인만 좋아함 | 25 − 10 = 15명 |
| 둘 다 좋아함 | 10명 |
| 둘 다 안 좋아함 | 5명 ✅ |
| 합계 | 50명 ✅ |
💡 시험 빈출 패턴: 포함-배제 원리 문제는 "전체 − (A ∪ B) = 어느 것도 안 함" 공식까지 함께 묻는 경우가 많다. 두 단계로 끊어 풀면 실수가 줄어든다.
문제 2. 집합 항등 법칙 적용
다음 집합 표현을 가장 단순하게 정리한 결과는?
(A ∩ B) ∪ (A ∩ B̄)
① A ② B ③ A ∩ B ④ A ∪ B
👉 정답: ①
| 시작 | (A ∩ B) ∪ (A ∩ B̄) | — |
| 1 | A ∩ (B ∪ B̄) | 분배 법칙 (역방향) |
| 2 | A ∩ U | 보원 법칙 (B ∪ B̄ = U) |
| 3 | A ✅ | 항등 법칙 (A ∩ U = A) |
"A이면서 B인 것" 또는 "A이면서 B가 아닌 것" = 결국 모두 A
B인지 아닌지 상관없이, A에 속하면 둘 중 하나에는 반드시 들어간다. 따라서 결과는 그냥 A.
💡 고난도 적용: 이런 문제는 1번에 풀이가 보이지 않으면 분배 법칙을 역방향으로 적용할 수 있는지가 핵심이다. (A ∩ B) ∪ (A ∩ C) ≡ A ∩ (B ∪ C) 패턴을 거꾸로 인식하는 연습이 필요하다.
'📌 SW전공-개념 > 이산구조' 카테고리의 다른 글
| [이산구조 개념-15] 함수의 성질과 연산 — 단사·전사·전단사부터 합성까지 (1) | 2026.06.08 |
|---|---|
| [이산구조 개념-14] 함수의 기초 — 입력하면 출력된다, 매핑 머신의 수학 (0) | 2026.06.07 |
| [이산구조 개념-12] 집합의 기초 — 원소·표기·부분집합부터 데카르트 곱 (0) | 2026.06.05 |
| [이산구조 특별편 2] 공리의 반란 — 수학은 어떻게 진화하는가 (0) | 2026.06.04 |
| [이산구조 개념-11] 추론 엔진과 패러다임 변화 — 전문가 시스템에서 딥러닝까지 (0) | 2026.06.03 |