Quine–McCluskey Solver

1. Combine minterms that differ in exactly one bit, round after round, until nothing combines. What survives uncombined is prime.
2. Chart the primes against the ON-set minterms.
3. Take the primes that uniquely cover something — the essentials — and strike out what they cover.
4. Reduce what is left by dominance.
5. Solve whatever remains — the cyclic core— with Petrick's method.
6. Among the irredundant covers that produces, take the cheapest.

A merge is legal only between adjacent 1-count buckets, only when the dash patterns already match, and only when the fixed bits differ in exactly one place. “Merging 0011 with 1100” is the standard first mistake, and the caption of the first table says so.

They may be used to build bigger primes, because you are free to read them as 1. They must not appear as chart columns, because nothing requires them to be covered. The corollary is a filter: a prime that covers no ON-set minterm is discarded before the chart is built, and this page shows the discards in a dimmed block rather than dropping them silently — including them in the chart is a known bug in the popular npm implementations.

A distinguishing cell makes a prime essential: it is a minterm that only that prime covers, and the chart rings it. An irredundant cover is one where no term can be deleted. A minimum cover is one no cover beats on cost. An irredundant cover can be strictly worse than the minimum, which is why the two words are not interchangeable.

Expanding the product of k sums and absorbing afterwards materialises up to n₁·n₂·…·n_k terms before anything cancels. Folding one factor at a time and keeping only the ⊆-minimal products applies absorption inside the loop, and Table 4 prints both numbers — the size the expansion would have reached against the largest antichain the fold actually held. Because every cost here is strictly positive, a minimum-cost cover is necessarily irredundant, so the antichain provably contains it; that is why the fold is sound for literal cost too and not only for term count.

This page opens on Σm(0, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13) over A B C D: 9 prime implicants, none of them essential, and 6 minimum covers, provably the complete set — minimal SOP A′ · D′ + A′ · C + B · C′ + A · B′, minimal POS (A + B + C + D′) · (A′ + B′ + C′). Those numbers are computed by the engine at build time.

The published handout this function comes from reports two. It is not wrong; it answered a different question. Its reduction applies column dominance, which is safe when you want an optimum and unsafe when you want every optimum: striking out a dominated prime discards every cover that used it, and some of those cost exactly the minimum. So this page runs two pipelines — the textbook walkthrough for the tables, and essentials plus row dominance only for the list of covers — and labels which is which.

One more guard, and it is a silent-wrong-answer bug in several published implementations: a dominated prime may only be struck out when the dominating one costs no more. That condition is vacuous under term-count cost and mandatory under literal cost.

They compute the same thing. The map is faster to read and stops at six variables; the tables scale, are mechanical, and are what an algorithm can execute. A group on a map is a prime implicant, and the largest legal rectangle is a maximal cube. The Karnaugh map solver draws the same functions this page tabulates.

Exact to 8 variables on the main thread and to 12 in a solve you can cancel; the Espresso heuristic to 20, badged near-minimal (Espresso heuristic) rather than exact, with the combining and chart tables replaced by a note saying why they do not exist on that path; refused above 20, with the reason in text. Worst-case prime count is Θ(3ⁿ/√n) and cover selection is NP-hard, which is why the thresholds exist. Equally minimal covers are enumerated to 200 and displayed to 200, and the badge says so when a cap is reached rather than printing a count nothing proved.

The minimiser is checked exhaustively against brute force for every function of up to four variables and by randomised differential testing above that, matching on both cost and the number of distinct minimum covers. It independently reproduces three published reference results: Petrick's own example (2 covers), the Columbia handout's Example #2 (6 covers, against the handout's 2), and Σm(4, 5, 7, 8, 9, 11, 12, 14) (4 covers). Publishing the test regime is this page's alternative to the incumbents' disclaimers.