ド・モルガンの法則の証明
ド・モルガンの法則を証明してみよう。
命題（ド・モルガンの法則）
集合 $A$ と $B$ について,
$\overline{A \cap B} = \overline{A} \cup \overline{B}$
$\overline{A \cup B} = \overline{A} \cap \overline{B}$
が成り立つ.
証明.
全体集合を $U$ とする.
■ $\overline{A \cap B} = \overline{A} \cup \overline{B}$ を証明する.
$\overline{A \cap B}$ $=$ $\overline{A} \cup \overline{B}$ $\Longleftrightarrow$ $\overline{A \cap B}$ $\subset \overline{A} \cup \overline{B}$ かつ $\overline{A} \cup \overline{B}$ $\subset \overline{A \cap B}$
$x \in \overline{A \cap B}$ をとる.
$\Leftrightarrow$ $x \in U$ かつ $x \not\in A \cap B$
$\Leftrightarrow$ $x \in U$ かつ ($x \not\in A$ または $ x \not \in B$ )
$\Leftrightarrow$ ( $x \in U$ かつ $x \not\in A$ ) または ( $x \in U$ かつ $ x \not \in B$ )
$\Leftrightarrow$ $x \in \overline{A}$ または $x \in \overline{B}$
$\Leftrightarrow$ $x \in \overline{A} \cup \overline{B}$
以上から,
$\overline{A \cap B}$ $\subset \overline{A} \cup \overline{B}$ かつ $\overline{A} \cup \overline{B}$ $\subset \overline{A \cap B}$
である.
ゆえに, $\overline{A \cap B}$ $=$ $\overline{A} \cup \overline{B}$ が成り立つ.
■ $\overline{A \cup B} = \overline{A} \cap \overline{B}$ を証明する.
さきほど証明した等式 $\overline{A \cap B}$ $=$ $\overline{A} \cup \overline{B}$ について, $A$ を $\overline{A}$, $B$ を $\overline{B}$ に置き換えると,
$\overline{\overline{A} \cap \overline{B}}$ $=$ $\overline{\overline{A}} \cup \overline{\overline{B}}$
$\Leftrightarrow$ $\overline{\overline{A} \cap \overline{B}}$ $=$ $A \cup B$
を得る. この等式の両辺のそれぞれの補集合を考えると,
$\overline{A} \cap \overline{B}$ $=\overline{A \cup B}$
となる.
ゆえに, $\overline{A \cup B}$ $=\overline{A} \cap \overline{B}$ が成り立つ.
たとえば,
$A=\{1, 2\}$
$B=\{2,3\}$,
全体集合 $U=\{1, 2, 3, 4\}$ の場合,
$\overline{A \cap B}$ $=\{1,3,4\}$,
$\overline{A \cup B}$ $=\{4\}$,
$\overline{A} \cup \overline{B}$ $=\{1,3,4\}$
$\overline{A} \cap \overline{B}$ $=\{4\}$
になります。
