De Morgan's laws
From Mathematics
De Morgan's laws are a pair of simple statements relating disjunction and conjunction in formal logic. Specifically:
- The negation of the conjunction of two statements is logically equivalent to the disjunction of their negations.
- The negation of the disjunction of two statements is logically equivalent to the conjunction of their negations.
Since the English description is obviously very unwieldy, they are better described here in terms of logical operators, respectively:
Both of these laws can easily be verified using truth tables:
 |  |  | 
|
|---|---|---|---|
| T | T | F | F |
| T | F | T | T |
| F | T | T | T |
| F | F | T | T |
| | |  | 
|
|---|---|---|---|
| T | T | F | F |
| T | F | F | F |
| F | T | F | F |
| F | F | T | T |
[edit] Application of De Morgan's Laws
Even though De Morgan's laws seem useless at the outset, they are really an important part of the logician's toolbox.[1] Here is an example of a short formal logical proof which relies strongly on DeMorgan's surprisingly important discovery:
(2, Add.)
(3, De M.)
(1,4, M.T.)
(5, De M.)
(6, Com.)
(7, Simp.)
De Morgan's first law is used twice in this proof. ('De Morgan' is conventionally shortened to 'De M.' in logical proofs.) In the first instance, the premiss 
is used to form the disjunctive statement —perfectly legal in formal logic—and then transformed into its conjunctive form with the first law. This form easily demonstrates the negation of 
through the principle of modus tollens, and since is also a candidate for transformation through De Morgan's first law, it becomes . then follows trivially from this statement. De Morgan's laws are a powerful tool for simplifying proofs greatly, not only for humans, but for automated theorem provers as well.
[edit] Notes
- ↑ Probably the ball peen hammer.
