ホーム >> 集合・論理 >> ド・モルガンの法則

集合に関する基本的な定理である,ド・モルガンの法則について解説します.




ド・モルガンの法則とは

一般に集合について考えるとき,$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$ の場合とほとんど同様にして示す事ができます.