ド・モルガンの法則

ウィキペディア

索引トップ用語の索引ランキングカテゴリー

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/03/28 05:42 UTC 版)

束論における法則

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]。