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 the most widely known example of duality in logic.
[1] The duality consists in these metalogical theorems: The connectives may be defined in terms of each other as follows: Since the Disjunctive Normal Form Theorem shows that the set of connectives
is functionally complete, these results show that the sets of connectives
are themselves functionally complete as well.
De Morgan's laws also follow from the definitions of these connectives in terms of each other, whichever direction is taken to do it.
[1] The dual of a sentence is what you get by swapping all occurrences of ∨ and &, while also negating all propositional constants.
The dual of a formula φ is notated as φ*.
The Duality Principle states that in classical propositional logic, any sentence is equivalent to the negation of its dual.
ϕ ⊨ ψ
by uniform substitution of
, by contraposition; so finally,
[7] And it follows, as a corollary, that if
in disjunctive normal form, the formula
will be in conjunctive normal form, and given the result that § Negation is semantically equivalent to dual, it will be semantically equivalent to
[8][9] This provides a procedure for converting between conjunctive normal form and disjunctive normal form.
[10] Since the Disjunctive Normal Form Theorem shows that every formula of propositional logic is expressible in disjunctive normal form, every formula is also expressible in conjunctive normal form by means of effecting the conversion to its dual.