ド・モルガンの法則

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動先: 案内検索

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

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

概要[編集]

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

C言語などプログラミング言語の記号を使って書けば、P, Q がどんな式であろうと

!(P || Q) == !P && !Q
!(P && Q) == !P || !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に対し〜」を表す記号を使って書くと

となる。

具体例を挙げると、

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

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

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

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


関連項目[編集]

外部リンク[編集]