📂집합론

드 모르간의 법칙 증명

정리 ¹

• [1] 드 모르간의 법칙: $$ \lnot (p \land q) \iff \lnot p \lor \lnot q \\ \lnot(p \lor q) \iff \lnot p \land \lnot q $$
• [2] 드 모르간의 정리: $$ (A \cup B)^{c} = A^{c} \cap B^{c} \\ (A \cap B)^{c} = A^{c} \cup B^{c} $$

설명

드 모르간의 법칙와 드 모르간의 정리는 각각 명제, 집합에 대한 정리지만 실제로 말을 하면서는 별로 구분하지 않는다. 법칙이든 정리든 드 모르간- 만 붙으면 부정이나 여집합을 취하면 괄호 안의 명제, 집합과 기호가 ‘뒤집히는’ 모양새라고 알아듣기 때문이다.

한편 수학적 귀납법에 따라 다음과 같은 일반화는 물론, 인덱스 패밀리까지 확장이 가능하다. $$ \begin{align*} \begin{matrix} \displaystyle \left( \bigcup_{i=1}^{\infty} X_{i} \right)^{c} = \bigcap_{i=1}^{\infty} (X_{i})^{c} \\ \displaystyle \left( \bigcap_{i=1}^{\infty} X_{i} \right)^{c} = \bigcup_{i=1}^{\infty} (X_{i})^{c} \end{matrix} &\qquad \& \begin{matrix} \displaystyle\left( \bigcup_{\alpha \in \forall } X_{\alpha} \right)^{c} = \bigcap_{\alpha \in \forall} (X_{\alpha})^{c} \\ \displaystyle \left( \bigcap_{\alpha \in \forall} X_{\alpha} \right)^{c} = \bigcup_{\alpha \in \forall } (X_{\alpha})^{c} \end{matrix} \end{align*} $$

증명

[1]

진리표로 증명한다.

Part 1. $\lnot (p \land q) \iff \lnot p \lor \lnot q$

---

Part 2. $\lnot(p \lor q) \iff \lnot p \land \lnot q$

■

[2]

Part 1. $(A \cup B)^{c} = A^{c} \cap B^{c}$

$$\begin{align*} x \in (A \cup B)^{c} \iff & \lnot (x \in A \cup B) \\ \iff & \lnot ( x \in A \lor x \in B ) \\ \iff & \lnot ( x \in A ) \land \lnot ( x \in B ) \\ \iff & x \in A^{c} \land x \in B^{c} \\ \iff & x \in ( A^{c} \cap B^{c} ) \end{align*} $$

---

Part 2. $(A \cap B)^{c} = A^{c} \cup B^{c}$

$$\begin{align*} x \in (A \cap B)^{c} \iff & \lnot (x \in A \cap B) \\ \iff & \lnot ( x \in A \land x \in B ) \\ \iff & \lnot ( x \in A ) \lor \lnot ( x \in B ) \\ \iff & x \in A^{c} \lor x \in B^{c} \\ \iff & x \in ( A^{c} \cup B^{c} ) \end{align*} $$

■