De Morgan's Laws
What you'll learn: How to correctly negate logical AND and OR operations—a critical skill for writing correct conditions in programming and digital logic.
What Are De Morgan's Laws?
De Morgan's Laws are two simple but powerful rules that tell you how negation (NOT) interacts with conjunction (AND) and disjunction (OR). They're named after mathematician Augustus De Morgan, and they appear everywhere in computer science.
The two laws state:
- NOT (A AND B) = (NOT A) OR (NOT B)
- NOT (A OR B) = (NOT A) AND (NOT B)
In symbolic notation:
¬(A ∧ B) ≡ (¬A) ∨ (¬B)¬(A ∨ B) ≡ (¬A) ∧ (¬B)
Why This Matters
Think of it this way: When you negate a compound statement, you flip both the individual parts AND swap the connector.
Example 1: "It is NOT true that (I'm hungry AND tired)" means "I'm NOT hungry OR I'm NOT tired" (at least one condition fails).
Example 2: "It is NOT true that (the door is open OR the window is open)" means "the door is NOT open AND the window is NOT open" (both must be closed).
In Computer Science
De Morgan's Laws help you:
- Simplify Boolean expressions in circuits and code
- Negate complex conditions correctly
- Convert between NAND/NOR gates and other logic gates
- Debug logical errors when conditions seem backwards
Without these laws, you might incorrectly negate (A AND B) as (NOT A AND NOT B)—which gives completely different results!
Key Takeaway: De Morgan's Laws let you correctly negate AND/OR operations by flipping each part and swapping the operator—essential for logical reasoning in CS.