ド・モルガンの法則

命題論理とブール代数において、ド・モルガンの法則^{[1] [2] [3]は}ド・モルガンの定理^[4]としても知られ、どちらも推論の有効な 規則である一対の変換規則である。これらは19世紀のイギリスの数学者オーガスタス・ド・モルガンにちなんで名付けられている。この規則により、否定を介して純粋に互いの用語だけで連言と選言を表現できる。

このルールは英語で次のように表現できます。

• 「A かつ B」の否定は「A ではない、または B ではない」と同じです。
• 「A または B」の否定は、「A ではなく、B でもない」と同じです。

または

• 2つの集合の和集合の補集合は、それらの補集合の積集合と同じである。
• 2つの集合の共通部分の補集合は、それらの補集合の和集合と同じである。

または

• (A または B) ではない = (A ではない) かつ (B ではない)
• (A かつ B) ではない = (A ではない) または (B ではない)

ここで、「A または B」は、 A または B のどちらか一方だけを意味する「排他的または」ではなく、A または B の 少なくとも1 つを意味する「包括的または」です。

ド・モルガンの法則の別の形式は以下のとおりです。

${\displaystyle A-(B\cup C)=(A-B)\cap (A-C),}$

${\displaystyle A-(B\cap C)=(A-B)\cup (A-C).}$

この法則の応用には、コンピュータ プログラムやデジタル回路設計における論理式の簡略化が含まれます。ド モルガンの法則は、数学的双対性のより一般的な概念の例です。

連言の否定規則は、次の順序記法で記述できます。

${\displaystyle {\begin{aligned}\neg (P\land Q)&\vdash (\neg P\lor \neg Q),{\text{and}}\\(\neg P\lor \neg Q)&\vdash \neg (P\land Q).\end{aligned}}}$

選言規則の否定は次のように記述できます。

${\displaystyle {\begin{aligned}\neg (P\lor Q)&\vdash (\neg P\land \neg Q),{\text{and}}\\(\neg P\land \neg Q)&\vdash \neg (P\lor Q).\end{aligned}}}$

規則形式：接続詞の否定

および選言の否定

真理関数トートロジーまたは命題論理の定理として表現される：

${\displaystyle {\begin{aligned}\neg (P\land Q)&\leftrightarrow (\neg P\lor \neg Q),\\\neg (P\lor Q)&\leftrightarrow (\neg P\land \neg Q).\\\end{aligned}}}$

ここで、およびは何らかの形式体系で表現された命題です。 ${\displaystyle P}$${\displaystyle Q}$

一般化されたド・モルガンの法則は、複数の項を含む論理積または論理和を否定するための等価性を提供します。
命題の集合に対して、一般化されたド・モルガンの法則は次のようになります。 ${\displaystyle P_{1},P_{2},\dots ,P_{n}}$

${\displaystyle {\begin{aligned}\lnot (P_{1}\land P_{2}\land \dots \land P_{n})\leftrightarrow \lnot P_{1}\lor \lnot P_{2}\lor \ldots \lor \lnot P_{n}\\\lnot (P_{1}\lor P_{2}\lor \dots \lor P_{n})\leftrightarrow \lnot P_{1}\land \lnot P_{2}\land \ldots \land \lnot P_{n}\end{aligned}}}$

これらの法則は、ド・モルガンの論理積と論理和の否定に関する元の法則を一般化したものです。

ド・モルガンの法則は通常、出力の否定を左側に、入力の否定を右側に置いた、上記の簡潔な形式で示されます。置換のより明確な形式は次のように表すことができます。

${\displaystyle {\begin{aligned}(P\land Q)&\Longleftrightarrow \neg (\neg P\lor \neg Q),\\(P\lor Q)&\Longleftrightarrow \neg (\neg P\land \neg Q).\end{aligned}}}$

これは、置換を行うときに入力と出力の両方を反転するとともに、演算子を変更する必要があることを強調しています。

集合論では、これは「和集合と積集合は相補関係の下で交換される」と表現されることが多く、^[5]次のように正式に表現される。

${\displaystyle {\begin{aligned}{\overline {A\cup B}}&={\overline {A}}\cap {\overline {B}},\\{\overline {A\cap B}}&={\overline {A}}\cup {\overline {B}},\end{aligned}}}$

どこ：

• ${\displaystyle {\overline {A}}}$は の否定であり、上線は否定される項の上に書かれる。${\displaystyle A}$
• ${\displaystyle \cap }$は積演算子（AND）です。
• ${\displaystyle \cup }$結合演算子 (OR)です。

一般化された形式は

${\displaystyle {\begin{aligned}{\overline {\bigcap _{i\in I}A_{i}}}&\equiv \bigcup _{i\in I}{\overline {A_{i}}},\\{\overline {\bigcup _{i\in I}A_{i}}}&\equiv \bigcap _{i\in I}{\overline {A_{i}}},\end{aligned}}}$

ここで、I は、可算無限または非可算無限である可能性のある何らかのインデックス セットです。

集合記法では、ド・モルガンの法則は「線を切って、符号を変える」という記憶法で覚えることができる。 ^[6]

同様に、ブール代数では、この法則は次のように正式に表現できます。

${\displaystyle {\begin{aligned}{\overline {A\land B}}&={\overline {A}}\lor {\overline {B}},\\{\overline {A\lor B}}&={\overline {A}}\land {\overline {B}},\end{aligned}}}$

どこ：

• ${\displaystyle {\overline {A}}}$は の否定であり、上線は否定される項の上に書かれる。${\displaystyle A}$
• ${\displaystyle \land }$論理積演算子（AND）です。
• ${\displaystyle \lor }$論理和演算子(OR)です。

これは次のように一般化できる

${\displaystyle {\begin{aligned}{\overline {A_{1}\land A_{2}\land \ldots \land A_{n}}}={\overline {A_{1}}}\lor {\overline {A_{2}}}\lor \ldots \lor {\overline {A_{n}}},\\{\overline {A_{1}\lor A_{2}\lor \ldots \lor A_{n}}}={\overline {A_{1}}}\land {\overline {A_{2}}}\land \ldots \land {\overline {A_{n}}}.\end{aligned}}}$

電気工学やコンピュータ工学では、ド・モルガンの法則は一般的に次のように記述されます。

${\displaystyle {\overline {(A\cdot B)}}\equiv ({\overline {A}}+{\overline {B}})}$

そして

${\displaystyle {\overline {(A+B)}}\equiv ({\overline {A}}\cdot {\overline {B}}),}$

どこ：

• ${\displaystyle \cdot }$論理積です。
• ${\displaystyle +}$論理和です。
• オーバーバーは、オーバーバーの下にあるものの論理 NOT です。

ド・モルガンの法則は、ブール演算子 AND、OR、NOT を使用したテキスト検索によく適用されます。「cats」と「dogs」という単語を含むドキュメント セットを考えてみましょう。ド・モルガンの法則によれば、次の 2 つの検索で同じドキュメント セットが返されます。

検索A: NOT (猫または犬)

検索 B: (猫ではない) AND (犬ではない)

「猫」または「犬」を含む文書のコーパスは、次の 4 つの文書で表すことができます。

文書 1: 「cats」という単語のみが含まれています。

文書 2: 「犬」のみが含まれます。

文書 3: 「猫」と「犬」の両方が含まれています。

文書 4: 「猫」も「犬」も含まれていません。

検索 A を評価すると、明らかに検索「(cats OR dogs)」はドキュメント 1、2、3 にヒットします。したがって、その検索の否定 (検索 A) は、他のすべて (ドキュメント 4) にヒットします。

検索 B を評価すると、検索「(NOT cats)」は「cats」を含まないドキュメント、つまりドキュメント 2 と 4 にヒットします。同様に、検索「(NOT dogs)」はドキュメント 1 と 4 にヒットします。これらの 2 つの検索 (検索 B) に AND 演算子を適用すると、これら 2 つの検索に共通するドキュメント、つまりドキュメント 4 にヒットします。

同様の評価を適用すると、次の 2 つの検索でドキュメント 1、2、4 が返されることがわかります。

検索C: NOT (猫と犬)、

Dを検索: (猫ではない)または(犬ではない)。

これらの法則は、古典的な命題論理にこれらの法則の形式版を導入したオーガスタス・ド・モルガン(1806–1871)にちなんで名付けられている^{[7] 。ド・モルガンの定式化は、}ジョージ・ブールによる論理の代数化の影響を受けており、これが後にド・モルガンの発見に対する主張を確固たるものにした。しかしながら、同様の観察はアリストテレスによってなされており、ギリシャや中世の論理学者には知られていた。^[8]例えば、14世紀には、ウィリアム・オッカムが、これらの法則を読み上げたときに生じる言葉を書き留めている。^[9]ジャン・ビュリダンは、著書『弁証法総括』の中で、ド・モルガンの法則に沿った変換規則についても説明している。^[10]それでも、ド・モルガンは、これらの法則を現代の形式論理の用語で述べ、それを論理の言語に取り入れたことで評価されている。ド・モルガンの法則は簡単に証明でき、些細なことのように思えるかもしれない。^[11]それにもかかわらず、これらの法則は証明や演繹的議論において有効な推論を行うのに役立ちます。

ド・モルガンの定理は、式の全体または一部における 選言の否定または連言の否定に適用できます。

これを選言に適用する場合、次の主張を考えてみましょう。「A または B のいずれかが真であるというのは誤りである」これは次のように記述されます。

${\displaystyle \neg (A\lor B).}$

A も B も真ではないことが確立されているので、AもB も真ではないということが必然的にわかります。これは次のように直接書くことができます。

${\displaystyle (\neg A)\wedge (\neg B).}$

A または B のいずれかが真であれば、A と B の論理和は真となり、その否定は偽になります。英語で表現すると、これは「2 つのことが両方とも偽であるため、どちらかが真であるというのも偽である」という論理に従います。

反対方向に作用すると、2 番目の式は A が偽であり、B が偽である (または、「A ではない」および「B ではない」が真である) と主張します。これを知ると、A と B の論理和も偽でなければなりません。したがって、この論理和の否定は真でなければならず、結果は最初の主張と同一になります。

ド・モルガンの定理を論理積に適用することは、形式と論理的根拠の両方において、論理和に適用することと非常に似ています。次の主張を考えてみましょう。「A と B が両方とも真であるというのは誤りである」これは次のように記述されます。

${\displaystyle \neg (A\land B).}$

この主張が真であるためには、A または B のいずれかまたは両方が偽でなければなりません。なぜなら、両方が真であれば、A と B の論理積は真となり、その否定は偽になるからです。したがって、A と B の少なくとも 1 つ以上が偽でなければなりません (または、同等に、「A ではない」と「B ではない」の 1 つ以上が真でなければなりません)。これは次のように直接記述できます。

${\displaystyle (\neg A)\lor (\neg B).}$

これを英語で表現すると、「2 つの事柄が両方とも真であるというのは誤りなので、少なくともそのうちの 1 つは誤りであるはずだ」という論理に従います。

再び逆方向に作業すると、2 番目の式は、「A ではない」と「B ではない」の少なくとも 1 つは真でなければならない、または同等に、A と B の少なくとも 1 つは偽でなければならないと主張します。それらの少なくとも 1 つは偽でなければならないため、それらの結合も同様に偽になります。したがって、この結合を否定すると、真の式になり、この式は最初の主張と同一になります。

ここでは、§ 集合論とブール代数で述べたように、 A の補集合を表すために を使用します。 の証明は、と の両方を証明することによって 2 つのステップで完了します。 ${\displaystyle {\overline {A}}}$${\displaystyle {\overline {A\cap B}}={\overline {A}}\cup {\overline {B}}}$${\displaystyle {\overline {A\cap B}}\subseteq {\overline {A}}\cup {\overline {B}}}$${\displaystyle {\overline {A}}\cup {\overline {B}}\subseteq {\overline {A\cap B}}}$

とします。 すると、${\displaystyle x\in {\overline {A\cap B}}}$${\displaystyle x\not \in A\cap B}$

なぜなら、またはであるはずだからです。 ${\displaystyle A\cap B=\{\,y\ |\ y\in A\wedge y\in B\,\}}$${\displaystyle x\not \in A}$${\displaystyle x\not \in B}$

もしならば、 なので。 ${\displaystyle x\not \in A}$${\displaystyle x\in {\overline {A}}}$${\displaystyle x\in {\overline {A}}\cup {\overline {B}}}$

同様に、 ならばなので、 となります。 ${\displaystyle x\not \in B}$${\displaystyle x\in {\overline {B}}}$${\displaystyle x\in {\overline {A}}\cup {\overline {B}}}$

したがって、; ${\displaystyle \forall x{\Big (}x\in {\overline {A\cap B}}\implies x\in {\overline {A}}\cup {\overline {B}}{\Big )}}$

つまり、。 ${\displaystyle {\overline {A\cap B}}\subseteq {\overline {A}}\cup {\overline {B}}}$

逆方向を証明するには、 とし、矛盾を避けるために と仮定します。 ${\displaystyle x\in {\overline {A}}\cup {\overline {B}}}$${\displaystyle x\not \in {\overline {A\cap B}}}$

この仮定のもとでは、 ${\displaystyle x\in A\cap B}$

したがって、およびとなり、したがっておよび となります。 ${\displaystyle x\in A}$${\displaystyle x\in B}$${\displaystyle x\not \in {\overline {A}}}$${\displaystyle x\not \in {\overline {B}}}$

しかし、それは、仮説に反して、 ${\displaystyle x\not \in {\overline {A}}\cup {\overline {B}}}$${\displaystyle x\in {\overline {A}}\cup {\overline {B}}}$

したがって、仮定は当てはまらないはずであり、つまり となります。 ${\displaystyle x\not \in {\overline {A\cap B}}}$${\displaystyle x\in {\overline {A\cap B}}}$

したがって、、 ${\displaystyle \forall x{\Big (}x\in {\overline {A}}\cup {\overline {B}}\implies x\in {\overline {A\cap B}}{\Big )}}$

つまり、。 ${\displaystyle {\overline {A}}\cup {\overline {B}}\subseteq {\overline {A\cap B}}}$

かつ ならばであり、これでド・モルガンの法則の証明は完了です。 ${\displaystyle {\overline {A}}\cup {\overline {B}}\subseteq {\overline {A\cap B}}}$ ${\displaystyle {\overline {A\cap B}}\subseteq {\overline {A}}\cup {\overline {B}}}$${\displaystyle {\overline {A\cap B}}={\overline {A}}\cup {\overline {B}}}$

もう一つのド・モルガンの法則も同様に証明されます。 ${\displaystyle {\overline {A\cup B}}={\overline {A}}\cap {\overline {B}}}$

古典的な命題論理の拡張でも、双対性は依然として成り立ちます (つまり、任意の論理演算子に対して常にその双対を見つけることができる)。これは、否定を支配する恒等式が存在する場合、常に別の演算子のド・モルガン双対である演算子を導入できるためです。これにより、古典論理に基づく論理の重要な特性、つまり否定正規形の存在がもたらされます。つまり、任意の式は、式の非論理アトムにのみ否定が適用された別の式と等価です。否定正規形の存在は、多くの応用を推進します。たとえば、デジタル回路設計では、論理ゲートの種類を操作するために使用されます。また、形式論理では、式の連言正規形と選言正規形を見つける必要があります。コンピュータプログラマーは、複雑な論理条件を簡略化したり、適切に否定したりするために使用します。また、初等確率論の計算でも役立つことがよくあります。

任意の命題演算子P( p , q ,...)の双対を、基本命題p , q ,...に応じて次のように定義される 演算子と定義する。${\displaystyle {\mbox{P}}^{d}}$

${\displaystyle {\mbox{P}}^{d}(p,q,...)=\neg P(\neg p,\neg q,\dots ).}$

この二重性は量指定子に一般化することができ、例えば全称量指定子と存在量指定子は二重です。

${\displaystyle \forall x\,P(x)\equiv \neg [\exists x\,\neg P(x)]}$

${\displaystyle \exists x\,P(x)\equiv \neg [\forall x\,\neg P(x)]}$

これらの量化子の双対性をド・モルガンの法則に関連付けるには、次のような、ドメインDに少数の要素を持つモデルを設定します。

D = { a、b、c }。

それから

${\displaystyle \forall x\,P(x)\equiv P(a)\land P(b)\land P(c)}$

そして

${\displaystyle \exists x\,P(x)\equiv P(a)\lor P(b)\lor P(c).}$

しかし、ド・モルガンの法則を用いると、

${\displaystyle P(a)\land P(b)\land P(c)\equiv \neg (\neg P(a)\lor \neg P(b)\lor \neg P(c))}$

そして

${\displaystyle P(a)\lor P(b)\lor P(c)\equiv \neg (\neg P(a)\land \neg P(b)\land \neg P(c)),}$

モデル内の量指定子の二重性を検証する。

次に、量指定子の双対性は、ボックス (「必然的に」) 演算子とダイヤモンド (「おそらく」) 演算子を関連付ける 様相論理にさらに拡張できます。

${\displaystyle \Box p\equiv \neg \Diamond \neg p,}$

${\displaystyle \Diamond p\equiv \neg \Box \neg p.}$

アリストテレスは、可能性と必然性の論理的様相への応用においてこの事例を観察しており、通常の様相論理の場合、これらの様相演算子と量化の関係は、クリプキ意味論を使用してモデルを設定することによって理解できます。

ド・モルガンの法則の4つの含意のうち3つは直観主義論理で成り立つ。具体的には、

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

そして

${\displaystyle {\big (}(\neg P)\lor (\neg Q){\big )}\,\to \,\neg (P\land Q).}$

最後の含意の逆は、純粋な直観論理では成り立たない。つまり、結合命題の失敗は、必ずしも2つの連言のいずれかの失敗に帰着するわけではない。例えば、アリスとボブの両方がデートに現れたわけではないことが分かっているからといって、誰が現れなかったかは分からない。後者の原理は、弱い排中律の原理と同等である。 ${\displaystyle P\land Q}$ ${\displaystyle {\mathrm {WPEM} }}$

${\displaystyle (\neg P)\lor \neg (\neg P).}$

この弱い形式は、中間論理の基礎として使用できます。存在ステートメントに関する失敗法則の洗練されたバージョンについては、より限定されていない全知の原理 を参照してください。ただし、これはとは異なります。 ${\displaystyle {\mathrm {LLPO} }}$${\displaystyle {\mathrm {WLPO} }}$

他の 3 つのド・モルガンの法則の妥当性は、否定が任意の定数述語 Cの含意に置き換えられた場合でも真のままです。つまり、上記の法則は最小論理では依然として真です。 ${\displaystyle \neg P}$${\displaystyle P\to C}$

上記と同様に、量指定子の法則は次のようになります。

${\displaystyle \forall x\,\neg P(x)\,\leftrightarrow \,\neg \exists x\,P(x)}$

そして

${\displaystyle \exists x\,\neg P(x)\,\to \,\neg \forall x\,P(x).}$

は、否定を固定された を意味することに置き換えた最小限の論理においてもトートロジーであり、最後の法則の逆は一般に真である必要はありません。 ${\displaystyle Q}$

さらに、

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

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

${\displaystyle \forall x\,P(x)\,\to \,\neg \exists x\,\neg P(x),}$

${\displaystyle \exists x\,P(x)\,\to \,\neg \forall x\,\neg P(x),}$

しかし、 それらの反転は排中律を意味します。${\displaystyle {\mathrm {PEM} }}$

• ド・モルガンの法則は、回路設計を簡素化する目的でコンピュータ工学やデジタルロジックの分野で広く使用されています。^[12]
• 現代のプログラミング言語では、コンパイラとインタープリタの最適化により、これらのオプション間のパフォーマンスの違いはごくわずかであるか、まったくありません。

• 結合/分離の二重性
• 同質性（言語学）
• 同型性
• ブール代数のトピックのリスト
• 集合の同一性と関係のリスト
• 肯定的な論理
• デ・モルガン代数

• 「双対原理」、数学百科事典、EMS Press、2001 [1994]
• ワイスタイン、エリック・W.「ド・モルガンの法則」。マスワールド。
• PlanetMathの de Morgan の法則。
• 論理と言語の二重性、インターネット哲学百科事典。