命題論理およびブール代数において、論理積と論理和の間には双対性（Conjunction/disjunction duality）が存在し、これは双対性原理とも呼ばれる。 これは論理学における双対性の中で最も広く知られた例である。 この双対性は、以下のようなメタ論理的定理から成り立っている。
古典命題論理において、論理積と論理和を表す結合子は互いによって定義することができ、その結果としてどちらか一方のみを原始記号として採用すればよい。 ある論理式において、論理積のすべての出現を論理和に、論理和のすべての出現を論理積に置き換えた結果を表す記法としてを用いる場合（例えばをに、あるいはその逆に置き換える）、また中のすべての命題文字をその否定に置き換えることを表す記法としてを用いる場合（例えばをに置き換える）、さらに意味論的帰結を表す記号として、論理式間の意味論的同値を表す記号として⟚を用いる場合、 ⟚ が証明可能であり、またであることとであることが同値であり、さらに ⟚ ならば ⟚ であることも証明可能である。（この文脈において、は論理式の双対と呼ばれる。）
相互定義可能性 これらの結合子は、以下のように互いを用いて定義することができる。 (1) (2) (3)
関数完全性 選言標準形定理により、結合子の集合が関数完全であることが示されるため、これらの結果から結合子の集合およびもそれ自体が関数完全であることが分かる。
ド・モルガンの法則 ド・モルガンの法則も、これらの結合子を互いによって定義することから導かれる。これはどちらの方向で行っても成り立つ。
(4)
(5)
双対性の性質
ある文の双対とは、とのすべての出現を入れ替え、同時にすべての命題定数を否定することで得られるものである。例えば、の双対はとなる。論理式の双対はと表記される。双対性原理は、古典命題論理において任意の文がその双対の否定と同値であることを主張する。
双対性原理: 任意のについて、が成り立つ。 証明: 複雑さに関する帰納法による。基底段階として、任意の原子文を考える。その双対はであるから、その双対の否定はとなり、これは確かにと同値である。帰納段階では、任意のを考え、それより複雑さの低いすべての文について結果が成り立つと仮定する。3つの場合がある。 があるについての形をしている場合、その双対はとなり、その双対の否定はとなる。ここではより複雑さが低いため、帰納法の仮定よりである。代入により、が得られ、これはがその双対の否定と同値であることを意味する。 があるとについての形をしている場合、その双対はとなり、その双対の否定はとなる。ここでとはより複雑さが低いため、帰納法の仮定よりおよびである。代入によりが得られ、これはド・モルガンの法則によりを与える。これもまた、がその双対の否定と同値であることを意味する。 がの形をしている場合、同様の推論により結果が従う。
さらなる双対性定理 と仮定する。このとき、をで一様代入することによりが成り立つ。したがって、対偶による証明によりとなる。よって最終的に、上で証明した ⟚ という性質により、が成り立つ。 そしてであるから、であることとであることは同値でもある。 さらに系として、ならばであることが従う。
連言標準形と選言標準形
選言標準形にある論理式に対して、は連言標準形になり、上で示した「否定は双対と意味論的に同値である」という結果を用いると、と意味論的に同値になる。 これにより、連言標準形と選言標準形の間で変換を行う手続きが得られる。 選言標準形定理により命題論理のすべての論理式が選言標準形で表現可能であることが示されているため、双対への変換を行うことで、すべての論理式は連言標準形でも表現可能である。
出典