ド・モルガンの法則

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

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

概要編集

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

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

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

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

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

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

!(P && Q) == !P || !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}}$

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

例編集

次の命題

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

の否定、すなわち

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

は、ド・モルガンの法則によれば、次の命題と等しい。

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

同じようにして

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

の否定は

「このボールは青くなく、かつ赤くない」

になる。

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

上のド・モルガンの法則は、一階述語論理にも拡張できる。

A(x) を変数 x についての言明とすると

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

と表現できる。

「全ての x に対し〜」、「ある 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(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)」が得られる。