Conjunction/disjunction duality

Logical connectives
AND ${\displaystyle A\land B}$, ${\displaystyle A\cdot B}$, ${\displaystyle AB}$, ${\displaystyle A\&B}$, ${\displaystyle A\&\&B}$ equivalent ${\displaystyle A\equiv B}$, ${\displaystyle A\Leftrightarrow B}$, ${\displaystyle A\leftrightharpoons B}$ implies ${\displaystyle A\Rightarrow B}$, ${\displaystyle A\supset B}$, ${\displaystyle A\rightarrow B}$ NAND ${\displaystyle A{\overline {\land }}B}$, ${\displaystyle A\uparrow B}$, ${\displaystyle A\mid B}$, ${\displaystyle {\overline {A\cdot B}}}$ nonequivalent ${\displaystyle A\not \equiv B}$, ${\displaystyle A\not \Leftrightarrow B}$, ${\displaystyle A\nleftrightarrow B}$ NOR ${\displaystyle A{\overline {\lor }}B}$, ${\displaystyle A\downarrow B}$, ${\displaystyle {\overline {A+B}}}$ NOT ${\displaystyle \neg A}$, ${\displaystyle -A}$, ${\displaystyle {\overline {A}}}$, ${\displaystyle \sim A}$ OR ${\displaystyle A\lor B}$, ${\displaystyle A+B}$, ${\displaystyle A\mid B}$, ${\displaystyle A\parallel B}$ XNOR ${\displaystyle A\ {\text{XNOR}}\ B}$ XOR ${\displaystyle A{\underline {\lor }}B}$, ${\displaystyle A\oplus B}$ converse ${\displaystyle A\Leftarrow B}$, ${\displaystyle A\subset B}$, ${\displaystyle A\leftarrow B}$
Related concepts
Propositional calculus Predicate logic Boolean algebra Truth table Truth function Boolean function Functional completeness Scope (logic)
Applications
Digital logic Programming languages Mathematical logic Philosophy of logic
Category
v t e

In propositional logic and Boolean algebra, there is a duality between conjunction and disjunction,^[1][2][3] also called the duality principle.^[4][5][6] It is, undoubtedly, the most widely known example of duality in logic.^[1] The duality consists in these metalogical theorems:

• In classical propositional logic, the connectives for conjunction and disjunction can be defined in terms of each other, and consequently, only one of them needs to be taken as primitive.^[4][1]
• If ${\displaystyle \varphi ^{D}}$ is used as notation to designate the result of replacing every instance of conjunction with disjunction, and every instance of disjunction with conjunction (e.g. ${\displaystyle p\land q}$ with ${\displaystyle q\lor p}$, or vice-versa), in a given formula ${\displaystyle \varphi }$, and if ${\displaystyle {\overline {\varphi }}}$ is used as notation for replacing every sentence-letter in ${\displaystyle \varphi }$ with its negation (e.g., ${\displaystyle p}$ with ${\displaystyle \neg p}$), and if the symbol ${\displaystyle \models }$ is used for semantic consequence and ⟚ for semantical equivalence between logical formulas, then it is demonstrable that ${\displaystyle \varphi ^{D}}$ ⟚ ${\displaystyle \neg {\overline {\varphi }}}$,^[4][7][6] and also that ${\displaystyle \varphi \models \psi }$ if, and only if, ${\displaystyle \psi ^{D}\models \varphi ^{D}}$,^[7] and furthermore that if ${\displaystyle \varphi }$ ⟚ ${\displaystyle \psi }$ then ${\displaystyle \varphi ^{D}}$ ⟚ ${\displaystyle \psi ^{D}}$.^[7] (In this context, ${\displaystyle {\overline {\varphi }}^{D}}$ is called the dual of a formula ${\displaystyle \varphi }$.)^[4][5]

This article will prove these results, in the § Mutual definability and § Negation is semantically equivalent to dual sections respectively.