集合に関する基本的な定理である，ド・モルガンの法則について解説します．
一般に集合について考えるとき，$1$ つの集合 $X$ を決めて (ひとつ固定しておいて)，その部分集合について議論することが多いです．この $X$ を全体集合と呼びます．$X$ の部分集合 $A$ に対して，$X$ の要素で，$A$ に属さない要素全体の集合を $A$ の補集合 といい，$A^c$ で表します．($\bar{A}$ で表すこともあります)
ド・モルガンの法則の最も基本的なタイプが次の命題です．
ド・モルガンの法則： $X$ を全体集合，$A,B$ を $X$ の部分集合とする．このとき，つぎの等式が成り立つ． $$\large (1) (A \cup B)^c=A^c \cap B^c$$ $$\large (2) (A \cap B)^c=A^c \cup B^c$$
例
$X=\{1,2,3,4,5,6,7,8,9,10\}$ を全体集合，$A=\{2,4,6,8,10\},B=\{1,3,6,9\}$ とします． ド・モルガンの法則 (の $(1)$) が成り立つことを確かめるために，$(A \cup B)^c$ と $A^c \cap B^c$ を計算してみましょう． $A\cup B=\{1,2,3,4,6,8,9,10\}$ なので， $$(A \cup B)^c=\{5,7\}$$ となります． 一方，$A^c=\{1,3,5,7,9\},B^c=\{2,4,5,7,8,10\}$ なので， $$A^c \cap B^c =\{5,7\}$$ となります．したがって，確かに $$(A \cup B)^c=A^c \cap B^c$$ が成り立っています．
上の例について，($2$) も成り立っているを確認してみてください．
ド・モルガンの法則は，集合同士の等式の形をしています．一般に，集合 $X,Y$ に対して，$X=Y$ を証明するためには，$X \subseteq Y$ と $X \supseteq Y$ の両方が成り立つことを示せばよいです．つまり，$X$ の要素 $x$ が $Y$ の要素でもあることと，$Y$ の要素 $y$ が $X$ の要素でもあることを示します．
証明： (1) $(A \cup B)^c \subseteq A^c \cap B^c$ かつ $ (A \cup B)^c \supseteq A^c \cap B^c$ を示せばよい． $\underline{(A \cup B)^c \subseteq A^c \cap B^c}$ $x \in (A \cup B)^c$ とすると，$x \notin (A \cup B)$ ．これは，$x$ は $A$ にも $B$ にも属していないということなので， $$x \notin A\ \text{かつ} \ x \notin B$$ となる．これより， $x \in A^c \ \text{かつ}\ x \in B^c$ となり， $$x \in A^c \cap B^c$$ が従う． $\underline{(A \cup B)^c \supseteq A^c \cap B^c}$ $x\in A^c \cap B^c$ とすると，$x \in A^c \ \text{かつ}\ x \in B^c$ である．これより， $$x \notin A \ \text{かつ}\ x\notin B$$ となり，$x \notin (A \cup B)$ となるから， $$x \in (A \cup B)^c$$ が従う．
(2) (1) とほとんど一緒なので省略．
ベン図による理解
直感的には，ベン図を用いて理解することができます．$X$ を全体集合，$A,B$ を $X$ の部分集合とするとき，この一般的な状況は，下のベン図によって表すことができます．
このとき，$A^c,B^c,A\cup B, A\cap B$ はそれぞれ下の色のついた部分に対応します．
$(1)$ の等式 $(A \cup B)^c=A^c \cap B^c$ が成り立つことを確認しましょう． まず，$(A \cup B)^c$ は下の色のついた部分に対応します．
つぎに，$A^c \cap B^c$ は $A^c$ と $B^c$ の両方ともに色が塗られている部分に対応します．
したがって，$(A \cup B)^c$ と $A^c \cap B^c$ のベン図をくらべると，両者は一致することがわかります．
同様にして，$(2)$ が成り立つ事も確認できます．(ぜひ確認してみてください)
先に紹介したド・モルガンの法則は，$A$ と $B$ という二つの集合に関してのものでしたが，実はド・モルガンの法則は $2$ つだけではなく，いくらでも多くの集合に対して成り立ちます．
ド・モルガンの法則： $n$ を自然数とする．$X$ を全体集合，$A_1,…,A_n$ を $X$ の部分集合とする．このとき，次の等式が成り立つ． $$\large (1) (A_1\cup A_2 \cup \cdots \cup A_n)^c=A_1^c \cap A_2^c \cap \cdots \cap A_n^c$$ $$\large (2) (A_1\cap A_2 \cap \cdots \cap A_n)^c=A_1^c \cup A_2^c \cup \cdots \cup A_n^c$$
証明は，$n=2$ の場合とほとんど同様にして示す事ができます．
