집합의 연산

현대 수학의 모든 대상(수, 함수, 공간)은 집합으로 정의된다. 집합의 연산과 그 법칙은 논리 연산과 정확히 대응한다: 합집합은 ‘또는’, 교집합은 ‘그리고’, 여집합은 ‘부정’이다.

핵심 개념

  • $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와 B 바깥 부분을 칠한 벤 다이어그램
$(A\cup B)^c=A^c\cap B^c$

핵심 정리

  • 드모르간 법칙: $(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)$이다. 드모르간 법칙과 교집합의 결합·교환법칙을 썼다.

정리

  • 집합 연산 ↔ 논리 연산 (∪=또는, ∩=그리고, ᶜ=부정)
  • 집합의 상등은 양쪽 포함으로 증명한다.
알림: 보호된 콘텐츠입니다.