ド・モルガンの法則
イギリス人、オーガスタス・ド・モルガン。ド・モルガンの法則を命題論理の法則として厳密な形で表した人物。数学的帰納法の定式化にも貢献した。 Augustus De Morgan（1806 - 1871）
ド・モルガンの法則
命題論理のド・モルガンの法則
定理（ド・モルガンの法則）
$P,Q$ を命題とするとき、次のことが成り立ちます。
（1）$\lnot (P\lor Q)\leftrightarrow( (\lnot P) \land (\lnot Q) )$
（2）$\lnot (P\land Q)\leftrightarrow( (\lnot P) \lor (\lnot Q) )$
証明
次の真理値表によります。
（1）
| $ P$ | $ \lnot P$ | $ Q$ | $ \lnot Q$ | $ P\lor Q$ | $ \lnot (P\lor Q)$ | $ (\lnot P) \land (\lnot Q)$ |
|---|---|---|---|---|---|---|
| T | F | T | F | T | F | F |
| T | F | F | T | T | F | F |
| F | T | T | F | T | F | F |
| F | T | F | T | F | T | T |
（2）
| $ P$ | $ \lnot P$ | $ Q$ | $ \lnot Q$ | $ P\land Q$ | $ \lnot (P\land Q)$ | $ (\lnot P) \lor (\lnot Q)$ |
|---|---|---|---|---|---|---|
| T | F | T | F | T | F | F |
| T | F | F | T | F | T | T |
| F | T | T | F | F | T | T |
| F | T | F | T | T | F | F |
通常「ド・モルガンの法則」といえば集合論のド・モルガンの法則がイメージされることが多いですが、こちらがオリジナルのド・モルガンの法則です。
述語論理のド・モルガンの法則
述語論理においてド・モルガンの法則に相当するのは、
（1）$(\lnot(\forall xP(x)))\leftrightarrow(\exists x(\lnot P(x)))$
（2）$(\lnot(\exists xP(x)))\leftrightarrow(\forall x(\lnot P(x)))$
ですが、 述語論理とは - 述語論理のド・モルガンの法則 に書いたように、このことは変数 $ x$ の取りうる値の可能性が無限個の場合には証明ができないので、述語論理における公理となっています。
集合論のド・モルガンの法則
定理（集合論のド・モルガンの法則）
$ A,B$ を、全体集合 $ U$をもつ集合とします。また、任意の部分集合 $ X\subset U$ に対し、$ U-X$ を $\overline{X}$ と表します。このとき、次が成り立ちます。
（1）$ \overline{A\cup B}=\overline{A}\cap \overline{B}$
（2）$\overline{A\cap B}=\overline{A}\cup \overline{B}$
証明
（1）
1：$ x\in \overline{A\cup B}$ $\Leftrightarrow$ $ \lnot(x\in A\cup B)$
2：$ \lnot(x\in A\cup B)$ $\Leftrightarrow$ $ \lnot( (x\in A)\lor (x\in B) )$
3：$ \lnot( (x\in A)\lor (x\in B) )$ $\Leftrightarrow$ $ \lnot (x\in A)\land \lnot (x\in B)$
4：$ \lnot (x\in A)\land \lnot (x\in B)$ $\Leftrightarrow$ $ x\in \overline{A}\cap \overline{B}$
2 は $\cup$ の定義、3 は命題論理のド・モルガンの法則によります。
（2）
1：$ x\in \overline{A\cap B}$ $\Leftrightarrow$ $ \lnot(x\in A\cap B)$
2：$ \lnot(x\in A\cap B)$ $\Leftrightarrow$ $ \lnot( (x\in A)\land (x\in B) )$
3：$ \lnot( (x\in A)\land (x\in B) )$ $\Leftrightarrow$ $ \lnot (x\in A)\lor \lnot (x\in B)$
4：$ \lnot (x\in A)\lor \lnot (x\in B)$ $\Leftrightarrow$ $ x\in \overline{A}\cup \overline{B}$
2 は $\cap$ の定義、3 は命題論理のド・モルガンの法則によります。
