ド・モルガンの法則

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

ド・モルガンの法則のベン図による表現。図1、図2のそれぞれの場合において、等式の両辺の集合は青い領域で図示される。

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

命題論理における法則編集

任意の命題 $P,Q\in \{\bot ,\top \}$ に対して

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

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

が成り立つ。これをド・モルガンの法則という^[1]。

より一般的な法則として、任意の n 個の命題 $P_{1},P_{2},\cdots ,P_{n}\in \{\bot ,\top \}$ に対して

\neg \left(\bigvee _{i=1}^{n}P_{i}\right)=\bigwedge _{i=1}^{n}\neg P_{i}\,,\quad \neg \left(\bigwedge _{i=1}^{n}P_{i}\right)=\bigvee _{i=1}^{n}\neg P_{i}

が成り立つ^[1]。

例編集

次の命題

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

の否定、すなわち

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

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

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

同じようにして

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

の否定は

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

になる。

述語論理における法則編集

D を空でない任意の対象領域とする。任意の 1 変数の述語 $F:D\to \{\bot ,\top \}$ に対して

\neg \,\forall x\,F(x)\,=\,\exists x\,\neg \,F(x)\,,

\neg \,\exists x\,F(x)\,=\,\forall x\,\neg \,F(x)

が成り立つ。これをド・モルガンの法則という^[1]。

$D=\{a_{1},a_{2},\cdots ,a_{n}\}$ （有限集合）である場合は、これは

\neg \left(\bigwedge _{i=1}^{n}F(a_{i})\right)=\bigvee _{i=1}^{n}\neg \,F(a_{i})\,,\quad \neg \left(\bigvee _{i=1}^{n}F(a_{i})\right)=\bigwedge _{i=1}^{n}\neg \,F(a_{i})

と変形できる^[1]。

例編集

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

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

と表現できる。具体例を挙げると、

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

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

全否定と部分否定編集

全否定や部分否定をどう言い換えるかという問題は（述語論理における）ド・モルガンの法則が扱う問題と本質的には同じである。

例えば x が本を表す変数として、「本 x が好きだ」という言明を A(x) と書くことにすると、肯定文「すべての本が好きだ」は「全ての x に対し A(x)」となる。

この文の部分否定「すべての本を好きだというわけではない」は「全ての x に対し A(x)」の否定であり、ド・モルガンの法則によって「ある x に対し￢A(x)」、すなわち「好きでない本もある」となる。全否定の文「すべての本が嫌いだ」は「全ての x に対し￢A(x)」と表せ、ド・モルガンの法則によって「ある x に対し A(x)」の否定、「好きな本はない」ということになる。

束論における法則編集

L を任意のブール代数とする。任意の $x,y\in L$ に対して

(x\cup y)^{c}=x^{c}\cap y^{c}\,,

(x\cap y)^{c}=x^{c}\cup y^{c}

が成り立つ。これをド・モルガンの法則という^[1]。

$\{a_{\lambda }|\lambda \in \Lambda \}$ を L の任意の部分集合とする。 $\textstyle \sup _{\lambda \in \Lambda }a_{\lambda }$ が存在するとき、 $\textstyle \inf _{\lambda \in \Lambda }a_{\lambda }^{c}$ も存在し、

\left(\sup _{\lambda \in \Lambda }a_{\lambda }\right)^{c}=\inf _{\lambda \in \Lambda }a_{\lambda }^{c}

が成り立つ。また、 $\textstyle \inf _{\lambda \in \Lambda }a_{\lambda }$ が存在するとき、 $\textstyle \sup _{\lambda \in \Lambda }a_{\lambda }^{c}$ も存在し、

\left(\inf _{\lambda \in \Lambda }a_{\lambda }\right)^{c}=\sup _{\lambda \in \Lambda }a_{\lambda }^{c}

が成り立つ。これをド・モルガンの一般法則という^[1]。

例編集

二元集合 $L=\{\bot ,\top \}$ をブール代数、 $\bot$ を最小元とすれば、 $\top$ は最大元となる。そのとき、最小元 $\bot$ は偽な命題、最大元 $\top$ は真な命題、結び ∪ は論理和 ∨、交わり ∩ は論理積 ∧ 、補元 c は否定￢を表すことになる。そして、ブール代数に関するド・モルガンの一般法則から、命題論理に関するド・モルガンの法則を導くことができる^[1]。

また、空でない任意の集合（対象領域）D を一つ固定して考えれば、D から L への写像は 1 変数の述語となり、全称作用素 $\forall x$ や存在作用素 $\exists x$ を定義することができる。そして、ブール代数に関するド・モルガンの一般法則から、述語論理に関するド・モルガンの法則を導くことができる^[1]。

直観主義論理における法則編集

直観主義論理においてはド・モルガンの法則は必ずしも成り立たない。しかし、直観主義論理（LJ）においても以下のシークエントは証明可能である^[1]。

$\,\neg ({\mathfrak {A}}\lor {\mathfrak {B}})\,\rightarrow \,\neg {\mathfrak {A}}\land \neg {\mathfrak {B}}$
$\,\neg {\mathfrak {A}}\land \neg {\mathfrak {B}}\,\rightarrow \,\neg ({\mathfrak {A}}\lor {\mathfrak {B}})$
$\,\neg {\mathfrak {A}}\lor \neg {\mathfrak {B}}\,\rightarrow \,\neg ({\mathfrak {A}}\land {\mathfrak {B}})$
$\,\neg \,\exists x\,{\mathfrak {F}}(x)\,\rightarrow \,\forall x\,\neg \,{\mathfrak {F}}(x)$
$\,\forall x\,\neg \,{\mathfrak {F}}(x)\,\rightarrow \,\neg \,\exists x\,{\mathfrak {F}}(x)$
$\,\exists x\,\neg \,{\mathfrak {F}}(x)\,\rightarrow \,\neg \,\forall x\,{\mathfrak {F}}(x)$