De Morgan's Laws
Logical identities used in propositional logic and in set theory that were formulated by British mathematician Augustus De Morgan.
- In propositional logic, these identities are stated as follows :
- The negation of a conjunction of two propositions is a disjunction of the negations of the two propositions, which means that "not(P and Q)" is "(not P) or (not Q)" : ¬(P ∧ Q) = ¬P ∨ ¬Q.
- The negation of a disjunction of two propositions is a conjunction of the negations of the two propositions, which means that "not(P or Q)" is "(not P) and (not Q)" : ¬(P ∨ Q) = ¬P ∧ ¬Q
- In set theory, these identities are stated as follows :
Consider the set U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} and the subsets A = {5, 6, 7, 8, 9, 10} and B = {2, 3, 4, 5, 6, 7}.
- Since A ∩ B = {5, 6, 7} then (A ∩ B)' = {1, 2, 3, 4, 8, 9, 10} and since A' = {1, 2, 3, 4} and B' = {1, 8, 9, 10} then A' ∪ B' = {1, 2, 3, 4, 8, 9, 10}. Therefore : (A ∩ B)' = A' ∪ B'.
- Similarly, since A ∪ B = {2, 3, 4, 5, 6, 7, 8, 9, 10}, then (A ∪ B)' = {1} and A' ∩ B' = {1}. It may also be noted that (A ∪ B)' = A' ∩ B'.
Example
In propositional logic :- The negation of "It is cold and the sky is grey" is "It is not cold or the sky is not grey".
- The negation of "It is cold or the sky is grey" is "It is not cold and the sky is not grey".