현대 수학의 모든 대상(수, 함수, 공간)은 집합으로 정의된다. 집합의 연산과 그 법칙은 논리 연산과 정확히 대응한다: 합집합은 ‘또는’, 교집합은 ‘그리고’, 여집합은 ‘부정’이다.
핵심 개념
- $A\cup B=\{x: x\in A\lor x\in B\}$, $A\cap B=\{x: x\in A\land x\in B\}$
- 여집합 $A^c=\{x\in U: x\notin A\}$, 차집합 $A\setminus B=A\cap B^c$
- 곱집합 $A\times B=\{(a,b): a\in A,\ b\in B\}$
- 멱집합 $\mathcal P(A)$: $A$의 모든 부분집합의 집합. $|A|=n$이면 $|\mathcal P(A)|=2^n$
- 두 집합이 같다 $\iff A\subset B$이고 $B\subset A$
핵심 정리
- 드모르간 법칙: $(A\cup B)^c=A^c\cap B^c$, $(A\cap B)^c=A^c\cup B^c$
- 분배법칙: $A\cap(B\cup C)=(A\cap B)\cup(A\cap C)$
증명 보기
집합의 상등은 ‘양쪽이 서로의 부분집합’임을 보여 증명한다. 원소 $x$를 잡아 논리로 바꾸면 된다.
드모르간. $x\in(A\cup B)^c\iff\lnot(x\in A\lor x\in B)\iff(x\notin A)\land(x\notin B)\iff x\in A^c\cap B^c$이다. 논리의 드모르간 법칙을 그대로 쓴 것이다.
분배법칙. $x\in A\cap(B\cup C)\iff x\in A\land(x\in B\lor x\in C)\iff(x\in A\land x\in B)\lor(x\in A\land x\in C)\iff x\in(A\cap B)\cup(A\cap C)$이다. 가운데 단계는 논리의 분배법칙이며 진리표로 확인할 수 있다. $\blacksquare$
예제
- $U=\{1,\dots,10\}$, $A=\{$짝수$\}$, $B=\{$3의 배수$\}$: $A\cap B=\{6\}$, $(A\cup B)^c=\{1,5,7\}$
- $\{1,2\}\times\{a,b\}=\{(1,a),(1,b),(2,a),(2,b)\}$
확인 문제
$A\setminus(B\cup C)=(A\setminus B)\cap(A\setminus C)$임을 보이시오.
풀이 보기
$A\setminus(B\cup C)=A\cap(B\cup C)^c=A\cap(B^c\cap C^c)=(A\cap B^c)\cap(A\cap C^c)=(A\setminus B)\cap(A\setminus C)$이다. 드모르간 법칙과 교집합의 결합·교환법칙을 썼다.
정리
- 집합 연산 ↔ 논리 연산 (∪=또는, ∩=그리고, ᶜ=부정)
- 집합의 상등은 양쪽 포함으로 증명한다.
