ド・モルガンの法則
ド・モルガンの法則(ド・モルガンのほうそく、De Morgan's laws)は、ブール論理や集合の代数学において、論理和と論理積と否定(集合のことばでは、合併と共通部分と補集合)の間に成り立つ規則性である。名前は数学者オーガスタス・ド・モルガン(Augustus de Morgan, 1806–1871)にちなむ。
この規則性(論理のことばで言うと「真と偽を入れ替え、論理和と論理積を入れ替えた論理体系」)は、元の論理体系と同一視できる、ということであるので、ド・モルガンの双対性(英: De Morgan's duality)と呼ばれることもある。
概要編集
形式体系に依り、定理であることが多いが、公理として要請される場合もある(詳細は後述: 例として、#ド・モルガンの法則と無限)。
一般的な論理の体系、一例としては古典論理などで、命題PとQがあって、演算子が、論理和 ∨、論理積 ∧、否定 ¬ とすると、以下となる。
C言語など、いくつかのプログラミング言語が採用している演算子を使うと、
!(P || Q) == !P && !Q
!(P && Q) == !P || !Q
(一般的な論理演算に従う対象ならば)以上のいずれの式も評価結果は常に必ず真となる、ということである。
同様に、一般的な集合代数では、
となる(ただし、 ̄は全体集合に対する補集合を表している)。ベン図を用いると、 を次のように表現できる:
ここでは二つの命題や集合について法則を述べたが、もっと多くのものについても同様の法則が成り立つ。差集合の記事を参照。
例編集
次の命題
- 「私の身長は160cm以上であり、かつ私の体重は50kg以上である」
の否定、すなわち
- 「「私の身長は160cm以上であり、かつ私の体重は50kg以上である」ではない」
は、ド・モルガンの法則によれば、次の命題と等しい。
- 「私の身長は160cm未満である、または私の体重は50kg未満である」
同じようにして
- 「このボールは青いか、または赤い」
の否定は
- 「このボールは青くなく、かつ赤くない」
になる。
述語論理におけるド・モルガンの法則編集
上のド・モルガンの法則は、一階述語論理にも拡張できる。
A(x) を変数 x についての言明とすると
- 「全ての x に対し A(x)」の否定は「ある x が存在して ¬A(x)」
- 「ある x が存在して A(x)」の否定は「全ての x に対し ¬A(x)」
と表現できる。
「全ての x に対し〜」、「ある x に対し〜」を表す記号 ∀, ∃ を使って書くと
となる。
具体例を挙げると、
- 「全ての人が冷蔵庫を持っている」の否定は「ある人は冷蔵庫を持っていない」(すなわち、「冷蔵庫を持っていない人が少なくとも一人いる」)
- 「ある人が冷蔵庫を持っている」(すなわち、「冷蔵庫を持っている人が少なくとも一人いる」)の否定は「全ての人が冷蔵庫を持っていない」(すなわち、「誰ひとりとして冷蔵庫を持っていない」)
などである。また、後述するように部分否定や全否定の言い換えも述語論理におけるド・モルガンの法則を表現していると考えられる。
命題論理におけるド・モルガンの法則から、以下のようにして述語論理に拡張されたド・モルガンの法則を確かめられる(次節に注意)。
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(3) または …… または 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 (英語).