ド・モルガンの法則

出典: フリー百科事典『ウィキペディア（Wikipedia）』

このページは半保護の方針に基づき、一部ユーザーによる編集から保護されています。

ド・モルガンの法則（ド・モルガンのほうそく）とは、数理論理学や集合論において、論理積（集合の共通分）と論理和（集合の合併）、否定（補集合）操作の間の関係性（ド・モルガンの双対性とよばれる）を記述する定理であり、数学者のオーガスタス・ド・モルガンにちなんでこの名前がついている。

概要

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

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

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

プログラミング言語的に表現すれば、

(not (P or Q)) == ((not P) and (not Q))

(not (P and Q)) == ((not P) or (not 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}$

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

例

「私の身長は 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に対し〜」を表す量化子記号 $\forall x, \exists 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(100)」

となり、「A(2)かつ… 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)」をが得られる。