What "minimal" means, and why it is not the same as "shorter"
Simplifying a Boolean expression by hand gives you a shorter expression. It does not tell you whether a shorter one exists. Two students can apply the identities in different orders, reach different answers, and both be correct — and neither knows which is cheapest. Minimisation as an algorithm answers the question that hand algebra cannot: among all two-level sum-of-products expressions for this function, which uses the fewest terms and the fewest literals?
The cost model matters. A literal is one appearance of a variable or its complement, so AB'C has three literals. A term is one product in a sum-of-products expression. In a two-level AND-OR circuit those map directly onto hardware: each term is one AND gate, each literal is one input to that gate, and the whole sum is one OR gate. Minimising literals minimises gate inputs, which in classical gate-array design is what you pay for.
Everything here is about two-level form. That restriction is deliberate: two-level circuits have a uniform, predictable propagation delay, and the minimisation problem is exactly solvable. Allow more levels and you can often do better on literal count — AB + AC factors to A(B + C), three literals instead of four — but the delay grows and the problem stops being tractable. If the calculator tells you the minimal form has more literals than the expression you typed, that is almost always what happened: you typed a factored form.
How the Quine–McCluskey algorithm finds the answer
The algorithm rests on a single identity: XY + XY′ = X. If two product terms agree in every variable except one, and disagree in that one, the differing variable drops out. Written on minterm indices, two minterms merge exactly when their binary codes differ in one bit position, and the merged implicant carries a dash in that position.
The procedure has two halves. First, find every prime implicant. List the minterms as binary codes. Compare every pair; where they differ in exactly one bit, record the merged term and mark both parents as used. Repeat on the merged terms, and again, until no more merges are possible. Anything never used in a merge is a prime implicant — an implicant that cannot be enlarged. This half is purely mechanical and always terminates.
icSecond, choose a minimal cover. Build a chart of prime implicants against minterms. Any minterm covered by exactly one prime implicant forces that implicant into the answer; it is an essential prime implicant, and every minimal solution contains it. Remove the essentials and the minterms they cover, then find the cheapest set of the remaining prime implicants that covers what is left. This calculator searches that remainder exhaustively when the number of candidates is small, so the reported cover really is minimal in literals, with ties broken by term count and then alphabetically so the answer is reproducible.
Karnaugh maps do exactly the same two steps graphically: adjacent cells on the map are minterms differing in one bit, a rectangular group of 2k cells is an implicant, and the largest groups are the prime implicants. The map is faster for a human up to four variables; the algorithm is what you use beyond that. The Karnaugh map solver shows the same function laid out on the grid.
Worked example: simplifying AB + AB′C + A′BC
Take the default expression with variables A, B, C, where A is the most significant bit.
- Find the minterms.
ABis true whenever A = 1 and B = 1, giving rows 110 and 111, that is m6 and m7.AB′Cis row 101, m5.A′BCis row 011, m3. So F = Σm(3, 5, 6, 7). - Write the codes and merge in pairs. m3 = 011, m5 = 101, m6 = 110, m7 = 111. Compare each pair: 011 and 111 differ only in the first bit, giving
-11. 101 and 111 differ only in the second, giving1-1. 110 and 111 differ only in the third, giving11-. The pair 011 and 101 differs in two bits, so it does not merge; nor do 011 and 110, nor 101 and 110. - Try a second round.
-11,1-1and11-all have their dashes in different positions, so none of them can merge with another. All three are prime implicants:-11= BC,1-1= AC,11-= AB. - Build the cover chart. m3 is covered only by BC. m5 is covered only by AC. m6 is covered only by AB. m7 is covered by all three. So BC, AC and AB are all essential.
- Read off the answer. F = BC + AC + AB — three terms, six literals, down from three terms and eight literals as written.
The same result falls out of hand algebra if you happen to pick the right moves: AB + AB′C = A(B + B′C) = A(B + C) = AB + AC, using X + X′Y = X + Y. That leaves AB + AC + A′BC, and AC + A′BC = C(A + A′B) = C(A + B) = AC + BC, giving AB + AC + BC. Two applications of the same identity — but you had to spot them. The algorithm never has to spot anything.
This function has a name: it is the majority function on three inputs, true whenever at least two of A, B and C are true. Its minimal form is symmetric in the three variables, which is a good sanity check on any answer you get.
How to read the output
Start with the literal count. Six literals in three terms means a two-level AND-OR circuit with three AND gates of two inputs each and one three-input OR gate — before you add inverters for the complemented literals. Compare that with the literal count for your input to see what the minimisation bought you, and remember the comparison is only meaningful when your input was already in two-level form.
The prime implicant list is longer than the answer whenever some implicants were not needed. That gap is informative: a function with many redundant prime implicants has multiple minimal covers of equal cost, and a synthesis tool may pick a different one than this calculator does. Both are correct. When every prime implicant is marked essential, the minimal cover is unique.
A result of 1 means the function is true in every row — a tautology — and a result of 0 means it is never true. Both are reported with zero terms and zero literals, because a constant needs no gates at all. If you expected a real expression and got a constant, check the parse: an unbalanced bracket or a misplaced apostrophe usually shows up this way. The truth table calculator is the quickest way to confirm what your expression actually evaluates to.
Choosing POS rather than SOP does not change the function, only its shape. The calculator minimises the complement as a sum of products and then applies De Morgan to every term, which is the standard construction. Whether SOP or POS is cheaper depends entirely on the function: a function true in only two of sixteen rows has a compact SOP, and its complement — true in fourteen rows — usually has a compact POS instead.
The Boolean identities this calculator is equivalent to applying
| Name | OR form | AND form |
|---|---|---|
| Identity | A + 0 = A | A · 1 = A |
| Null (dominance) | A + 1 = 1 | A · 0 = 0 |
| Idempotent | A + A = A | A · A = A |
| Complement | A + A′ = 1 | A · A′ = 0 |
| Involution | (A′)′ = A | |
| Commutative | A + B = B + A | AB = BA |
| Associative | (A + B) + C = A + (B + C) | (AB)C = A(BC) |
| Distributive | A + BC = (A + B)(A + C) | A(B + C) = AB + AC |
| Absorption | A + AB = A | A(A + B) = A |
| Adjacency | AB + AB′ = A | (A + B)(A + B′) = A |
| Simplification | A + A′B = A + B | A(A′ + B) = AB |
| De Morgan | (A + B)′ = A′B′ | (AB)′ = A′ + B′ |
| Consensus | AB + A′C + BC = AB + A′C | |
Adjacency is the one the algorithm uses directly; every other row can be derived from the first four plus distribution. Note that A + BC = (A + B)(A + C) has no counterpart in ordinary arithmetic — Boolean addition distributes over multiplication as well as the reverse.
Notation this calculator accepts
Variables are single letters, and case is ignored, so a and A are the same variable. Writing letters next to each other means AND: ABC is A·B·C. A trailing apostrophe or prime complements the term before it, so A', (A+B)' and AB' all work. You can also use + or | for OR, *, . or & for AND, ! or ~ for a prefix NOT, and ^ for exclusive-or. Word operators AND, OR, NOT, XOR, NAND, NOR and XNOR work too, but put spaces around them — AANDB reads as five separate variables.
Pitfalls and limits
- Minimal literal count is not minimal delay or minimal transistor count. Real synthesis tools optimise against a technology library, where a 3-input NAND may be cheaper than a 2-input AND plus an inverter. Use this result as the algebraic baseline, not as a layout.
- Inverters are not counted. The literal count ignores the cost of producing A′ from A. If complemented inputs are not already available, add one inverter per distinct complemented variable.
- Ties are real. When several covers have the same literal count, the calculator picks one deterministically. A textbook answer key may show a different but equally minimal expression — compare literal counts, not strings.
- Two-level only. Factored and multi-level forms are excluded by construction, so the reported minimum can exceed the literal count of a factored expression you already had.
- Hazards are not modelled. A minimal cover can contain a static hazard: a glitch when two inputs change and no product term covers the transition. Hazard-free design deliberately adds redundant prime implicants, which costs literals.
- Six variables is the ceiling here. The truth table is enumerated in full, so cost doubles per variable. Beyond that, use Espresso-style heuristic minimisation, which trades guaranteed optimality for speed.
Where this sits among the alternatives
Hand algebra, Karnaugh maps and Quine–McCluskey all compute the same thing, and they differ only in who does the searching. Hand algebra needs you to spot the applicable identity, and gives no guarantee of optimality. A K-map turns spotting into seeing, and works comfortably to four variables and awkwardly to five or six. Quine–McCluskey is the mechanical form of the same search, correct at any size but exponential in cost — which is why industrial synthesis uses heuristic minimisers such as Espresso, which usually find the optimum and never promise it.
The algorithm is due to Willard Van Orman Quine, who described the prime-implicant idea in 1952, and Edward J. McCluskey, who turned it into a tabular procedure in 1956. Maurice Karnaugh's map had appeared in 1953. All three predate integrated circuits, and all three are still taught because the underlying question — what is the cheapest circuit that computes this table — never went away.
Two neighbouring tools finish the picture. To see whether an expression is a tautology or to compare two expressions row by row, use the truth table calculator. To work with collections rather than propositions — where the same De Morgan laws govern union, intersection and complement — use the set operations calculator. And when the structure you are minimising is a graph rather than a function, the Dijkstra shortest path calculator handles the corresponding optimisation.