De Morgan's laws Glossary
Definition
De Morgan's laws are logical equivalences relating conjunction and disjunction by using the properties of classical negation. A negated conjunction is equivalent to the disjunction of the negated conjuncts, and dually a negated disjunction is equivalent to the conjunction of the negated disjuncts. That is:
NOT(p AND q)
⊣⊢ NOTp OR
NOTq
NOT(p OR q)
⊣⊢ NOTp AND
NOTq
Comments
By substituting negated atoms for atoms and appealing to double negation, we reach other versions:
NOT(p AND NOTq)
⊣⊢ NOTp OR
q
NOT(NOTp OR NOTq)
⊣⊢ p AND q
etc.
Systems of logic sometimes allow De Morgan's laws to be used as steps of immediate consequence in derivations. This gives an easy treatment of negation, but it breaks the general pattern of supplying each connective with an introduction rule and an elimination rule.
The universal and existential quantifiers form a dual pair, just like conjunction and disjunction, so they too give rise to a pair of equivalences allowing negation to be moved inside or outside:
NOTALLx Fx
⊣⊢ SOMEx
NOTFx
NOTALLx Fx
⊣⊢ SOMEx
NOTFx