ド・モルガンの法則のソースを表示

{{出典の明記| date = 2018年6月}}
[[File:Demorganlaws.svg|thumb|ド・モルガンの法則のベン図による表現。図1、図2のそれぞれの場合において、等式の両辺の集合は青い領域で図示される。]]
'''ド・モルガンの法則'''（ド・モルガンのほうそく、{{Lang-en-short|De Morgan's laws}}）は、[[ブール論理]]や[[集合の代数学]]において、[[論理和]]と[[論理積]]と[[否定]]（集合のことばでは、[[和集合]]と[[共通部分 (数学)|共通部分]]と[[差集合]]）の間に成り立つ規則性である。名前は数学者[[オーガスタス・ド・モルガン]]（Augustus de Morgan, 1806–1871）にちなむ。

この規則性（論理のことばで言うと「真と偽を入れ替え、論理和と論理積を入れ替えた論理体系」）は、元の論理体系と同一視できる、ということであるので、'''ド・モルガンの[[双対性]]'''（{{Lang-en-short|links=no|De Morgan's duality}}）と呼ばれることもある。

== 命題論理における法則 ==
任意の[[命題]] <math>P, Q \in \{ \bot, \top \}</math>（<math>P</math>と<math>Q</math>は真または偽のいずれか） に対して
{{NumBlk|:|<math>\neg (P \lor Q) = \neg P \land \neg Q \, ,</math>| |RawN=.}}
{{NumBlk|:|<math>\neg (P \land Q) = \neg P \lor \neg Q</math>| |RawN=.}}
すなわち
: 「<math>P</math>または<math>Q</math>」でないは、「<math>P</math>でない」かつ「<math>Q</math>でない」と等しい
: 「<math>P</math>かつ<math>Q</math>」でないは、「<math>P</math>でない」または「<math>Q</math>でない」と等しい
が成り立つ。ここで<math>\lor</math>は[[論理和]]、<math>\land</math>は[[論理積]]、<math>\neg</math>は[[否定]]を表す演算子である。

[[C言語]]とその影響を受けた[[プログラミング言語]]で一般的な論理式で表すと
: <code>!(P || Q) == !P && !Q</code>
: <code>!(P && Q) == !P || !Q</code>
となる。ここで<code>||</code>は論理和、<code>&&</code>は論理積、<code>!</code>は否定を表す[[論理演算子]]である。

これを'''ド・モルガンの法則'''という{{Sfn|前原|2010}}。

より一般的な法則として、任意の ''n'' 個の命題 <math>P_{1}, P_{2}, \cdots, P_{n}\in \{ \bot, \top \}</math>（<math>P_{1}</math>から<math>P_{n}</math>は真または偽のいずれか） に対して
{{NumBlk|:|<math>\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}</math>| |RawN=.}}
が成り立つ{{Sfn|前原|2010}}。

=== 例 ===
次の命題
:「私の身長は160cm以上であり、'''かつ'''私の体重は50kg以上である」
の否定、すなわち
:「「私の身長は160cm以上であり、'''かつ'''私の体重は50kg以上である」では'''ない'''」
は、ド・モルガンの法則によれば、次の命題と等しい。
:「私の身長は160cm未満である、'''または'''私の体重は50kg未満である」
同じようにして
:「このボールは青いか、'''または'''赤い」
の否定は
:「このボールは青くなく、'''かつ'''赤くない」
になる。

== 述語論理における法則 ==
D を空でない任意の対象領域とする。任意の 1 変数の[[述語論理|述語]] <math>F : D \to \{ \bot, \top \}</math> に対して
{{NumBlk|:|<math>\neg \, \forall x \, F(x) \, = \, \exists x \, \neg \, F(x) \, ,</math>| |RawN=.}}
{{NumBlk|:|<math>\neg \, \exists x \, F(x) \, = \, \forall x \, \neg \, F(x)</math>| |RawN=.}}
が成り立つ。これを'''ド・モルガンの法則'''という{{Sfn|前原|2010}}。

<math>D = \{ a_{1}, a_{2}, \cdots, a_{n} \}</math>（有限集合）である場合は、これは
{{NumBlk|:|<math>\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})</math>| |RawN=.}}
と変形できる{{Sfn|前原|2010}}。

=== 例 ===
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 を任意の[[ブール代数]]とする。任意の <math>x,y \in L</math> に対して
{{NumBlk|:|<math>(x \cup y)^{c} = x^{c} \cap y^{c} \, ,</math>| |RawN=.}}
{{NumBlk|:|<math>(x \cap y)^{c} = x^{c} \cup y^{c}</math>| |RawN=.}}
が成り立つ。これを'''ド・モルガンの法則'''という{{Sfn|前原|2010}}。

<math>\{ a_{\lambda} | \lambda \in \Lambda \}</math> を L の任意の[[部分集合]]とする。<math>\textstyle \sup_{\lambda \in \Lambda} a_{\lambda}</math> が存在するとき、<math>\textstyle \inf_{\lambda \in \Lambda} a_{\lambda}^{c}</math> も存在し、
{{NumBlk|:|<math>\left ( \sup_{\lambda \in \Lambda} a_{\lambda} \right )^{c} = \inf_{\lambda \in \Lambda} a_{\lambda}^{c}</math>| |RawN=.}}
が成り立つ。また、<math>\textstyle \inf_{\lambda \in \Lambda} a_{\lambda}</math> が存在するとき、<math>\textstyle \sup_{\lambda \in \Lambda} a_{\lambda}^{c}</math> も存在し、
{{NumBlk|:|<math>\left ( \inf_{\lambda \in \Lambda} a_{\lambda} \right )^{c} = \sup_{\lambda \in \Lambda} a_{\lambda}^{c}</math>| |RawN=.}}
が成り立つ。これを'''ド・モルガンの一般法則'''という{{Sfn|前原|2010}}。

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

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

== 直観主義論理における法則 ==
[[直観主義論理]]においてはド・モルガンの法則は必ずしも成り立たない。しかし、直観主義論理（[[シークエント計算#LJ|LJ]]）においても以下の[[シークエント計算]]は証明可能である{{Sfn|前原|2010}}。
* <math>\, \neg (\mathfrak{A} \lor \mathfrak{B}) \, \rightarrow \, \neg \mathfrak{A} \land \neg \mathfrak{B}</math>
* <math>\, \neg \mathfrak{A} \land \neg \mathfrak{B} \, \rightarrow \, \neg (\mathfrak{A} \lor \mathfrak{B})</math>
* <math>\, \neg \mathfrak{A} \lor \neg \mathfrak{B} \, \rightarrow \, \neg (\mathfrak{A} \land \mathfrak{B})</math>
* <math>\, \neg \, \exists x \, \mathfrak{F}(x) \, \rightarrow \, \forall x \, \neg \, \mathfrak{F}(x)</math>
* <math>\, \forall x \, \neg \, \mathfrak{F}(x) \, \rightarrow \, \neg \, \exists x \, \mathfrak{F}(x)</math>
* <math>\, \exists x \, \neg \, \mathfrak{F}(x) \, \rightarrow \, \neg \, \forall x \, \mathfrak{F}(x)</math>

== 集合論における法則 ==
一般的な[[集合の代数学]]では、
: <math>\overline{(P\cup Q)}=\overline{P}\cap \overline{Q}</math>
: <math>\overline{(P\cap Q)}=\overline{P}\cup \overline{Q}</math>
となる（ただし、￣は全体集合に対する[[差集合#補集合|補集合]]を表している）。[[ベン図]]を用いると第一式が正しいことが次のようにして分かる。
<gallery>
Image:Venn-Diagram-OR.png|<math>P\cup Q</math>
Image:Venn-Diagram-NOR.png|<math>\overline{(P\cup Q)}</math>
</gallery>
<gallery>
Image:Venn-Diagram-NOT-P.png|<math>\overline{P}</math>
Image:Venn-Diagram-NOT-Q.png|<math>\overline{Q}</math>
Image:Venn-Diagram-NOR.png|<math>\overline{P} \cap \overline{Q}</math>
</gallery>
{{Main|差集合#ド・モルガンの法則}}

== 出典 ==
{{Reflist}}

==参考文献==
* {{Cite book|和書|last=前原 |first=昭二 |year=2010 |title=復刊 数理論理学序説 |publisher=共立出版 |isbn=9784320019430 |ref=harv }}

== 関連項目 ==
* [[負論理]]
* [[真理関数]]

== 外部リンク ==
*{{Kotobank|ド・モルガンの法則|2=世界大百科事典}}
*{{MathWorld|title=de Morgan's Laws|urlname=deMorgansLaws}}
*{{MathWorld|title=de Morgan's Duality Law|urlname=deMorgansDualityLaw}}

{{Mathematical logic}}
{{Normdaten}}


{{DEFAULTSORT:ともるかんのほうそく}}
[[Category:推論規則]]
[[Category:命題論理の定理]]
[[Category:オーガスタス・ド・モルガン]]
[[Category:数学のエポニム]]
[[Category:数学に関する記事]]