De Morgan's laws & simplifying conditions

There is one logic mistake that shows up in production code more than any other, and it takes a single line to make. Someone needs the opposite of “logged in and has credit”, writes “not logged in and not has credit”, ships it, and a whole class of users slips through the check. The fix is a pair of equivalences named after Augustus De Morgan, and once you have them they change how you read every compound condition.

The two laws

¬(p ∧ q) ≡ ¬p ∨ ¬q

¬(p ∨ q) ≡ ¬p ∧ ¬q

In words: the negation of “both” is “at least one fails”, and the negation of “either” is “both fail”. The negation moves inward onto each operand, and as it passes through, the connective flips — ∧ (and) becomes ∨ (or), ∨ becomes ∧.

Why the flip? Think about what each connective demands. A conjunction wants everything to succeed, so the cheapest way to defeat it is a single failure — that is an “or” over failures. A disjunction wants only one success, so defeating it means knocking out every operand — that is an “and” over failures. Negation swaps “all” for “at least one”. Everything else follows.

If you want proof rather than intuition, build the table:

The fourth and seventh columns are identical, in all four rows. That is what logical equivalence means, and it is why the substitution is always safe.

Why the naive version is wrong

Compare ¬(p ∧ q) with the tempting ¬p ∧ ¬q. The first is true in three rows; the second in one — only when both operands are false. They agree in exactly that one row and disagree in two of the other three.

Translated back to the example: “not (logged in and has credit)” should catch a logged-out user with credit, and a logged-in user without credit, and a logged-out user without credit. “not logged in and not has credit” catches only the last. The bug is invisible in testing if your test data happens to fail both conditions together, which is depressingly common.

The rule of thumb: when a negation crosses a connective, the connective changes. If you rewrote a condition and every and stayed an and, you probably made a mistake.

The recipe, and its companions

To negate any compound condition: negate each operand, and flip every connective. Apply it recursively until no negation sits outside a bracket. Comparisons negate too — the opposite of a < b is a >= b, not a > b, which is its own well-worn source of off-by-one bugs.

Three laws travel with De Morgan and finish most simplifications:

• Double negation: ¬(¬p) ≡ p. Two negations cancel, which is what makes the recursive recipe terminate cleanly.
• Distribution: p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r), and p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r). Unlike arithmetic, where only multiplication distributes over addition, in logic each connective distributes over the other.
• Negating a conditional: ¬(p → q) ≡ p ∧ ¬q. Rewrite p → q as ¬p ∨ q, De Morgan it into p ∧ ¬q. A promise is broken only by a true antecedent with a false consequent — no “if” survives in the negation.

Refactoring a tangled condition

Guard clauses are where these laws earn their keep, because a guard is the negation of the condition you actually want.

// Before: deeply nested, hard to scan.
function submitOrder(order) {
  if (order.isValid && order.hasStock && !order.isFrozen) {
    charge(order);
  }
}

// After: negate the whole condition to get the guard.
// ¬(valid ∧ stock ∧ ¬frozen) ≡ ¬valid ∨ ¬stock ∨ frozen
function submitOrder(order) {
  if (!order.isValid || !order.hasStock || order.isFrozen) return;
  charge(order);
}

Notice the third term: !order.isFrozen was already negated, so double negation turned it back into a plain order.isFrozen. Every && became ||. If your inverted guard still reads as a chain of &&, check it again.

The same laws, three other places

Sets. Complement behaves exactly like negation, union like ∨, intersection like ∧. So the complement of A ∪ B is A' ∩ B', and the complement of A ∩ B is A' ∪ B'. The Venn picture makes it obvious: everything outside two overlapping circles is outside the first and outside the second.

SQL. NOT (status = 'active' AND verified) filters the same rows as status <> 'active' OR NOT verified. Query planners perform this rewrite for you when pushing predicates down, which is why a NOT (... OR ...) can suddenly become index-friendly once it is turned into a conjunction. One caution: SQL is three-valued, so a NULL comparison yields UNKNOWN rather than TRUE or FALSE, and NOT UNKNOWN is still UNKNOWN — the laws hold, but NULL rows fail the WHERE clause either way.

Quantifiers. ¬∀x P(x) ≡ ∃x ¬P(x) and ¬∃x P(x) ≡ ∀x ¬P(x). “Not everything is valid” means “something is invalid”. This is the array-method version you already use: the negation of items.every(inStock) is items.some(x => !inStock(x)), never items.every(x => !inStock(x)).

Hardware. NAND is ¬(p ∧ q) and NOR is ¬(p ∨ q). By De Morgan a NAND gate is equally an OR gate with inverted inputs, which is exactly the substitution chip designers use to build whole circuits from one gate type.

Four domains, one pair of equivalences. Learn the flip once and you have debugged a lifetime of conditions.