Two logical formulas are equivalent when they take the same truth value for every combination of their variables. Knowing a small repertoire of equivalences lets you turn a complicated condition into a simpler one, with the certainty that you have not changed its behaviour. Of all of them, De Morgan's laws are the ones used most often, especially when a condition has to be negated.
De Morgan's laws
The two laws say how to negate a conjunction and a disjunction:
- ¬(p ∧ q) ≡ ¬p ∨ ¬q
- ¬(p ∨ q) ≡ ¬p ∧ ¬q
In words: the negation "moves inside" the parentheses, negates each term and swaps ∧ with ∨. "It is not true that the file is readable and writable" is equivalent to "the file is not readable or it is not writable". "It is not true that it is raining or snowing" is equivalent to "it is not raining and it is not snowing".
The laws extend to any number of terms: ¬(p ∧ q ∧ r) ≡ ¬p ∨ ¬q ∨ ¬r. They also hold for sets, where the complement of an intersection is the union of the complements, and for circuits, where a NAND gate is equivalent to an OR with inverted inputs.
The repertoire of equivalences
| Name | Equivalence |
|---|---|
| Double negation | ¬¬p ≡ p |
| Commutative | p ∧ q ≡ q ∧ p; p ∨ q ≡ q ∨ p |
| Associative | (p ∧ q) ∧ r ≡ p ∧ (q ∧ r) |
| Distributive | p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r) |
| Dual distributive | p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r) |
| Idempotence | p ∧ p ≡ p; p ∨ p ≡ p |
| Absorption | p ∨ (p ∧ q) ≡ p; p ∧ (p ∨ q) ≡ p |
| Identity | p ∧ T ≡ p; p ∨ F ≡ p |
| Domination | p ∨ T ≡ T; p ∧ F ≡ F |
| Complement | p ∨ ¬p ≡ T; p ∧ ¬p ≡ F |
| Implication | p → q ≡ ¬p ∨ q |
Each one can be checked with a truth table. Notice the symmetry: every law has a "dual" version obtained by swapping ∧ with ∨ and T with F. This is a general property of Boolean algebra.
A step-by-step simplification
Suppose you find this condition in some code:
not (user_active and not subscription_expired) or not user_active
Let a = user_active and s = subscription_expired. The formula is ¬(a ∧ ¬s) ∨ ¬a.
- De Morgan on the first part: ¬a ∨ ¬¬s ∨ ¬a.
- Double negation: ¬a ∨ s ∨ ¬a.
- Commutativity and idempotence: ¬a ∨ s.
The result, not user_active or subscription_expired, is much more readable. It can also be reread as an implication: a → s, that is, "if the user is active, then the subscription has expired". This kind of rereading often helps you see whether the original condition really expressed what its author intended, or whether it hid a bug.
The most common mistake: negating halfway
When a condition has to be inverted, for instance to turn an if into an early return, the typical mistake is to negate the terms without swapping the operator:
# original condition: proceed if age >= 18 and document is valid
if age >= 18 and document_valid:
proceed()
# WRONG early return
if age < 18 and not document_valid:
return
# CORRECT early return (De Morgan)
if age < 18 or not document_valid:
return
The wrong version lets a minor with a valid document through. Errors like this are insidious because the code looks reasonable at a quick glance. When I review code, negated access checks are among the places I always recheck with De Morgan in hand.
Equivalences and SQL
The same laws apply to WHERE clauses, with one caveat: SQL has the NULL value, which introduces three-valued logic (true, false, unknown). De Morgan's laws still hold there, but NOT (column = 5) does not return the rows where the column is NULL, because comparing with NULL gives "unknown" and its negation is still "unknown". Anyone simplifying a query must therefore take missing values into account, adding OR column IS NULL where needed.
Why simplify
A shorter condition is not merely more elegant:
- it is easier to read and review;
- it reduces the risk of errors when someone changes it later;
- in hardware it translates into fewer logic gates;
- in testing, it makes clearer which cases need covering.
Be careful not to overdo it, though: sometimes the shortest form is less expressive than a slightly longer one that mirrors the business rule. The goal is clarity, not the smallest number of symbols.
In short
- De Morgan's laws negate conjunctions and disjunctions by swapping ∧ and ∨ and negating each term.
- A repertoire of about ten equivalences is enough to simplify almost any real condition.
- Every law has a dual, obtained by swapping ∧ with ∨ and true with false.
- The typical mistake is negating the terms without changing the operator, especially in early returns.
- In SQL, remember that NULL introduces a third truth value.
