ド・モルガンの法則
ド・モルガンの法則（ド・モルガンのほうそく、テンプレート:Lang-en-short）とは、数理論理学や集合論において、論理積（集合の積、共通部分）と論理和（集合の和、合併）、否定（補集合）の間に成り立つ関係を記述する定理であり、数学者のオーガスタス・ド・モルガンにちなんでこの名前がついている。
この関係性は、真・偽を反転させ、論理和・論理積の定義を交換した論理体系が元の論理体系と同一視できることを指しているので、ド・モルガンの双対性（テンプレート:Lang-en-short）とよばれることもある。
概要
論理和<math>\lor</math>、論理積<math>\land</math>、否定<math>\neg</math>の論理記号を使って記述すると、このように表現できる。
- <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) == !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>\forall, \exists</math>を使って書くと
- <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)」の否定、「好きな本はない」ということになる。
