ド・モルガンの法則
イギリス人、オーガスタス・ド・モルガン。ド・モルガンの法則を命題論理の法則として厳密な形で表した人物。数学的帰納法の定式化にも貢献した。
ド・モルガンの法則
命題論理のド・モルガンの法則
定理(ド・モルガンの法則)
$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 は命題論理のド・モルガンの法則によります。