⊕Boolean Optimizer
A Quine-McCluskey minimizer with a terminal and a browser front end: state a Boolean function six different ways, get the provably minimal expression, and watch every step of the working — grouping tables, Karnaugh groups, and a drawn logic circuit.
Timeline
January — August 2026
Team
Solo build
Role
Algorithm & Full-Stack Engineering
Skills
Digital Logic, Algorithms, Python
Built with
LONG STORY SHORT
I built a Boolean minimizer that proves its own answers are minimal, and shows its working the way a textbook would.
Every digital logic course teaches Quine-McCluskey, and almost every implementation of it you can find will quietly hand you a wrong answer. Some are merely valid rather than minimal — they cover the function, but with more gates than necessary. Some hang forever on a function that resists reduction. Most show you a result and nothing of how they got there, which is precisely backwards for a tool whose main audience is someone trying to learn the method.
This one takes a Boolean function stated any of six ways, returns the provably minimal expression in either canonical form, and shows the entire derivation: the grouping and combining tables, the coverage chart, the Karnaugh map with its groups outlined, and the resulting circuit drawn gate by gate. The algorithm is pure standard library — zero runtime dependencies, about 3,800 lines of Python — and it is backed by 197 tests, including brute-force verification against independently computed oracles.
How a function becomes a minimal expression
Minterms, maxterms, an algebraic sum of products, a product of sums, a clickable Karnaugh map, or a truth table — all six inputs normalize to the same set of rows, so a single engine serves every one of them and the front ends stay thin.
- 1
State it
six input forms
- 2
Expand
to minterm rows
- 3
Group
by ones count
- 4
Combine
adjacent pairs
- 5
Essentials
singly-covered rows
- 6
Petrick
minimum residue
The tabular method itself is the easy part. Implicants are grouped by their number of ones, adjacent groups are compared, and any pair differing in exactly one bit combines into a shorter pattern with a dash where they differed. Repeat until nothing combines; whatever never combined is prime. Grouping by ones count is what makes this tractable — two patterns differing in one bit necessarily differ by one in their ones count, so each round compares only adjacent groups rather than every pair.
The part that is actually hard
Finding prime implicants is mechanical. Choosing the cheapest subset of them that still covers every minterm is the set-cover problem, and it is NP-hard.
Petrick's method solves it exactly by building a covering expression and multiplying it out — which grows multiplicatively in the number of rows. Left alone it will consume a machine. Three things keep it usable:
- Dominance reduction first. Before any expansion, rows and columns that provably cannot change the optimum are struck out, along with any prime forced by a singly-covered minterm. Measured on random dense functions, this is the difference between 0.010 s and "still running after 20 seconds" at eight variables.
- Absorption interleaved, not deferred. Subsumed terms are discarded after every multiplication rather than once at the end, so the intermediate never balloons before the next clause folds in.
- A ceiling, honestly reported. Some charts survive reduction with dozens of rows and no forced primes, and on those the expansion genuinely will not finish. Rather than hang, it stops at a bounded size and says so, naming the greedy method as the way forward. The bound sits above every measured peak on charts that do finish, so nothing solvable became unsolvable.
That last point is the one I care about most. An honest "I cannot do this, here is what to try instead" is a better answer than a spinner that never resolves.
Architecture
Three layers, strictly separated. The algorithm returns structured data and knows nothing about presentation; the presentation layer formats it and contains no algorithm; the two front ends share one parsing path so the terminal and the browser cannot disagree about what an input means.
Front ends
A terminal and a browser
- qmc — argparse CLI, exit codes
- Static page + JSON endpoint
- One shared parsing path
Presentation
Everything that formats
- Tables, K-maps, circuit geometry
- POS rendering via De Morgan
- Knows no algorithm
Core
The algorithm alone
- Implicants, combining, coverage
- Petrick + dominance reduction
- Pure standard library
The web server is http.server from the standard library and the browser page is hand-written HTML, CSS and JavaScript with no build step or framework. That is a deliberate constraint rather than an aesthetic one: the project's premise is that the whole thing is readable, and a reader who can follow the algorithm should not then hit a bundler to understand the interface.
One engine, pointed two ways
The most satisfying thing I learned building this is that product-of-sums minimization is not a second algorithm. It is the same algorithm run against the function's zero rows, with each resulting implicant read back through De Morgan.
Sum of products
Cover the rows where f = 1
- 1.Minimize the minterms directly
- 2.Each implicant is a product term
- 3.Sum the terms
A'BD + B'C' + CD'
Product of sums
Cover the rows where f = 0
- 1.Minimize the complement instead
- 2.Invert each literal — De Morgan
- 3.Multiply the clauses
(A' + B' + D')(B + C' + D')(B' + C + D)
One function, one engine, run twice. The second run is a different problem: on a twelve-variable example the 586 minterms reduced in 0.02 s while its 3510 zero rows took 60 s.
Getting this right meant the POS path had to honour everything the SOP path did — the method choice, the request for alternative equal-cost forms, don't-cares. It originally honoured none of them, which was invisible until I measured it: on a twelve-variable function the SOP side finished in 0.02 s while the POS side ran for a full minute, because the complement had six times as many rows and 9,666 prime implicants. The fix was to let the caller say which form it actually needs, which took that request from 60.10 s to 0.02 s.
The map has to wrap
A Karnaugh map is a torus. Its first and last rows differ in a single variable, as do its first and last columns, so a group may leave one edge and continue on the opposite one. The adjacency test stopped dead at the border, which drew the four-corner group as four unrelated single-cell boxes.
There is one exception worth getting right: a group that already fills an entire axis has nothing outside it to continue into, so the line at the border is the map's own edge rather than a cut through the group. Without that carve-out a full-width band comes out looking unbounded on both sides.
Taking the screenshots for this page is what surfaced a second bug, and a worse one. The outline is an absolutely positioned overlay appended to a map cell — but the rule styling the cell's little m0 label matched any span inside a cell, including the overlay, and at higher specificity. It forced the overlay back to position: relative, collapsing it from a group boundary to a three-pixel speck. No group outline had ever rendered. The map had been showing which cells were ones while never showing which cells the minimizer had grouped, which is the entire reason to draw a Karnaugh map at all.
Drawing the circuit
The browser renders the minimized expression as a schematic, and this turned out to be far more interesting than I expected.
An AND gate's outline is a cubic Bézier whose two control points share an x coordinate, which means its rightmost point — the nose the output wire has to meet — sits at x + 0.865·width, not at x + width. The code assumed the latter for both gate shapes. Since an OR gate genuinely does end at x + width, a single hand-tuned nudge made the OR look right and left every AND gate floating 8 to 15 pixels clear of its own output wire.
Three other things were wrong once I started measuring rather than eyeballing: gates were drawn even when they had a single input, so F = A rendered as a pin into a one-input AND into a one-input OR; gate width was hardcoded while height grew with input count, so an eight-input gate was three times taller than wide; and the output wire stopped ten pixels short of the lamp on every diagram.
Proving it, rather than asserting it
A minimizer is exactly the kind of program that can look right and be wrong. It produces a plausible expression for any input, and eyeballing a four-variable answer tells you very little about the fifth.
It computes the right function
Evaluate the emitted expression on every input row and compare with the truth table that was requested.
exhaustive to 3 variables · with don't-cares · sampled at 4 and 5 · 6,830 functions
It is genuinely minimal
Exhaustively search every cube the function contains, take the cheapest cover, and compare costs — a valid but larger answer fails.
exhaustive to 4 variables · term count and literal count
The drawing joins up
Re-derive each gate outline from the emitted SVG path data and assert that wires meet the shapes they target.
gate noses · input landings · aspect ratios · layer order
The map wraps correctly
Drive the Karnaugh adjacency rules directly, including the corner group and a degenerate one-column map.
toroidal edges · full-axis exception · single cells
So every claim is checked against an oracle that shares no code with the thing it is checking. Correctness is verified by evaluating the emitted expression row by row against the truth table that was requested. Minimality is verified by exhaustively enumerating every cube the function contains and finding the genuinely cheapest cover, then comparing costs — a merely valid answer fails. The circuit tests re-derive gate outlines from the emitted SVG path data, so they measure the drawing as rendered rather than trusting the renderer's intent.
That harness is also what found most of the bugs worth finding, including the ones above.
Making it usable at scale
A twelve-variable function has 4,096 rows, and the first version tried to send all of them, along with megabytes of working tables, a canonical form a quarter of a megabyte long, and per-implicant cover lists — about 6 MB of response that no view on the page could display.
Each of those now has a ceiling placed where the corresponding view stops being readable, and each says what it left out rather than truncating silently. Truth rows cap at 256 with the real total reported alongside. A canonical form past 4,000 characters falls back to index shorthand. Cover lists are sent only up to the width the Karnaugh map is actually drawn for, since shading its cells is the only thing they are used for. The same request now returns 249 KB in 0.23 s.
Why I built it this way
- Show the working, not just the answer. The grouping tables, the coverage chart, the outlined Karnaugh groups and the drawn circuit are the product. A minimized string alone teaches nothing.
- Prove minimality, do not claim it. Brute-force oracles over exhaustive cube enumeration, so a valid-but-suboptimal cover fails the suite rather than passing it.
- Fail honestly and usefully. NP-hard means some inputs genuinely cannot be solved exactly. Saying so, and naming the alternative, beats an unbounded wait.
- One engine, two forms. Product-of-sums falls out of minimizing the complement, so the duality is expressed in code rather than duplicated.
- Zero dependencies, no build step. Standard library and hand-written front end throughout, so the whole thing stays readable end to end.
- Test the drawing, not just the maths. Geometry is asserted from the emitted path data, because a schematic can be numerically correct and still visibly broken.
NEXT UP …
