ド・モルガンの法則

ド・モルガンの法則（ド・モルガンのほうそく、De Morgan の法則）は、ブール論理や集合の代数学において、論理和と論理積と否定（集合のことばでは、共通部分と合併と補集合）の間に成り立つ規則性である。名前は数学者オーガスタス・ド・モルガン（1806–1871）にちなむ。

この関係性は（論理のことばで言うと）「真と偽を入替え、論理和を論理積を入替えた論理体系」は、元の論理体系と同一視できる、ということであるので、ド・モルガンの双対性（英: De Morgan's duality）と呼ばれることもある。

概要

形式体系に依り、定理であることが多いが、公理として要請される場合もある（詳細は後述: 例として、#ド・モルガンの法則と無限）。

一般的な論理の体系、一例としては古典論理などで、命題PとQがあって、演算子が、論理和 ∨、論理積 ∧、否定 ￢ とすると、以下となる。

[math]\neg (P \lor Q) = \neg P \land \neg Q[/math]

[math]\neg (P \land Q) = \neg P \lor \neg Q[/math]

C言語など、いくつかのプログラミング言語が採用している演算子を使うと、

!(P || Q) == !P && !Q

!(P && Q) == !P || !Q

（一般的な論理演算に従う対象ならば）以上のいずれの式も評価結果は常に必ず真となる、ということである。

同様に、一般的な集合代数では、

[math]\overline{(A\cap B)}=\overline{A}\cup \overline{B}[/math]

[math]\overline{(A\cup B)}=\overline{A}\cap \overline{B}[/math]

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

• Venn-Diagram-OR.png

  論理和 (OR) [math]P \lor Q[/math]または[math]P\cup Q[/math]

• Venn-Diagram-NOR.png

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

• Venn-Diagram-NOT-P.png

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

• Venn-Diagram-NOT-Q.png

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

• Venn-Diagram-NOR.png

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

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

例

「私の身長は 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 に対し〜」を表す記号 ∀, ∃ を使って書くと

• [math]\neg\forall x~A(x) \Leftrightarrow \exists x~\neg A(x)[/math]
• [math]\neg\exists x~A(x) \Leftrightarrow \forall x~\neg A(x)[/math]

となる。

具体例を挙げると、

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

などである。また、後述するように部分否定や全否定の言い換えも述語論理におけるド・モルガンの法則を表現していると考えられる。

命題論理におけるド・モルガンの法則から、以下のようにして述語論理に拡張されたド・モルガンの法則を確かめられる（次節に注意）。

x が 1 から 100 までの数を表す変数だとする。このとき「全ての x に対し A(x)」は、「A(1) かつ A(2) かつ …… かつ A(100)」を意味する。これの否定は、命題論理のド・モルガンの法則から

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

となり、さらに「A(2) かつ A(3) かつ …… 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)」と表せ、ド・モルガンの法則によって「ある x に対し A(x)」の否定、「好きな本はない」ということになる。

参考文献

• 西岡康夫 『数学チュートリアル やさしく語る 確率統計』 オーム社、2013年。ISBN 9784274214073。

関連項目

• 負論理

外部リンク

• Weisstein, Eric W. “de Morgan's Laws”. MathWorld（英語）.
• Weisstein, Eric W. “de Morgan's Duality Law”. MathWorld（英語）.