ド・モルガンの法則

出典: フリー百科事典『ウィキペディア（Wikipedia）』

ド・モルガンの法則（ド・モルガンのほうそく）とは、数理論理学や集合論において、論理積（集合の共通分）と論理和（集合の合併）、否定（補集合）操作の間の関係性（ド・モルガンの双対性とよばれる）を記述する定理であり、数学者のオーガスタス・ド・モルガンにちなんでこの名前がついている。

概要

論理和 $\lor$ 、論理積 $\land$ 、否定 $\neg$ の論理記号を使って記述すると、このように表現できる。

$\neg (P \lor Q) = \neg P \land \neg Q$

$\neg (P \land Q) = \neg P \lor \neg Q$

同じことを集合の言葉を用いて言い換えると、

$\overline{(A\cap B)}=\overline{A}\cup \overline{B}$

$\overline{(A\cup B)}=\overline{A}\cap \overline{B}$

となる（ただし、￣は全体集合に対する補集合を表している）。ベン図を用いると、 $\neg (P \lor Q) \equiv \neg P \land \neg Q$ を次のように表現できる：

論理和 (OR) $P \lor Q$ または $P\cup Q$

論理和の否定 $\neg (P \lor Q)$ または $\overline{(P\cup Q)}$

片方の論理否定 (NOT-P) $\neg P$ または $\overline{P}$

もう片方の論理否定 (NOT-Q) $\neg Q$ または $\overline{Q}$

二つの否定の論理積 $\neg P \land \neg Q$ または $\overline{P} \cap \overline{Q}$

ここでは二つの命題や集合について法則を述べたが、もっと多くのものについても同様の法則が成り立つ。差集合の記事を参照。

例

「私の身長は 160 cm 以上であり、かつ私の体重は 50 kg 以上」である

の否定

「私の身長は 160 cm 以上であり、かつ私の体重は 50 kg 以上」ではない

が、次の命題と等しいことを、ド・モルガンの法則は主張している。

「私の身長は 160 cm 未満であるか、または私の体重は 50 kg 未満」である

同じようにして

「このボールは青いか、または赤い」

の否定は

「このボールは青くもないし赤くもない」

になる。

述語論理におけるド・モルガンの法則

上のド・モルガンの法則の拡張として、一階の述語論理におけるド・モルガンの法則がある：A(x) を変数 x についての言明とすると

「全てのxに対しA(x)」の否定は「あるxが存在して￢A(x)」
「あるxが存在してA(x)」の否定は「全てのxに対し￢A(x)」

具体例を挙げると、

「全ての人が冷蔵庫を持っている」の否定は「ある人は冷蔵庫を持っていない」（すなわち、「冷蔵庫を持っていない人が少なくとも一人いる」）
「ある人が冷蔵庫を持っている」（すなわち、「冷蔵庫を持っている人が少なくとも一人いる」）の否定は「全ての人が、冷蔵庫を持っていない」（すなわち、「誰ひとりとして冷蔵庫を持っていない」）

「全てのxに対し〜」や「あるxに対し〜」を表す量化子記号 $\forall x, \exists x$ を使うと、述語論理におけるド・モルガンの法則は次のように書ける：

$\neg\forall x~A(x) \Leftrightarrow \exists x~\neg A(x)$
$\neg\exists x~A(x) \Leftrightarrow \forall x~\neg A(x)$

命題論理におけるド・モルガンの法則を認めれば以下のようにして述語論理版のド・モルガンの法則を確かめることができる。

今xが1から100までの数を表す変数だとする。このとき「全てのxに対しA(x)」であるとは、「A(1)かつA(2)かつ… A(100)」を意味する。これを否定すると

￢A(1)または￢「A(2)かつ... A(100)」

となり、「A(2)かつ… A(100)」の否定について同様の操作を行い、これを続ければ「￢A(1)または￢A(2)または… ￢A(100)」がえられる。これは「あるxに対し￢A(x)」を意味している。また逆に、「あるxに対しA(x)」は「A(1)またはA(2)または… A(100)」ということだが、これの否定は

￢A(1)かつ￢「A(2)または... A(100)」

であり、これをつづけて「全てのxに対し￢A(x)」をが得られる。

ド・モルガンの法則と無限

上述の、述語論理におけるド・モルガンの法則の確認に際し「全てのxに対しA(x)」を「A(1)かつA(2)かつ…A(100)」に置き換える議論を行ったが、このような操作ができるのは、変数xの選択肢が有限個の場合だけである。xの表すものが無限にある場合、この方法では有限回の手続きでド・モルガンの法則を導くことができない。普通の述語論理の体系では無限個の選択肢がある場合についてのド・モルガンの法則にあたるものを公理として要請するが、記号論理学者の中にはこれを認めない場合に対する論理学を研究しているものもいる。

全否定と部分否定

全否定や部分否定をどう言い換えるかという問題は（述語論理における）ド・モルガンの法則に関係する。例えばx が本を表す変数だとして、「本xが好きだ」という言明をA(x)と書くことにすると、「全ての本が好きだ」は「全てのxに対しA(x)」となる。

これの部分否定「すべての本を好きだというわけではない」は「全てのxに対しA(x)」の否定であり、ド・モルガンの法則によってこれは「あるxに対し￢A(x)」、すなわち「好きでない本もある」となる。他方、全否定「すべての本が嫌いだ」は「全てのxに対し￢A(x)」を指し、ド・モルガンの法則によってこれは『ある本を好きだ』の否定だということになる。