📂集合論

ド・モルガンの法則の証明

定理 ¹

• [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]

真理表で証明する。

パート1. $\lnot (p \land q) \iff \lnot p \lor \lnot q$

---

パート2. $\lnot(p \lor q) \iff \lnot p \land \lnot q$

■

[2]

パート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*} $$

---

パート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*} $$

■