ド・モルガンの法則

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

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

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

命題論理における法則

任意の命題 ${\displaystyle P,Q\in \{\bot ,\top \}}$（${\displaystyle P}$と${\displaystyle Q}$は真または偽のいずれか） に対して

${\displaystyle \neg (P\lor Q)=\neg P\land \neg Q\,,}$

${\displaystyle \neg (P\land Q)=\neg P\lor \neg Q}$

すなわち

「${\displaystyle P}$または${\displaystyle Q}$」でないは、「${\displaystyle P}$でない」かつ「${\displaystyle Q}$でない」と等しい

「${\displaystyle P}$かつ${\displaystyle Q}$」でないは、「${\displaystyle P}$でない」または「${\displaystyle Q}$でない」と等しい

が成り立つ。ここで${\displaystyle \lor }$は論理和、${\displaystyle \land }$は論理積、${\displaystyle \neg }$は否定を表す演算子である。

C言語とその影響を受けたプログラミング言語で一般的な論理式で表すと

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

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

となる。ここで||は論理和、&&は論理積、!は否定を表す論理演算子である。

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

より一般的な法則として、任意の n 個の命題 ${\displaystyle P_{1},P_{2},\cdots ,P_{n}\in \{\bot ,\top \}}$（${\displaystyle P_{1}}$から${\displaystyle P_{n}}$は真または偽のいずれか） に対して

${\displaystyle \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 変数の述語 ${\displaystyle F:D\to \{\bot ,\top \}}$ に対して

${\displaystyle \neg \,\forall x\,F(x)\,=\,\exists x\,\neg \,F(x)\,,}$

${\displaystyle \neg \,\exists x\,F(x)\,=\,\forall x\,\neg \,F(x)}$

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

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

${\displaystyle \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 を任意のブール代数とする。任意の ${\displaystyle x,y\in L}$ に対して

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

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

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

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

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

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

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

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

例

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

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

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

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

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

集合論における法則

一般的な集合の代数学では、

${\displaystyle {\overline {(P\cup Q)}}={\overline {P}}\cap {\overline {Q}}}$

${\displaystyle {\overline {(P\cap Q)}}={\overline {P}}\cup {\overline {Q}}}$

となる（ただし、￣は全体集合に対する補集合を表している）。ベン図を用いると第一式が正しいことが次のようにして分かる。

• 
  ${\displaystyle P\cup Q}$
• 
  ${\displaystyle {\overline {(P\cup Q)}}}$

• 
  ${\displaystyle {\overline {P}}}$
• 
  ${\displaystyle {\overline {Q}}}$
• 
  ${\displaystyle {\overline {P}}\cap {\overline {Q}}}$

→詳細は「差集合 § ド・モルガンの法則」を参照