How to simplify Boolean expressions, in one line: find the collapses, apply them, stop when nothing else moves. A + AB looks like it needs an AND gate and an OR gate. It needs neither — absorption reduces the whole thing to plain A, and the gates come off the board.
What follows is the practical version: the eleven identities that do almost all the reducing, a full four-term reduction traced law by law, the De Morgan mistake that quietly breaks student circuits, and the point where a Karnaugh map beats algebra outright. Notation throughout uses a prime for complement, so A′ means NOT A — the same thing as an overbar on paper.
How to Simplify Boolean Expressions: Start With These Eleven Identities
Boolean algebra has more rules than this, but in practice a handful carry the load. Absorption and the complement law between them account for most real reductions; consensus is the one people forget and then wonder why their answer has an extra term.
| Law | AND form | OR form | What it buys you |
|---|---|---|---|
| Identity | A · 1 = A | A + 0 = A | Deletes tied-off inputs |
| Null | A · 0 = 0 | A + 1 = 1 | Kills a whole branch at once |
| Idempotent | A · A = A | A + A = A | Also runs backwards, to duplicate a term |
| Complement | A · A′ = 0 | A + A′ = 1 | The workhorse — removes a variable entirely |
| Involution | (A′)′ = A | Cancels double inverters | |
| Commutative | AB = BA | A + B = B + A | Reorder to expose a pattern |
| Associative | (AB)C = A(BC) | (A+B)+C = A+(B+C) | Regroup wide gates |
| Distributive | A(B+C) = AB + AC | A + BC = (A+B)(A+C) | The OR form has no arithmetic analogue — check it |
| Absorption | A(A+B) = A | A + AB = A | Deletes an entire redundant term |
| De Morgan | (AB)′ = A′ + B′ | (A+B)′ = A′B′ | Converts between NAND and NOR logic |
| Consensus | AB + A′C + BC = AB + A′C | Removes the term nobody notices is redundant | |
Two of these deserve a second look. Absorption is the one to hunt for first, because it deletes a term rather than shortening one. And the OR form of the distributive law, A + BC = (A+B)(A+C), has no equivalent in ordinary arithmetic — 2 + (3×4) is not (2+3)×(2+4) — which is exactly why it slips past people who are reasoning by analogy with numbers. Feed both sides to the truth table calculator once and it stops feeling strange.
One Reduction, Traced Law by Law
Here is the reduction worth memorising, because the trick inside it — deliberately duplicating a term — is the move most students never think to make.
F = A′BC + AB′C + ABC′ + ABC
Step 1. Idempotent law, backwards: ABC = ABC + ABC + ABC. Write the term three times.
F = (A′BC + ABC) + (AB′C + ABC) + (ABC′ + ABC)
Step 2. Distributive law, pulling the common factor out of each pair.
F = BC(A′ + A) + AC(B′ + B) + AB(C′ + C)
Step 3. Complement law: every bracket is 1.
F = BC · 1 + AC · 1 + AB · 1
Step 4. Identity law.
F = AB + AC + BC
That expression is the majority function: it outputs 1 whenever at least two of the three inputs are 1. Voting circuits and triple-redundant avionics use exactly this. The hardware difference is not cosmetic. The original form needs three inverters, four three-input AND gates and a four-input OR — eight gates. The reduced form needs three two-input ANDs and one three-input OR, and no inverters at all: four gates, half the count, and one less level of propagation delay.
Notice that step 1 makes the expression longer. Reduction is not monotonic, which is precisely why algebraic simplification is hard to do reliably by hand — you sometimes have to grow the expression to shrink it. If you want the answer without the archaeology, the Boolean algebra calculator applies these identities and shows which law fired at each step.
De Morgan's Theorems, and the Error That Ships Broken Circuits
The two theorems are short: (AB)′ = A′ + B′ and (A+B)′ = A′B′. Break the bar, change the sign. Break it, change it — both halves are mandatory, and skipping the second half is the single most common error in introductory digital logic.
The failure is easy to demonstrate. Take A = 1, B = 0. Then AB = 0, so (AB)′ = 1. Now do it wrong, distributing the bar without flipping the operator: A′B′ = 0 · 1 = 0. The correct De Morgan form A′ + B′ gives 0 + 1 = 1. One input combination out of four is wrong, which in a real design means a circuit that passes three quarters of your bench tests and then misbehaves in the field.
Why manufacturers care
De Morgan is what lets a fab build everything from one gate type. NAND is functionally complete — AND, OR and NOT can all be constructed from NAND alone — so a chip can be laid out with a single repeated cell instead of five different ones. Converting an AND-OR design into all-NAND form is a De Morgan exercise, applied bubble by bubble, and the logic gate simplifier handles that conversion directly.
The same two theorems appear in set theory as (A ∩ B)ᶜ = Aᶜ ∪ Bᶜ, which is why a Venn diagram is a legitimate way to check a Boolean identity — shade both sides and compare. If the algebra is not convincing you, drawing it in the Venn diagram calculator often is. Augustus De Morgan published the laws in the 1840s; Wikipedia's entry on De Morgan's laws covers the set-theoretic and propositional forms side by side.
Where Algebra Stops Being the Fast Route
Past three variables, algebraic manipulation turns into a search problem — you are hunting for a factoring you cannot see. A Karnaugh map removes the searching by rearranging the truth table so that adjacent cells differ in exactly one variable. Anything you can circle is a term you can simplify, and the circling is visual rather than deductive.
The row and column labels run in Gray-code order — 00, 01, 11, 10, never 00, 01, 10, 11 — because that ordering is what makes neighbours differ by a single bit. Take F(A,B,C,D) = Σm(0, 2, 5, 7, 8, 10, 13, 15), eight minterms out of sixteen:
| AB \ CD | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 00 | 1 | 0 | 0 | 1 |
| 01 | 0 | 1 | 1 | 0 |
| 11 | 0 | 1 | 1 | 0 |
| 10 | 1 | 0 | 0 | 1 |
Amber: the four corners group to B′D′. Green: the centre block groups to BD.
Two groups of four cover all eight ones. The amber group is the four corners — legal, because a K-map wraps around top-to-bottom and left-to-right like the surface of a torus, which is the rule beginners most often refuse to believe. Across those four cells B = 0 and D = 0 while A and C both vary, so the term is B′D′. The green block in the centre has B = 1 and D = 1 throughout, giving BD.
So F = B′D′ + BD, which is XNOR(B, D) — the function ignores A and C completely. Eight four-literal minterms became two two-literal terms, or a single XNOR gate if your library has one. Getting there algebraically is possible but nobody would find it quickly.
The four grouping rules, in order of how often they are broken
- Groups must be a power of two in size: 1, 2, 4, 8, 16. A group of six is not a group.
- Groups wrap around all four edges, and the four corners count as one group of four.
- Groups may overlap. Reusing a cell costs nothing and usually shortens a term.
- Make every group as large as legally possible before you make more of them — each doubling in size removes one literal.
Minterm numbering is just binary counting, so m10 is ABCD = 1010, meaning A·B′·C·D′. If converting index to bit pattern is slowing you down, the binary to decimal calculator handles the arithmetic while you concentrate on the grouping.
Algebra, K-Map, or Quine–McCluskey?
Three methods, three different failure modes. Pick by variable count first, then by whether you actually need a provably minimal answer or merely a shorter one.
| Method | Practical range | Minimal result? | Use it when |
|---|---|---|---|
| Algebraic laws | 1–3 variables | No guarantee | The structure is visible, or you need to show working |
| Karnaugh map | 2–4 comfortably, 5–6 stacked | Yes, if you group correctly | Exam questions and most real 4-input logic |
| Quine–McCluskey | Any n, but brutal by hand past 6 | Yes, provably | You need a guarantee and have a computer |
| Espresso heuristic | Dozens of variables | Near-minimal, not proven | Actual chip synthesis — this is what EDA tools run |
The scaling is the whole story. A K-map for n variables has 2ⁿ cells: 16 for four variables, 64 for six, 1,024 for ten. Human pattern recognition gives out somewhere around 5 or 6, which is exactly where Quine–McCluskey takes over — it is the same minimisation done as a table instead of a picture, so a machine can execute it. Beyond about 15 variables even that becomes impractical and synthesis tools switch to Espresso, which trades the proof of minimality for a result you can get before lunch.
Count the Zeros Before You Start
Every function can be written two ways. Sum of products (SOP) ORs together AND terms, one per 1 in the truth table: AB + A′C. Product of sums (POS) ANDs together OR terms, one per 0: (A + B)(A′ + C). Both are correct; they are rarely the same size.
The shortcut nobody mentions in class: group whichever output value is rarer. Consider F(A,B,C,D) = Σm(0,1,2,4,5,6,8,9,10,12,13,14) — twelve ones. Grouping twelve cells for an SOP is tedious. But the function is 0 only at minterms 3, 7, 11 and 15, and those four all have C = 1 and D = 1. So F′ = CD, and therefore F = (CD)′ = C′ + D′.
One OR gate and two inverters. Twelve minterms, and the answer has two literals — found by looking at four cells instead of twelve. Whenever the ones outnumber the zeros roughly two to one or worse, simplify the complement and invert at the end.
There is a physical reason to care beyond gate count. In CMOS, NAND gates are cheaper than NOR gates of the same fan-in, because PMOS transistors carry current worse than NMOS and a NOR stacks its PMOS devices in series. A NAND-friendly SOP form is usually faster silicon than the equivalent POS form, even at identical literal counts. That asymmetry is why synthesis tools bias toward SOP even when POS looks tidier on paper.
A Simplification Is a Claim — Test It
Two Boolean expressions are equal if and only if their truth tables match on every row. That is a finite check: 8 rows for three variables, 16 for four, 32 for five. Unlike most of mathematics, exhaustive verification here is not just possible, it is quick — so there is no excuse for shipping an unverified reduction.
Build the table for the original and the simplified form side by side and compare columns. If a single row disagrees, the error is almost always one of three things: a dropped complement, De Morgan applied to only half the expression, or a K-map group that was not a power of two. Run both expressions through the truth table calculator, or check the reduction directly in the Boolean algebra calculator, which reports the intermediate forms as well as the final one.
One last caveat worth knowing before you trust a minimal answer in hardware. A minimal SOP can contain a static hazard: a brief incorrect output glitch when two inputs change at nearly the same instant and the circuit momentarily passes through no covering term. The fix is to add back a redundant term — usually the consensus term you just deleted — which costs a gate and buys glitch-free switching. Minimal on paper and correct in silicon are not always the same target.
