この記事は(検証可能 )な(参考文献や出典 )が全く示されていないか、不十分です。 (出典を追加 )して記事の信頼性向上にご協力ください。((このテンプレートの使い方 )) 出典検索? : ("ド・モルガンの法則" ) – (ニュース ) · (書籍 ) · (スカラー ) · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL (2018年6月 )
ド・モルガンの法則 (ド・モルガンのほうそく、英 : De Morgan's laws )は、ブール論理 や集合の代数学 において、論理和 と論理積 と否定 (集合のことばでは、合併 と共通部分 と補集合 )の間に成り立つ規則性である。名前は数学者オーガスタス・ド・モルガン (Augustus de Morgan, 1806–1871)にちなむ。
ド・モルガンの法則のベン図による表現。図1、図2のそれぞれの場合において、等式の両辺の集合は青い領域で図示される。
この規則性(論理のことばで言うと「真と偽を入れ替え、論理和と論理積を入れ替えた論理体系」)は、元の論理体系と同一視できる、ということであるので、ド・モルガンの双対性 (英: De Morgan's duality )と呼ばれることもある。
命題論理における法則 任意の命題 P , Q ∈ { ⊥ , ⊤ } {\displaystyle P,Q\in \{\bot ,\top \}} に対して
¬ ( P ∨ Q ) = ¬ P ∧ ¬ Q , {\displaystyle \neg (P\lor Q)=\neg P\land \neg Q\,,}
¬ ( P ∧ Q ) = ¬ P ∨ ¬ Q {\displaystyle \neg (P\land Q)=\neg P\lor \neg Q}
が成り立つ。これをド・モルガンの法則 という。
より一般的な法則として、任意の n 個の命題 P 1 , P 2 , ⋯ , P n ∈ { ⊥ , ⊤ } {\displaystyle P_{1},P_{2},\cdots ,P_{n}\in \{\bot ,\top \}} に対して
¬ ( ⋁ i = 1 n P i ) = ⋀ i = 1 n ¬ P i , ¬ ( ⋀ i = 1 n P i ) = ⋁ i = 1 n ¬ P i {\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}}
が成り立つ。
例 次の命題
「私の身長は160cm以上であり、かつ 私の体重は50kg以上である」 の否定、すなわち
「「私の身長は160cm以上であり、かつ 私の体重は50kg以上である」ではない 」 は、ド・モルガンの法則によれば、次の命題と等しい。
「私の身長は160cm未満である、または 私の体重は50kg未満である」 同じようにして
「このボールは青いか、または 赤い」 の否定は
「このボールは青くなく、かつ 赤くない」 になる。
述語論理における法則 D を空でない任意の対象領域 とする。任意の 1 変数の述語 F : D → { ⊥ , ⊤ } {\displaystyle F:D\to \{\bot ,\top \}} に対して
¬ ∀ x F ( x ) = ∃ x ¬ F ( x ) , {\displaystyle \neg \,\forall x\,F(x)\,=\,\exists x\,\neg \,F(x)\,,}
¬ ∃ x F ( x ) = ∀ x ¬ F ( x ) {\displaystyle \neg \,\exists x\,F(x)\,=\,\forall x\,\neg \,F(x)}
が成り立つ。これをド・モルガンの法則 という。
D = { a 1 , a 2 , ⋯ , a n } {\displaystyle D=\{a_{1},a_{2},\cdots ,a_{n}\}} (有限集合)である場合は、これは
¬ ( ⋀ i = 1 n F ( a i ) ) = ⋁ i = 1 n ¬ F ( a i ) , ¬ ( ⋁ i = 1 n F ( a i ) ) = ⋀ i = 1 n ¬ F ( a i ) {\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})}
と変形できる。
例 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 ∈ L {\displaystyle x,y\in L} に対して
( x ∪ y ) c = x c ∩ y c , {\displaystyle (x\cup y)^{c}=x^{c}\cap y^{c}\,,}
( x ∩ y ) c = x c ∪ y c {\displaystyle (x\cap y)^{c}=x^{c}\cup y^{c}}
が成り立つ。これをド・モルガンの法則 という。
{ a λ | λ ∈ Λ } {\displaystyle \{a_{\lambda }|\lambda \in \Lambda \}} を L の任意の部分集合 とする。 sup λ ∈ Λ a λ {\displaystyle \textstyle \sup _{\lambda \in \Lambda }a_{\lambda }} が存在するとき、 inf λ ∈ Λ a λ c {\displaystyle \textstyle \inf _{\lambda \in \Lambda }a_{\lambda }^{c}} も存在し、
( sup λ ∈ Λ a λ ) c = inf λ ∈ Λ a λ c {\displaystyle \left(\sup _{\lambda \in \Lambda }a_{\lambda }\right)^{c}=\inf _{\lambda \in \Lambda }a_{\lambda }^{c}}
が成り立つ。また、 inf λ ∈ Λ a λ {\displaystyle \textstyle \inf _{\lambda \in \Lambda }a_{\lambda }} が存在するとき、 sup λ ∈ Λ a λ c {\displaystyle \textstyle \sup _{\lambda \in \Lambda }a_{\lambda }^{c}} も存在し、
( inf λ ∈ Λ a λ ) c = sup λ ∈ Λ a λ c {\displaystyle \left(\inf _{\lambda \in \Lambda }a_{\lambda }\right)^{c}=\sup _{\lambda \in \Lambda }a_{\lambda }^{c}}
が成り立つ。これをド・モルガンの一般法則 という。
例 二元集合 L = { ⊥ , ⊤ } {\displaystyle L=\{\bot ,\top \}} をブール代数、 ⊥ {\displaystyle \bot } を最小元 とすれば、 ⊤ {\displaystyle \top } は最大元 となる。そのとき、最小元 ⊥ {\displaystyle \bot } は偽な命題、最大元 ⊤ {\displaystyle \top } は真な命題、結び ∪ は論理和 ∨、交わり ∩ は 論理積 ∧ 、補元 c は否定 ¬ を表すことになる。そして、ブール代数に関するド・モルガンの一般法則から、命題論理に関するド・モルガンの法則 を導くことができる。
また、空でない任意の集合(対象領域)D を一つ固定して考えれば、D から L への写像 は 1 変数の述語となり、全称作用素 ∀ x {\displaystyle \forall x} や存在作用素 ∃ x {\displaystyle \exists x} を定義することができる。そして、ブール代数に関するド・モルガンの一般法則から、述語論理に関するド・モルガンの法則 を導くことができる。
直観主義論理における法則 直観主義論理 においてはド・モルガンの法則は必ずしも成り立たない。しかし、直観主義論理((LJ ))においても以下のシークエント は証明可能である。
¬ ( A ∨ B ) → ¬ A ∧ ¬ B {\displaystyle \,\neg ({\mathfrak {A}}\lor {\mathfrak {B}})\,\rightarrow \,\neg {\mathfrak {A}}\land \neg {\mathfrak {B}}} ¬ A ∧ ¬ B → ¬ ( A ∨ B ) {\displaystyle \,\neg {\mathfrak {A}}\land \neg {\mathfrak {B}}\,\rightarrow \,\neg ({\mathfrak {A}}\lor {\mathfrak {B}})} ¬ A ∨ ¬ B → ¬ ( A ∧ B ) {\displaystyle \,\neg {\mathfrak {A}}\lor \neg {\mathfrak {B}}\,\rightarrow \,\neg ({\mathfrak {A}}\land {\mathfrak {B}})} ¬ ∃ x F ( x ) → ∀ x ¬ F ( x ) {\displaystyle \,\neg \,\exists x\,{\mathfrak {F}}(x)\,\rightarrow \,\forall x\,\neg \,{\mathfrak {F}}(x)} ∀ x ¬ F ( x ) → ¬ ∃ x F ( x ) {\displaystyle \,\forall x\,\neg \,{\mathfrak {F}}(x)\,\rightarrow \,\neg \,\exists x\,{\mathfrak {F}}(x)} ∃ x ¬ F ( x ) → ¬ ∀ x F ( x ) {\displaystyle \,\exists x\,\neg \,{\mathfrak {F}}(x)\,\rightarrow \,\neg \,\forall x\,{\mathfrak {F}}(x)}
集合論における法則 一般的な集合代数 では、
( P ∪ Q ) ¯ = P ¯ ∩ Q ¯ {\displaystyle {\overline {(P\cup Q)}}={\overline {P}}\cap {\overline {Q}}} ( P ∩ Q ) ¯ = P ¯ ∪ Q ¯ {\displaystyle {\overline {(P\cap Q)}}={\overline {P}}\cup {\overline {Q}}} となる(ただし、 ̄は全体集合に対する(補集合 )を表している)。ベン図 を用いると第一式が正しいことが次のようにして分かる。
P ∪ Q {\displaystyle P\cup Q}
( P ∪ Q ) ¯ {\displaystyle {\overline {(P\cup Q)}}}
P ¯ {\displaystyle {\overline {P}}}
Q ¯ {\displaystyle {\overline {Q}}}
P ¯ ∩ Q ¯ {\displaystyle {\overline {P}}\cap {\overline {Q}}}
詳細は「(差集合#ド・モルガンの法則 )」を参照
脚注
参考文献 前原, 昭二『復刊 数理論理学序説』共立出版、2010年。ISBN (9784320019430 )。
関連項目
外部リンク 世界大百科事典『(ド・モルガンの法則 )』 - コトバンク Weisstein, Eric W . "de Morgan's Laws ". MathWorld (英語). Weisstein, Eric W . "de Morgan's Duality Law ". MathWorld (英語).