De Morgan’s Laws
De Morgan’s laws are two equivalences that relate negation, conjunction, and disjunction in logic and set theory. They tell you how to push a negation across a complex statement: the negation of an AND becomes an OR of negations, and the negation of an OR becomes an AND of negations. Formalized by the British mathematician Augustus De Morgan in the 1840s, they’re foundational in logic, set theory, Boolean algebra, digital circuit design, and database queries.
The Two Laws
For any two propositions \( P \) and \( Q \), or equivalently for any two sets \( A \) and \( B \):
First law: \( \neg(P \wedge Q) \equiv \neg P \vee \neg Q \). In set theory: \( \overline{A \cap B} = \overline{A} \cup \overline{B} \).
Second law: \( \neg(P \vee Q) \equiv \neg P \wedge \neg Q \). In set theory: \( \overline{A \cup B} = \overline{A} \cap \overline{B} \).
In words: ‘NOT (A AND B)’ is the same as ‘NOT A OR NOT B’; and ‘NOT (A OR B)’ is the same as ‘NOT A AND NOT B’.
Worked Examples in Plain English
Example 1. ‘It is not true that I have both an umbrella and a raincoat’ is logically the same as ‘I don’t have an umbrella OR I don’t have a raincoat’. (The first form rules out the both-true case; the second form says at least one of them is false — these mean the same thing.)
Example 2. ‘There is no one who is both rich and famous’ rewrites as ‘Everyone is not rich OR not famous’.
Example 3. ‘I don’t drink coffee or tea’ (negating an OR) means ‘I don’t drink coffee AND I don’t drink tea’.
Why They’re True: Truth Tables
For two propositions, there are four possible truth assignments. The truth table for \( \neg(P \wedge Q) \) gives the same column of values as the truth table for \( \neg P \vee \neg Q \) — they’re true in exactly the same cases. The other law works the same way. Truth tables aren’t elegant, but they’re conclusive.
| P | Q | P ∧ Q | ¬(P ∧ Q) | ¬P | ¬Q | ¬P ∨ ¬Q |
|---|---|---|---|---|---|---|
| T | T | T | F | F | F | F |
| T | F | F | T | F | T | T |
| F | T | F | T | T | F | T |
| F | F | F | T | T | T | T |
Columns 4 and 7 match — the first law is verified. The same procedure verifies the second law.
Set-Theoretic Form
For sets \( A \) and \( B \) inside a universe \( U \), the complement of an intersection equals the union of complements, and the complement of a union equals the intersection of complements:
$$ \overline{A \cap B} = \overline{A} \cup \overline{B}, \quad \overline{A \cup B} = \overline{A} \cap \overline{B} $$
The pictures (shaded Venn diagrams) for the two sides of each equation are identical, which is a visual proof.
Boolean Algebra and Digital Logic
In digital electronics, signals are represented by 0 and 1, and gates implement AND, OR, NOT. De Morgan’s laws translate directly:
$$ \overline{AB} = \overline{A} + \overline{B}, \quad \overline{A + B} = \overline{A} \cdot \overline{B} $$
In circuit terms: a NAND gate is equivalent to an OR gate with inverted inputs; a NOR gate is equivalent to an AND gate with inverted inputs. This equivalence is critical because real hardware factories typically build a chip using only NAND gates (or only NOR gates) — and De Morgan’s laws let designers express any logical function using one type of gate.
Applications
- Simplifying logic. De Morgan’s laws together with distributive and absorption laws let engineers reduce complex Boolean expressions to minimal forms — the basis of Karnaugh maps and Quine-McCluskey minimization.
- Database queries. ‘WHERE NOT (status = active AND priority = high)’ is equivalent to ‘WHERE status <> active OR priority <> high’. Rewriting via De Morgan’s laws often clarifies query intent and helps the optimizer choose better plans.
- Programming. The condition
!(a && b)is the same as!a || !b. Refactoring early-return conditions via De Morgan often makes branches easier to read. - Mathematical proof. Negating a ‘for all’ statement gives ‘there exists’ (and vice versa) when applied to predicates. The connection extends De Morgan’s laws to quantified logic: ¬∀x P(x) ≡ ∃x ¬P(x), and ¬∃x P(x) ≡ ∀x ¬P(x).
Related study notes: Set Theory, Boolean Algebra, Logic Gates, Truth Tables.
Frequently Asked Questions
What are De Morgan’s laws?
Two logical equivalences: (1) NOT (P AND Q) ≡ NOT P OR NOT Q; (2) NOT (P OR Q) ≡ NOT P AND NOT Q. In set theory: the complement of an intersection equals the union of complements; the complement of a union equals the intersection of complements. They tell you how to push a negation across a compound statement.
Who was De Morgan?
Augustus De Morgan (1806-1871) was a British mathematician who formalized these laws around 1847. He was a contemporary of George Boole and helped shape the modern field of mathematical logic. The laws were known earlier to medieval logicians and to George Boole, but De Morgan’s name stuck because of his 1847 systematic treatment.
How do De Morgan’s laws apply to programming?
The boolean expression !(a && b) is logically equivalent to !a || !b. Refactoring with De Morgan’s laws often makes conditional logic clearer — especially when you can flip a condition for an early-return or to avoid double negation. Useful in code review when simplifying compound boolean tests.
How do De Morgan’s laws relate to logic gates?
A NAND gate is functionally identical to an OR gate with inverted inputs; a NOR gate is identical to an AND gate with inverted inputs. This identity comes directly from De Morgan’s laws. Chip manufacturers often build everything from NAND (or NOR) alone, because that single gate plus De Morgan’s laws lets them implement any logical function.
Do De Morgan’s laws apply to quantifiers?
Yes — in predicate logic. The quantifier versions are: NOT (for all x: P(x)) ≡ there exists x with NOT P(x); and NOT (there exists x: P(x)) ≡ for all x: NOT P(x). These are very useful when proving statements by contradiction or contraposition.
Are De Morgan’s laws used in SQL?
Yes. The WHERE clause condition NOT (a = 1 AND b = 2) is equivalent to (a 1 OR b 2). Rewriting via De Morgan’s laws often makes complex WHERE clauses easier to read and can help the query optimizer choose better execution plans, particularly when conditions interact with indexes.