Digital Logic Toolkit — Boolean algebra simplifier
Boolean Algebra Simplifier
Simplify any expression to its minimal SOP and POS, one named law at a time.
Accepts + · ' ¬ ∧ ∨ ⊕ ~ ! & | and the words AND, OR, NOT, XOR.
Check how this was read
- Read "AB" as A · B — 2 variables ANDed together. Declare "AB" as a variable name if you meant one variable.
- Read "BC" as B · C — 2 variables ANDed together. Declare "BC" as a variable name if you meant one variable.
read as ((A · B) + (¬A · C) + (B · C))
Notation ▾
This tool reads + as OR, juxtaposition as AND and a trailing ' as NOT, and it always echoes the fully parenthesised reading it used. The full notation and precedence table is below.
Bookkeeping steps are pure commutative and associative reorderings. They are folded onto the step that follows them unless you ask for them.
Start from a worked example
Step-by-step simplification
Minimal SOP
A · B + A′ · C
A · B + A′ · C + B · C simplifies to A · B + A′ · C in 1 step. That is a proven minimum (2 terms, 4 literals), not a best effort. It is the only minimum-cost form.
Hide the 1 step
Step 1, Consensus
A · B + A′ · C + B · C = A · B + A′ · Cwith
A=A,B=B,C=CA · B + A′ · C + B · C
becomes A · B + A′ · C
The consensus term is implied by the two terms it was formed from, so deleting it cannot change a single row.
Why this is the minimum
The minimum was computed first, by the Quine–McCluskey algorithm with Petrick’s method for the covering step; the steps above are then a named-law path to that already-proven answer.
Commutativity and associativity are handled by canonicalising each product term as a sorted set of literals, which is why there are no pointless “apply the commutative law” steps to read past.
The prime implicants and the covering step for this function are shown in full on the Quine–McCluskey page.
Minimal forms
Minimal SOP
A′ · C + A · B
Minimal POS
(A + C) · (A′ + B)
They cost the same here — 2 terms · 4 literals as a sum of products, 2 terms · 4 literals as a product of sums.
Why you can trust the count
Two pipelines run over the same prime-implicant chart. The walkthrough uses essential primes, then minterm (“row”) dominance, then implicant (“column”) dominance, then Petrick’s method — the sequence a textbook shows, which reaches one correct answer.
The list of every minimum cover is produced by a second pipeline that uses essentials and minterm dominance only. Essential-prime extraction is safe for enumeration and minterm dominance is safe; implicant dominance is not — striking out a dominated prime discards every cover that used it, and some of those cost exactly the minimum.
So the walkthrough answers “what is an optimum?” and the list answers “what are all the optima?”. Both are shown because the textbook shows the first and the truth is the second.
Notation and operator precedence used here
Every operator can be written several ways, and all the spellings below are equivalent. Input is Unicode-NFKC-normalised before parsing, so a full-width Ａ and a plain A are the same variable.
| Operation | Accepted input | Rendered as |
|---|---|---|
| NOT | A', !A, ~A, ¬A, NOT A, Ā | A′ |
| AND | A·B, A*B, A&B, A&&B, A∧B, A AND B, AB | A · B |
| OR | A+B, A|B, A||B, A∨B, A OR B | A + B |
| XOR | A^B, A⊕B, A⊻B, A XOR B | A ⊕ B |
| XNOR | A@B, A⊙B, A XNOR B | A ⊙ B |
| NAND | A↑B, A NAND B | A ↑ B |
| NOR | A↓B, A NOR B | A ↓ B |
| IMPLIES | A->B, A=>B, A→B | A → B |
| IFF | A<->B, A<=>B, A↔B, A≡B | A ↔ B |
| Constants | 0, 1, F, T, FALSE, TRUE, ⊥, ⊤ | 0, 1 |
Precedence. Highest to lowest: ( ) → postfix ′ and prefix NOT → AND (including juxtaposition) → XOR / XNOR → NAND / NOR → OR → IMPLIES (right-associative) → IFF. That matches the Wolfram Language and the C family. It is not universal — VHDL gives every logical operator the same precedence and refuses to guess — so this tool echoes the fully parenthesised reading of whatever you type and warns, without blocking, whenever XOR, XNOR, NAND or NOR is mixed with AND or OR outside brackets.
Three rules that surprise people.
- The overbar is a grouping symbol: its extent is its operand, and plain text cannot express that. Type
'or¬( … ); overbars are drawn on output only. - Postfix
'binds to the single item immediately before it, soAB'is A·(B′),(A+B)'complements the whole group, andA''is A. |means OR here, never the Sheffer stroke. NAND is↑or the wordNAND.
Variable names. Single letters, optionally followed by digits or an underscore subscript (A, B, X1, x_2), and case-sensitive. With single-letter names juxtaposition means AND, so AB is A·B.
What “simplest” means, and why the answer might not be unique
Three cost models exist and they disagree: product-term count (one AND gate each), literal count (roughly one transistor pair each) and gate-input count, the model most modern courses use for area. The standard textbook objective is lexicographic — fewest product terms first, then fewest literals — which is exactly what Berkeley's Espresso guarantees in exact mode, and it is the default here.
A function can have several covers that tie under one model and separate under another, and several that tie under all of them. When that happens this page shows every one of them rather than picking one and implying it is the answer.
How the simplification is computed
The minimum is found first, by Quine–McCluskey with Petrick's method for the covering step, so the answer is proven before any prose is written. The named-law steps are then a path to that known target rather than a greedy search that might stop short. That is why no answer here is ever hedged: the one permitted qualification is the cost badge naming the Espresso heuristic when the exact path was not taken.
The page opens on AB + A'C + BC, whose proven minimum is A′ · C + A · B — 2 terms · 4 literals, and the only cover of that cost. Those numbers are computed at build time by the same engine call the browser makes, so the static HTML and the live tool cannot disagree.
Commutativity and associativity are handled by canonicalising each product term as a sorted set of literals, which is why you will not see six pointless “apply the commutative law” steps. Above eight variables the exact path moves to a cancellable background solve, and above twelve it becomes the Espresso heuristic — labelled as a heuristic, never as exact.
The laws used, at a glance
| Law | Form | Dual |
|---|---|---|
| Identity | a · 1 = a | a + 0 = a |
| Null | a · 0 = 0 | a + 1 = 1 |
| Idempotent | a · a = a | a + a = a |
| Complement | a · a′ = 0 | a + a′ = 1 |
| Involution | (a′)′ = a | self-dual |
| Commutative | a · b = b · a | a + b = b + a |
| Associative | (a·b)·c = a·(b·c) | (a+b)+c = a+(b+c) |
| Distributive | a·(b + c) = a·b + a·c | a + b·c = (a + b)·(a + c) |
| Absorption | a + a·b = a | a · (a + b) = a |
| Redundancy (second absorption) | a + a′·b = a + b | a · (a′ + b) = a · b |
| Consensus | a·b + a′·c + b·c = a·b + a′·c | (a+b)·(a′+c)·(b+c) = (a+b)·(a′+c) |
| De Morgan | (a · b)′ = a′ + b′ | (a + b)′ = a′ · b′ |
| Adjacency | a·b + a·b′ = a | (a + b)·(a + b′) = a |
| Shannon expansion | f = a · f|ₐ₌₁ + a′ · f|ₐ₌₀ | f = (a + f|ₐ₌₀)·(a′ + f|ₐ₌₁) |
Absorption (a + a·b = a) and redundancy (a + a′·b = a + b) are different laws with different names. The first deletes a term outright; the second keeps it and throws away one literal. Filing the second under “absorption” is the most common error in this field, including in the market-leading calculator.
Common problem-set patterns
| Input | The law that cracks it | Answer |
|---|---|---|
| A·B + A·B′ | Adjacency (factor and cancel) | A |
| A + A′·B | Redundancy | A + B |
| A·B + A′·C + B·C | Consensus | A·B + A′·C |
| A·B + A·(B + C) + B·(B + C) | Distributive, then absorption | B + A·C |
Mistakes this calculator will catch
- Wrong: (A + B)′ = A′ + B′ — Right: (A + B)′ = A′ · B′
- Wrong: A + A·B = A·B — Right: A + A·B = A
- Wrong: AB′ means (A·B)′ — Right: AB′ means A·(B′)
- Wrong: a minimal form is always unique — Right: a function can have several, all correct
Limits, stated plainly
Exact minimisation to eight variables instantly and to twelve in a background solve you can cancel; above twelve the Espresso heuristic, labelled as such by the cost badge. The Karnaugh map view stops at six variables and says so rather than silently clamping. There is no sequential logic here: a feedback loop is detected and reported on the circuit page, never unrolled.
Worked examples
Worked examples
- A·B + A·B̄introadjacency; 1 term, 1 literal
- A + A·Bintroabsorption; 1 term, 1 literal
- A·B + Ā·C + B·Ccoreconsensus; the B·C term is redundant
- (A + B)·(A + B̄)corePOS adjacency; dual of example 1
- A·(Ā + B)coredistribution then null law
- (A + B)′coreDe Morgan; NOR expands to Ā·B̄
- Ā·B̄·C + Ā·B·C + A·B·Ccoretwo 2-literal terms
- A ⊕ B ⊕ Ccoreirreducible: 4 minterms, no adjacency
- (A + B)·(Ā + C)·(B + C)coreconsensus in POS; (B + C) is redundant
- Ā·B̄·C̄ + Ā·B̄·C + Ā·B·C̄ + A·B·C̄examone 2-literal and one 2-literal term
- X·Y + X̄·Z + Y·Z̄examabsorption after consensus; Y absorbs two terms
- A·B + Ā·C + B·C + A·B·Dedge caseconsensus and absorption together; 2 terms
Related
- Boolean algebra laws and theorems — every law used above, with proofs
- De Morgan's laws — the one law students get backwards
- Karnaugh map solver — see this simplification as a grouped map
- Quine–McCluskey solver — the algorithm behind the answer, with its tables
- SOP and POS canonical forms — canonical forms and minterm/maxterm lists
- Logic gate diagram builder — build the minimised circuit
- Truth table generator — check the result row by row
- Universal gates — NAND-only and NOR-only versions of this result
Sources
- Boole, George. An Investigation of the Laws of Thought, on Which are Founded the Mathematical Theories of Logic and Probabilities. London: Walton and Maberly, 1854.
- Huntington, Edward V. “Sets of Independent Postulates for the Algebra of Logic.” Transactions of the American Mathematical Society 5, no. 3 (1904): 288–309. doi:10.2307/1986459.
- Shannon, Claude E. “A Symbolic Analysis of Relay and Switching Circuits.” Transactions of the American Institute of Electrical Engineers 57, no. 12 (December 1938): 713–723. doi:10.1109/T-AIEE.1938.5057767.
- Quine, Willard V. “The Problem of Simplifying Truth Functions.” The American Mathematical Monthly 59, no. 8 (October 1952): 521–531. doi:10.2307/2308219.
- McCluskey, Edward J. “Minimization of Boolean Functions.” The Bell System Technical Journal 35, no. 6 (November 1956): 1417–1444. doi:10.1002/j.1538-7305.1956.tb03835.x.
- Petrick, Stanley R. A Direct Determination of the Irredundant Forms of a Boolean Function from the Set of Prime Implicants. Technical Report AFCRC-TR-56-110. Bedford, MA: Air Force Cambridge Research Center, April 1956.