結合／分離の二重性

命題論理とブール代数では、論理積と論理和の間に双対性があり、^{[ 1 ] [ 2 ] [ 3 ]}双対性原理とも呼ばれます。^{[ 4 ] [ 5 ] [ 6 ]}これは論理における双対性の最もよく知られた例です。^{[ 1 ]}この双対性は、以下のメタ論理定理から成ります。

• 古典命題論理では、連言と選言の結合子は互いに定義できるため、どちらか一方だけを基本要素として採用すればよい。^{[ 4 ] [ 1 ]}
• もし$\displaystyle \varphi ^{D}}$は、すべての論理積を論理和に、すべての論理和を論理積に置き換えた結果を表す表記法として使用されます（例：${\displaystyle p\land q}$と${\displaystyle q\lor p}$（またはその逆）特定の式において${\displaystyle \varphi }$、そしてもし${\displaystyle {\overline {\varphi }}}$は、文中のすべての文字を置き換えるための表記として使用されます。${\displaystyle \varphi }$否定形（例：${\displaystyle p}$と${\displaystyle \neg p}$)、そしてその記号が${\displaystyle \models }$は意味的帰結に、⟚は論理式間の意味的等価性に使用されるので、次のことが証明できる。$\displaystyle \varphi ^{D}}$ ⟚ ${\displaystyle \neg {\overline {\varphi }}}$[ ^{4 ] [ 7 ] [ 6 ]}また^、${\displaystyle \varphi \models \psi }$もし、そしてその場合に限り、${\displaystyle \psi ^{D}\models \varphi ^{D}}$[ ^{7 ]}さらに、^もし${\displaystyle \varphi }$ ⟚ ${\displaystyle \psi }$それから$\displaystyle \varphi ^{D}}$ ⟚ $\displaystyle \psi ^{D}}$^{[ 7 ]}（この文脈では、${\displaystyle {\overline {\varphi }}^{D}}$は公式の双対と呼ばれる。${\displaystyle \varphi }$.) ^{[ 4 ] [ 5 ]}

接続詞は、互いに関して次のように定義することができる。

${\displaystyle \varphi \vee \psi$ :\equiv \neg (\neg \varphi \land \neg \psi ).} (1)

${\displaystyle \varphi \land \psi$ :\equiv \neg (\neg \varphi \vee \neg \psi ).} (2)

${\displaystyle \neg (\neg \varphi \vee \neg \psi )\equiv \neg \neg (\neg \neg \varphi \land \neg \neg \psi )\equiv \varphi \land \psi .}$（３）

文の双対は、すべての出現箇所を入れ替えることで得られるものです。${\textstyle \vee }$そして${\textstyle \land }$同時に、すべての命題定数を否定します。たとえば、の双対は${\textstyle (A\land B\vee C)}$だろう${\textstyle (\neg A\vee \neg B\land \neg C)}$公式の双対${\textstyle \varphi }$は次のように表記されます${\textstyle \varphi ^{*}}$双対性原理は、古典命題論理では、任意の文はその双対の否定と等価であると述べている。^{[ 4 ] [ 7 ]}

二元性の原理：すべての人にとって${\textstyle \varphi }$我々はそれを持っている${\textstyle \varphi =\neg (\varphi ^{*})}$[ ^{4 ] [ 7 ]​}

証明：複雑性に関する帰納法による。基本ケースとして、任意の原子文を考える。${\textstyle A}$双対は${\textstyle \neg A}$その双対の否定は${\textstyle \neg \neg A}$これは確かに${\textstyle A}$帰納ステップでは、任意の${\textstyle \varphi }$そして、この結果がより単純なすべての文にも当てはまると仮定する。３つのケース：

1. もし${\textstyle \varphi }$形式は${\textstyle \neg \psi }$一部の人にとって${\textstyle \psi }$すると、その双対は${\textstyle \neg (\psi ^{*})}$したがって、その双対の否定は次のようになる。${\textstyle \neg \neg (\psi ^{*})}$.さて、${\textstyle \psi }$より複雑ではない${\textstyle \varphi }$帰納仮説によれば、${\textstyle \psi =\neg (\psi ^{*})}$代入すると、次のようになる。${\textstyle \varphi =\neg \neg (\psi ^{*})}$つまり、${\textstyle \varphi }$それは、その双対の否定と同等である。
2. もし${\textstyle \varphi }$形式は${\textstyle (\psi \vee \chi )}$一部の人にとって${\textstyle \psi }$そして${\textstyle \chi }$すると、その双対は${\textstyle (\psi ^{*}\land \chi ^{*})}$したがって、その双対の否定は次のようになる。${\textstyle \neg (\psi ^{*}\land \chi ^{*})}$.さて、${\textstyle \psi }$そして${\textstyle \chi }$より複雑ではない${\textstyle \varphi }$帰納仮説によれば、${\textstyle \psi =\neg (\psi ^{*})}$そして${\textstyle \chi =\neg (\chi ^{*})}$代入すると、次のようになる。${\textstyle \varphi =\neg (\psi ^{*})\vee \neg (\chi ^{*})}$それは私たちに${\textstyle \varphi =\neg (\psi ^{*}\land \chi ^{*})}$ド・モルガンの法則により。そしてそれは、${\textstyle \varphi }$それは、その双対の否定と同等である。
3. もし${\textstyle \varphi }$形式は${\textstyle \psi \vee \chi }$同様の推論により、結果は導かれる。

数式の場合${\displaystyle \varphi }$選言標準形では、式${\displaystyle {\overline {\varphi }}^{D}}$は連言標準形になり、 § 否定が双対と意味的に同等であるという結果が与えられた場合、それは意味的に同等になります${\displaystyle \neg \varphi }$[ ^{8 ] [ 9 ]これは、}連言標準形と選言標準形の間の変換手順を提供する。^{[ 10 ]}選言標準形定理は、命題論理のすべての式が選言標準形で表現可能であることを示しているので、すべての式は、その双対への変換を行うことによって連言標準形でも表現できる。^{[ 9 ]}

^{[ 11 ] [ 12 ]}