Logical connectives | ||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
||||||||||||||||||||||
Related concepts | ||||||||||||||||||||||
Applications | ||||||||||||||||||||||
![]() | ||||||||||||||||||||||
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:
This article will prove these results, in the § Mutual definability and § Negation is semantically equivalent to dual sections respectively.
Because of their semantics, i.e. the way they are commonly interpreted in classical propositional logic, conjunction and disjunction can be defined in terms of each other with the aid of negation, so that consequently, only one of them needs to be taken as primitive. [4] [1] For example, if conjunction (∧) and negation (¬) are taken as primitives, then disjunction (∨) can be defined as follows: [1] [8]
Alternatively, if disjunction is taken as primitive, then conjunction can be defined as follows: [1] [9] [8]
Also, each of these equivalences can be derived from the other one; for example, if (1) is taken as primitive, then (2) is obtained as follows: [1]
Since the Disjunctive Normal Form Theorem shows that the set of connectives is functionally complete, these results show that the sets of connectives and 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] If conjunction is taken as primitive, then (4) follows immediately from (1), while (5) follows from (1) via (3): [1]
Theorem: [4] [7] Let be any sentence in . (That is, the language with the propositional variables and the connectives .) Let be obtained from by replacing every occurrence of in by , every occurrence of by , and every occurrence of by . Then ⟚ . ( is called the dual of .)
Proof: [4] [7] A sentence of , where is as in the theorem, will be said to have the property if ⟚ . We shall prove by induction on immediate predecessors that all sentences of have . (An immediate predecessor of a well-formed formula is any of the formulas that are connected by its dominant connective; it follows that sentence letters have no immediate predecessors.) So we have to establish that the following two conditions are satisfied: (1) each has ; and (2) for any non-atomic , from the inductive hypothesis that the immediate predecessors of have , it follows that does also.
Assume . Then by uniform substitution of for . Hence, , by contraposition; so finally, , by the property that ⟚ , which was just proved above. [7] And since , it is also true that if, and only if, . [7] And it follows, as a corollary, that if , then . [7]
For a formula 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 . [10] [11] This provides a procedure for converting between conjunctive normal form and disjunctive normal form. [12] 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. [11]
Logical connectives | ||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
||||||||||||||||||||||
Related concepts | ||||||||||||||||||||||
Applications | ||||||||||||||||||||||
![]() | ||||||||||||||||||||||
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:
This article will prove these results, in the § Mutual definability and § Negation is semantically equivalent to dual sections respectively.
Because of their semantics, i.e. the way they are commonly interpreted in classical propositional logic, conjunction and disjunction can be defined in terms of each other with the aid of negation, so that consequently, only one of them needs to be taken as primitive. [4] [1] For example, if conjunction (∧) and negation (¬) are taken as primitives, then disjunction (∨) can be defined as follows: [1] [8]
Alternatively, if disjunction is taken as primitive, then conjunction can be defined as follows: [1] [9] [8]
Also, each of these equivalences can be derived from the other one; for example, if (1) is taken as primitive, then (2) is obtained as follows: [1]
Since the Disjunctive Normal Form Theorem shows that the set of connectives is functionally complete, these results show that the sets of connectives and 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] If conjunction is taken as primitive, then (4) follows immediately from (1), while (5) follows from (1) via (3): [1]
Theorem: [4] [7] Let be any sentence in . (That is, the language with the propositional variables and the connectives .) Let be obtained from by replacing every occurrence of in by , every occurrence of by , and every occurrence of by . Then ⟚ . ( is called the dual of .)
Proof: [4] [7] A sentence of , where is as in the theorem, will be said to have the property if ⟚ . We shall prove by induction on immediate predecessors that all sentences of have . (An immediate predecessor of a well-formed formula is any of the formulas that are connected by its dominant connective; it follows that sentence letters have no immediate predecessors.) So we have to establish that the following two conditions are satisfied: (1) each has ; and (2) for any non-atomic , from the inductive hypothesis that the immediate predecessors of have , it follows that does also.
Assume . Then by uniform substitution of for . Hence, , by contraposition; so finally, , by the property that ⟚ , which was just proved above. [7] And since , it is also true that if, and only if, . [7] And it follows, as a corollary, that if , then . [7]
For a formula 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 . [10] [11] This provides a procedure for converting between conjunctive normal form and disjunctive normal form. [12] 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. [11]