De Morgan's Laws

(A · B)′ = A′ + B′

Not (both) is (not one) or (not the other).

(A + B)′ = A′ · B′

Not (either) is (not one) and (not the other).

The mnemonic that actually works: break the bar, change the sign. Break the overbar over the whole expression into two overbars over the parts, and flip the operator between them. The page opens on (AB + C)', which needs both laws in order — (A · B)′ · C′ by De Morgan, then (A′ + B′) · C′ by De Morgan — and lands on (A′ + B′) · C′.

Two proofs, because two audiences want different ones. By truth table is complete and checkable in ten seconds: four rows for each law, both columns and an agreement column. Every row below was computed by the engine when this page was built, and a law whose two sides stopped agreeing would fail the build rather than appear here as a false proof.

❌ Wrong: (A + B)′ = A′ + B′. A complement is not a factor and does not distribute over the operator underneath it — the operator itself changes. One disagreeing row is a proof and a paragraph is not: A = 0, B = 1 gives (A + B)′ = 0 but A′ + B′ = 1.

✅ Right: (A + B)′ = A′ · B′.

De Morgan drawn instead of written — the same law, applied to a schematic. Four rewrites on the diagram:

1. Two bubbles on one wire annihilate. That is Involution, drawn.
2. A gate with an output bubble is the other gate with input bubbles. A NAND is an OR with both inputs inverted; a NOR is an AND with both inputs inverted.
3. A two-level AND–OR network becomes NAND–NAND by inserting a bubble pair on every AND→OR wire. Nothing changes: each pair cancels.
4. The dual holds for OR–AND, which becomes NOR–NOR the same way.

This is what makes NAND and NOR universal, and it is why IEEE Std 91 gives every gate an alternative symbol. Draw any expression and watch the bubbles move.

!(a && b) is !a || !b, and !(a || b) is !a && !b. Getting it wrong is a real bug, not only a lost mark — inverting a compound guard by adding one ! at the front and leaving the operator alone is one of the most common conditional errors there is.

Note that | in this toolkit is OR, never the Sheffer stroke. In pure logic notation the bar is NAND; in every programming language it is OR, and that is the reading almost everyone arrives with.

The same shape holds for set complement — (A ∪ B)ᶜ = Aᶜ ∩ Bᶜ and (A ∩ B)ᶜ = Aᶜ ∪ Bᶜ — and for quantifiers — ¬∀x P(x) ≡ ∃x ¬P(x) and ¬∃x P(x) ≡ ∀x ¬P(x) — because all three are Boolean algebras or behave like them. This is a digital-logic tool and not a set-theory one: the paragraph is here because those searches land here, and it does not pretend to be more. The truth-table generator handles the propositional half of that syllabus.

The dual swaps · with + and 0 with 1 and leaves the literals alone. The complement does that and complements every literal: f ᵈ(x) = f′(x′), which is not f′. Confusing them is why a minimal POS must be derived by minimising the OFF-set and De Morganing each cube, and never by dualising the minimal SOP. Duality, in full.

The tool pushes negations through AND, OR, XOR, XNOR, NAND, NOR, implication and the biconditional. The derived operators are expanded to their definitions first, and the page names that step rather than performing it silently — so (A ⊕ B)′ begins with Definition of XOR and only then applies De Morgan.

The step-by-step derivation is limited to 6variables. Above that the answer, the truth-table check and the minimal forms are still exact — the answer comes from the engine's pushNegationsIn, which has no variable limit — and the page says so where the steps would have been rather than truncating quietly.

It does not minimise unless you ask. Negation normal form and minimal SOP are different destinations: this page opens on (AB + C)', whose NNF is (A′ + B′) · C′, whose minimal SOP is A′ · C′ + B′ · C′ and whose minimal POS is C′ · (A′ + B′) — with Σm(0, 2, 4) and ΠM(1, 3, 5, 6, 7). All of those numbers are computed by the engine at build time.