ド・モルガンの法則

ド・モルガンの法則（ド・モルガンのほうそく、）は、ブール論理や集合の代数学において、論理和と論理積と否定（集合のことばでは、合併と共通部分と補集合）の間に成り立つ規則性である。名前は数学者オーガスタス・ド・モルガン（Augustus de Morgan, 1806–1871）にちなむ。
この規則性（論理のことばで言うと「真と偽を入れ替え、論理和と論理積を入れ替えた論理体系」）は、元の論理体系と同一視できる、ということであるので、ド・モルガンの双対性（）と呼ばれることもある。
命題論理における法則.
任意の命題 formula_1 に対して
が成り立つ。これをド・モルガンの法則という。
より一般的な法則として、任意の "n" 個の命題 formula_2 に対して
が成り立つ。
例.
次の命題
の否定、すなわち
は、ド・モルガンの法則によれば、次の命題と等しい。
同じようにして
の否定は
になる。
述語論理における法則.
D を空でない任意の対象領域とする。任意の 1 変数の述語 formula_3 に対して
が成り立つ。これをド・モルガンの法則という。
formula_4（有限集合）である場合は、これは
と変形できる。
例.
F(x) を変数 x についての言明とすると
と表現できる。具体例を挙げると、
などである。また、後述するように部分否定や全否定の言い換えも述語論理におけるド・モルガンの法則を表現していると考えられる。
全否定と部分否定.
全否定や部分否定をどう言い換えるかという問題は（述語論理における）ド・モルガンの法則が扱う問題と本質的には同じである。
例えば x が本を表す変数として、「本 x が好きだ」という言明を A(x) と書くことにすると、肯定文「すべての本が好きだ」は「全ての x に対し A(x)」となる。
この文の部分否定「すべての本を好きだというわけではない」は「全ての x に対し A(x)」の否定であり、ド・モルガンの法則によって「ある x に対し ￢A(x)」、すなわち「好きでない本もある」となる。全否定の文「すべての本が嫌いだ」は「全ての x に対し ￢A(x)」と表せ、ド・モルガンの法則によって「ある x に対し A(x)」の否定、「好きな本はない」ということになる。
束論における法則.
L を任意のブール代数とする。任意の formula_5 に対して
が成り立つ。これをド・モルガンの法則という。
formula_6 を L の任意の部分集合とする。formula_7 が存在するとき、formula_8 も存在し、
が成り立つ。また、formula_9 が存在するとき、formula_10 も存在し、
が成り立つ。これをド・モルガンの一般法則という。
例.
二元集合 formula_11 をブール代数、formula_12 を最小元とすれば、formula_13 は最大元となる。そのとき、最小元 formula_12 は偽な命題、最大元 formula_13 は真な命題、結び ∪ は論理和 ∨、交わり ∩ は 論理積 ∧ 、補元 c は否定 ￢ を表すことになる。そして、ブール代数に関するド・モルガンの一般法則から、命題論理に関するド・モルガンの法則を導くことができる。
また、空でない任意の集合（対象領域）D を一つ固定して考えれば、D から L への写像は 1 変数の述語となり、全称作用素 formula_16 や存在作用素 formula_17 を定義することができる。そして、ブール代数に関するド・モルガンの一般法則から、述語論理に関するド・モルガンの法則を導くことができる。
直観主義論理における法則.
直観主義論理においてはド・モルガンの法則は必ずしも成り立たない。しかし、直観主義論理（LJ）においても以下のシークエントは証明可能である。
集合論における法則.
一般的な集合代数では、
となる（ただし、￣は全体集合に対する補集合を表している）。ベン図を用いると第一式が正しいことが次のようにして分かる。