De Morgan's laws
De Morgan's laws describe the interaction between negation, conjunction, and disjunction.
They provide rules for transforming logical statements into equivalent forms.
Statements
- ¬(p ∧ q) ≡ ¬p ∨ ¬q
- ¬(p ∨ q) ≡ ¬p ∧ ¬q
Explanation
Negating a conjunction is equivalent to the disjunction of the negations.
Negating a disjunction is equivalent to the conjunction of the negations.
These transformations are widely used in proofs, algebraic simplifications, and computer science.
Examples
- "It is not the case that (I study AND I work)"
≡ "I do not study OR I do not work".
- "It is not the case that (I travel OR I rest)"
≡ "I do not travel AND I do not rest".
Truth Table (First Law)
| p |
q |
p ∧ q |
¬(p ∧ q) |
¬p ∨ ¬q
|
| T |
T |
T |
F |
F
|
| T |
F |
F |
T |
T
|
| F |
T |
F |
T |
T
|
| F |
F |
F |
T |
T
|
Truth Table (Second Law)
| p |
q |
p ∨ q |
¬(p ∨ q) |
¬p ∧ ¬q
|
| T |
T |
T |
F |
F
|
| T |
F |
T |
F |
F
|
| F |
T |
T |
F |
F
|
| F |
F |
F |
T |
T
|