방송대 방통대 이산수학 4강 - 집합론 - 요약 노트 시험족보 예상문제 - 올에이클래스

이산수학 4강 - 집합론

집합과 원소의 표현부터 부분집합, 분할, 멱집합을 차례로 익히고 합집합·교집합·차집합·여집합·대칭차집합·곱집합의 의미를 살펴본다. 이어 집합의 크기를 계산하는 포함배제 원리와 다양한 집합 항등식, 포함관계의 동치 조건을 학습한다.

제1장 집합의 기본 개념

1. 논리학과 집합론

집합론은 여러 대상을 하나의 모임으로 다루는 수학적 언어이다. 명제논리에서 논리합 p(x) ∨ q(x)는 두 조건 중 적어도 하나를 만족한다는 뜻이며, 집합에서는 이에 대응하여 합집합 A ∪ B를 사용한다. 논리곱 p(x) ∧ q(x)는 두 조건을 모두 만족한다는 뜻이고, 집합의 교집합 A ∩ B와 연결된다. 이처럼 집합의 연산과 법칙은 논리식의 구조와 밀접하게 대응한다.

2. 집합과 원소

집합(set)과 원소(element)는 다른 개념으로 더 정의하기 어려워 직관적으로 받아들이는 무정의 용어이다. 칸토어는 집합을 직관이나 사고로부터 한정적이고 서로 구별되는 객체들을 모은 것으로 설명하였다. 어떤 대상 a가 집합 S에 속하면 a ∈ S, 속하지 않으면 a ∉ S로 쓴다.

원소와 집합을 구별하자. a는 하나의 원소이고 {a}는 a를 원소로 갖는 집합이다. 따라서 a와 {a}는 서로 다르다. 또한 집합에서는 원소의 나열 순서와 중복을 고려하지 않으므로 {a, b, a, c} = {a, b, c}이다.

3. 집합의 표현

집합은 중괄호 { }로 나타낸다. 원소나열법은 S = {1, 2, 3}처럼 원소를 직접 나열하는 방식이고, 조건제시법은 S = {x | 0 < x < 4인 자연수}처럼 원소가 만족하는 조건을 제시하는 방식이다. 예를 들어 수직선에서 −3보다 크고 4 이하인 실수의 집합은 {x | −3 < x ≤ 4인 실수}로 쓴다.

유한집합 S에 들어 있는 서로 다른 원소의 개수는 집합의 크기(cardinality)라 하며 |S|로 표시한다. S = {1, 2, 3}이면 |S| = 3이다.

구분	표현	의미
소속 관계	a ∈ A	a가 집합 A의 원소이다.
비소속 관계	b ∉ A	b가 집합 A의 원소가 아니다.
원소나열법	A = {1, 2, 3}	집합의 원소를 직접 나열한다.
조건제시법	A = {x | 조건}	원소가 만족해야 할 조건을 제시한다.
집합의 크기	|A|	유한집합 A의 서로 다른 원소 수이다.

제2장 부분집합과 집합의 상등

1. 부분집합

집합 A의 모든 원소가 집합 B의 원소이면 A를 B의 부분집합(subset)이라 하고 A ⊆ B로 쓴다. 논리식으로는 A ⊆ B ⇔ ∀x(x ∈ A → x ∈ B)이다. 공집합 ∅은 원소가 하나도 없으므로 모든 집합의 부분집합이다.

소속과 포함은 다르다. x ∈ A는 x가 A의 원소라는 뜻이고, X ⊆ A는 집합 X의 모든 원소가 A에 속한다는 뜻이다. 예를 들어 2 ∈ {1, 2}는 참이지만 2 ⊆ {1, 2}는 수 2를 집합으로 보지 않는 한 올바른 표현이 아니다.

2. 진부분집합과 상등

A ⊆ B이면서 A ≠ B이면 A는 B의 진부분집합(proper subset)이다. 이는 A ⊆ B이고 B ⊈ A인 것과 같다. 한편 두 집합이 같다는 것은 원소가 완전히 같다는 뜻이므로 A = B ⇔ A ⊆ B이고 B ⊆ A이다. 이 성질은 집합의 상등을 증명할 때 양방향 포함을 각각 보이는 근거가 된다.

3. 서로소와 쌍으로 서로소

A ∩ B = ∅이면 두 집합 A와 B는 서로소(disjoint)이다. 여러 집합 A₁, A₂, …, A_n이 쌍으로 서로소(pairwise disjoint)라는 말은 서로 다른 모든 i, j에 대하여 A_i ∩ A_j = ∅이라는 뜻이다. 단지 전체 집합을 한꺼번에 교집합한 결과가 공집합이라는 것만으로는 쌍으로 서로소라고 할 수 없다.

예를 들어 A₁ = {a, b, d}, A₂ = {c, e}, A₃ = {b, f}라 하자. A₁과 A₂, A₂와 A₃은 서로소이지만 A₁ ∩ A₃ = {b}이므로 세 집합은 쌍으로 서로소가 아니다.

제3장 분할과 멱집합

1. 집합의 분할

집합 A의 분할(partition)은 A를 겹치지 않는 비어 있지 않은 부분집합들로 빠짐없이 나눈 것이다. P = {A₁, A₂, …, A_n}가 A의 분할이 되려면 다음 세 조건을 만족해야 한다.

① 각 A_i는 공집합이 아니다.
② A₁ ∪ A₂ ∪ … ∪ A_n = A이다.
③ 서로 다른 i, j에 대하여 A_i ∩ A_j = ∅이다.

A = {1, 2, 3}의 모든 분할은 {{1}, {2}, {3}}, {{1, 2}, {3}}, {{1, 3}, {2}}, {{1}, {2, 3}}, {{1, 2, 3}}의 다섯 가지이다. 반면 {∅, {1, 2}, {3}}은 공집합을 포함하고, {{1, 2}, {2, 3}}은 2가 겹치며, {{1}, {2}}는 3을 빠뜨리므로 분할이 아니다. A ≠ ∅일 때 {A}는 A 전체를 한 블록으로 삼는 자명한 분할이다.

모든 정수의 집합 Z를 짝수 집합 Z₀ = {z | z = 2k, k는 정수}와 홀수 집합 Z₁ = {z | z = 2k + 1, k는 정수}로 나누면 Z₀ ∪ Z₁ = Z이고 Z₀ ∩ Z₁ = ∅이다. 따라서 {Z₀, Z₁}은 Z의 분할이다.

2. 멱집합

집합 A의 모든 부분집합을 원소로 갖는 집합을 A의 멱집합(power set)이라 하고 P(A)로 쓴다. S = {a, b, c}이면 P(S) = {∅, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}}이다. 공집합과 S 자신도 S의 부분집합이므로 반드시 포함된다.

|S| = n이면 각 원소마다 부분집합에 ‘포함한다’와 ‘포함하지 않는다’의 두 선택이 있으므로 |P(S)| = 2ⁿ이다. 원소가 3개인 집합의 멱집합 크기는 2³ = 8이다.

제4장 집합의 기본 연산

전체집합을 U, A와 B를 U의 부분집합이라 하자. 집합 연산은 각 원소가 A와 B에 속하는지를 논리 조건으로 판정한다.

연산	정의	핵심 의미
합집합	A ∪ B = {x ∈ U | x ∈ A ∨ x ∈ B}	A 또는 B 중 적어도 하나에 속한다.
교집합	A ∩ B = {x ∈ U | x ∈ A ∧ x ∈ B}	A와 B 모두에 속한다.
차집합	A − B = {x ∈ U | x ∈ A ∧ x ∉ B}	A에는 속하고 B에는 속하지 않는다.
여집합	Ac = U − A = {x ∈ U | x ∉ A}	전체집합에서 A를 제외한다.
대칭차집합	A ⊕ B = {x ∈ U | x ∈ A ∪ B ∧ x ∉ A ∩ B}	둘 중 정확히 한 집합에만 속한다.

예를 들어 U = {1, 2, 3, 4, 5}, A = {1, 2, 3}, B = {2, 3, 4}이면 A ∪ B = {1, 2, 3, 4}, A ∩ B = {2, 3}, A − B = {1}, A^c = {4, 5}이다. 두 집합의 공통 원소를 제외한 대칭차집합은 A ⊕ B = {1, 4}이다.

차집합은 순서가 중요하여 일반적으로 A − B ≠ B − A이다. 반면 대칭차집합은 두 집합 중 한쪽에만 속하는 원소를 모으므로 A ⊕ B = B ⊕ A이다.

곱집합

A의 원소 a와 B의 원소 b로 만드는 모든 순서쌍 (a, b)의 집합을 A와 B의 곱집합(Cartesian product)이라 한다. 기호로는 A × B = {(a, b) | a ∈ A, b ∈ B}이다. 순서쌍은 순서를 구별하므로 일반적으로 A × B와 B × A는 같지 않다. 유한집합에서는 |A × B| = |A||B|가 성립한다.

제5장 집합의 크기와 포함배제 원리

1. 두 집합의 합집합 크기

유한집합 A와 B의 원소 수를 단순히 더하면 A ∩ B에 속한 원소가 두 번 세어진다. 따라서 중복된 교집합의 크기를 한 번 빼야 한다.

|A ∪ B| = |A| + |B| − |A ∩ B|

A ∪ B를 서로소인 A와 B − A로 나누면 |A ∪ B| = |A| + |B − A|이다. 또 B는 서로소인 B − A와 A ∩ B로 나뉘므로 |B − A| = |B| − |A ∩ B|이다. 이를 앞 식에 대입하면 공식이 얻어진다.

2. 세 집합의 합집합 크기

세 유한집합에서는 각 집합의 크기를 더하고 두 집합씩의 교집합 크기를 뺀 뒤, 세 집합의 공통부분이 지나치게 빠진 것을 보정하기 위해 세 집합의 교집합 크기를 다시 더한다.

|A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|

3. 서로소인 집합의 경우

A와 B가 서로소이면 A ∩ B = ∅이므로 |A ∩ B| = 0이다. 따라서 포함배제 공식은 |A ∪ B| = |A| + |B|로 단순해진다.

제6장 포함관계와 집합 항등식

1. 기본 포함관계와 이행성

모든 집합 A, B에 대하여 A ∩ B ⊆ A, A ∩ B ⊆ B이고, A ⊆ A ∪ B, B ⊆ A ∪ B이다. 또한 A ⊆ B이고 B ⊆ C이면 A ⊆ C인 이행성이 성립한다.

집합 X ⊆ Y를 증명하는 대표적인 방법은 원소 논증이다. 임의의 x ∈ X를 잡고 x ∈ Y임을 보이면 된다. 예를 들어 x ∈ A ∩ B이면 x ∈ A이면서 x ∈ B이므로 곧 x ∈ B이다. 따라서 A ∩ B ⊆ B이다. 두 집합 X와 Y가 같음을 증명하려면 X ⊆ Y와 Y ⊆ X를 모두 보인다.

2. 집합의 항등식

법칙	합집합 형태	교집합 형태
교환법칙	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 ∪ ∅ = A	A ∩ U = A
보수법칙	A ∪ Ac = U	A ∩ Ac = ∅
멱등법칙	A ∪ A = A	A ∩ A = A
전체한계법칙	A ∪ U = U	A ∩ ∅ = ∅
흡수법칙	A ∪ (A ∩ B) = A	A ∩ (A ∪ B) = A

이중보수법칙은 (A^c)^c = A이며, 전체집합과 공집합의 여집합은 각각 U^c = ∅, ∅^c = U이다. 차집합법칙은 A − B = A ∩ B^c로, 차집합을 교집합과 여집합만으로 표현한다.

3. 드모르간의 법칙

(A ∪ B)^c = A^c ∩ B^c
(A ∩ B)^c = A^c ∪ B^c

합집합 전체를 부정하면 각 집합을 부정한 것의 교집합이 되고, 교집합 전체를 부정하면 각 집합을 부정한 것의 합집합이 된다. 즉 여집합을 괄호 안으로 분배할 때 ∪와 ∩이 서로 바뀐다.

4. 포함관계에 대한 동치

U를 전체집합, A와 B를 U의 부분집합이라 할 때 다음 일곱 명제는 모두 동치이다. 어느 하나가 참이면 나머지도 모두 참이다.

① A ⊆ B
② B^c ⊆ A^c
③ A ∪ B = B
④ A ∩ B = A
⑤ A^c ∪ B = U
⑥ A ∩ B^c = ∅
⑦ A − B = ∅

특히 A ⊆ B이면 A의 원소 중 B 밖에 있는 것이 없으므로 A − B = ∅이고, A와 B를 합쳐도 B에 새 원소가 더해지지 않아 A ∪ B = B이다. 또한 여집합을 취하면 포함 방향이 뒤집혀 B^c ⊆ A^c가 된다.

핵심 개념 정리

• 집합은 중괄호로 나타내며 원소나열법과 조건제시법을 사용할 수 있다. 원소의 순서와 중복은 집합을 바꾸지 않는다.
• A ⊆ B는 A의 모든 원소가 B에 속한다는 뜻이다. A = B는 양방향 포함으로 판정한다.
• 분할은 비어 있지 않고 서로 겹치지 않는 부분집합들이 원래 집합을 빠짐없이 덮는 것이다.
• 멱집합 P(A)는 A의 모든 부분집합의 집합이며 |A| = n이면 |P(A)| = 2ⁿ이다.
• 합집합은 논리합, 교집합은 논리곱에 대응한다. 대칭차집합은 두 집합 중 정확히 한쪽에만 속하는 원소의 집합이다.
• 두 유한집합에 대해 |A ∪ B| = |A| + |B| − |A ∩ B|가 성립한다.
• 집합 항등식에는 교환·결합·분배·항등·보수·이중보수·멱등·전체한계·드모르간·흡수·차집합 법칙이 있다.

집합론 문제의 핵심은 기호를 정확히 해석하는 데 있다. 원소 관계 ∈와 포함 관계 ⊆를 구별하고, 분할에서는 ‘공집합 제외·전체를 덮음·서로 겹치지 않음’을 동시에 확인한다. 복잡한 집합식은 원소 하나가 각 집합에 속하는지 논리식으로 바꾸거나, 항등식과 포함관계의 동치 조건을 적용하면 체계적으로 해결할 수 있다.

예상문제 20선

1. 집합 A = {1, 2, 2, 3}의 크기 |A|는 얼마인가?

① 2 ② 3 ③ 4 ④ 5

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
집합에서는 중복된 원소를 한 번만 센다. 따라서 A = {1, 2, 3}과 같고 크기는 3이다.

2. 집합 A = {a, b}에 대한 설명으로 옳은 것은?

① a ⊆ A ② {a} ∈ A ③ A ∈ a ④ {a} ⊆ A

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
{a}의 유일한 원소 a가 A에 속하므로 {a}는 A의 부분집합이다. a는 집합이 아니라 A의 원소이므로 a ∈ A라고 써야 한다.

3. A가 B의 진부분집합이기 위한 조건은?

① A ⊆ B이고 A ≠ B ② B ⊆ A이고 A = B ③ A ∩ B = ∅ ④ A ∪ B = A이고 A = B

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
진부분집합은 A의 모든 원소가 B에 속하면서 두 집합이 같지는 않은 경우이다.

4. 세 집합 A₁, A₂, A₃이 쌍으로 서로소라는 뜻은?

① 세 집합의 합집합이 공집합이다. ② 세 집합의 전체 교집합만 공집합이다. ③ 서로 다른 모든 두 집합의 교집합이 공집합이다. ④ 세 집합의 원소 수가 모두 같다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
쌍으로 서로소는 서로 다른 임의의 두 집합을 골랐을 때 그 교집합이 항상 공집합이라는 뜻이다.

5. A = {1, 2, 3}의 분할이 아닌 것은?

① {{1}, {2}, {3}} ② {{1, 2}, {2, 3}} ③ {{1, 2}, {3}} ④ {{1, 2, 3}}

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
두 블록 {1, 2}와 {2, 3}은 원소 2를 함께 포함하여 서로소가 아니므로 분할이 될 수 없다.

6. |S| = 4일 때 멱집합 P(S)의 원소 수는?

① 16 ② 8 ③ 4 ④ 24

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
원소가 n개인 집합의 부분집합 수는 2ⁿ이므로 |P(S)| = 2⁴ = 16이다.

7. U = {1, 2, 3, 4, 5}, A = {1, 2, 3}일 때 A^c는?

① {1, 2, 3} ② {1, 2, 3, 4, 5} ③ {1, 2} ④ {4, 5}

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
A의 여집합은 전체집합 U에서 A의 원소를 제외한 집합이므로 {4, 5}이다.

8. A = {1, 2, 3}, B = {2, 3, 4}일 때 A ⊕ B는?

① {2, 3} ② {1, 2, 3, 4} ③ {1, 4} ④ ∅

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
대칭차집합은 두 집합 중 정확히 한쪽에만 속하는 원소의 집합이다. 공통 원소 2와 3을 제외하면 {1, 4}가 남는다.

9. A = {a, b}, B = {1, 2, 3}일 때 |A × B|는?

① 6 ② 5 ③ 3 ④ 2

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
각 A의 원소마다 B의 원소 3개와 순서쌍을 만들므로 |A × B| = |A||B| = 2 × 3 = 6이다.

10. |A| = 12, |B| = 9, |A ∩ B| = 4일 때 |A ∪ B|는?

① 21 ② 25 ③ 8 ④ 17

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
|A ∪ B| = |A| + |B| − |A ∩ B|에 대입하면 12 + 9 − 4 = 17이다.

11. 유한집합 A와 B가 서로소이고 |A| = 7, |B| = 5일 때 |A ∪ B|는?

① 2 ② 12 ③ 35 ④ 7

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
서로소인 두 집합은 교집합의 크기가 0이므로 합집합의 크기는 7 + 5 = 12이다.

12. 세 유한집합의 합집합 크기를 구하는 공식에서 마지막에 더하는 항은?

① |A ∪ B ∪ C| ② |A ∩ B| ③ |A ∩ B ∩ C| ④ |A × B × C|

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
각 집합의 크기를 더하고 두 집합씩의 교집합을 뺀 다음, 지나치게 빠진 세 집합의 교집합 크기를 다시 더한다.

13. 드모르간의 법칙을 올바르게 나타낸 것은?

① (A ∪ B)^c = A^c ∪ B^c ② (A ∩ B)^c = A^c ∩ B^c ③ (A ∪ B)^c = A ∩ B ④ (A ∩ B)^c = A^c ∪ B^c

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
교집합의 여집합은 각 집합의 여집합을 합한 것과 같다. 여집합을 괄호 안으로 옮길 때 ∩과 ∪가 바뀐다.

14. 흡수법칙에 해당하는 식은?

① A ∪ ∅ = A ② A ∪ (A ∩ B) = A ③ A ∪ B = B ∪ A ④ A ∩ A^c = ∅

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
A에 A의 일부인 A ∩ B를 합해도 A 그대로이므로 흡수법칙이다.

15. 차집합법칙에 따라 A − B와 같은 것은?

① A ∩ B^c ② A^c ∩ B ③ A ∪ B^c ④ A^c ∪ B

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
A − B는 A에 속하면서 B에는 속하지 않는 원소의 집합이므로 A ∩ B^c이다.

16. A ⊆ B일 때 반드시 성립하는 것은?

① A ∩ B = B ② A ∪ B = A ③ A − B = ∅ ④ B − A = ∅

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
A의 모든 원소가 B에 속하므로 A에는 속하지만 B에는 속하지 않는 원소가 없다. 따라서 A − B = ∅이다.

17. 집합의 상등 A = B를 원소 논증으로 증명하는 일반적인 방법은?

① A ∩ B = ∅만 보인다. ② A ⊆ B와 B ⊆ A를 모두 보인다. ③ |A| = |B|만 보인다. ④ A ∪ B = U만 보인다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
두 집합이 같음을 보이려면 양방향 포함, 즉 A의 모든 원소가 B에 속하고 B의 모든 원소가 A에 속함을 각각 증명한다.

18. 다음 중 분배법칙은?

① A ∩ U = A ② A ∪ A = A ③ (A^c)^c = A ④ A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
교집합은 합집합에 대해 분배되며, A ∩ (B ∪ C)를 두 교집합의 합집합으로 전개할 수 있다.

19. A ⊆ B와 동치가 아닌 것은?

① A ∪ B = B ② A ∩ B = A ③ B − A = ∅ ④ B^c ⊆ A^c

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
A ⊆ B일 때 비어 있는 차집합은 A − B이다. B − A = ∅은 오히려 B ⊆ A를 뜻하므로 일반적으로 성립하지 않는다.

20. 전체집합 U에 대한 설명으로 옳은 것은?

① U^c = ∅ ② A ∩ U = U ③ A ∪ U = A ④ ∅^c = ∅

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
전체집합 U 밖의 원소는 없으므로 U의 여집합은 공집합이다. 반대로 공집합의 여집합은 U이다.