Karnaugh map solver
Type an expression or click the squares to build a map, mark the rows you don't care about, and get every group drawn with the minimal expression underneath. Two to six variables, worked out in your browser.
Rows whose output does not matter, so a group may swallow them for free. You can also click any square to cycle it through 0, 1 and X.
Reading it as a ∧ ¬b ∨ a ∧ b ∧ c ∨ ¬a ∧ ¬b ∧ c
| a bc | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 0 | ||||
| 1 |
Pick a group to see only its squares. Click a square to cycle it through 0, 1 and X.
Simplified ¬b ∧ c ∨ a ∧ ¬b ∨ a ∧ c
How a Karnaugh map works
A Karnaugh map is a truth table folded into a grid so that logical neighbours are physical neighbours. That one change turns simplification into pattern spotting.
- The edges count in Gray code. The column labels run 00, 01, 11, 10 rather than in binary order, so moving one square changes exactly one variable. It is why the map works at all.
- Circle rectangles of 1s. Every group has to be a power of two: 1, 2, 4, 8. Inside a group of two, one variable takes both values, so it cancels and drops out of the term. Every doubling removes one more variable.
- The edges wrap. The left column touches the right column and the top row touches the bottom, as if the map were rolled into a torus. Corner squares can form a group of four.
- Overlap is free. Reusing a square in two groups costs nothing, so always take the biggest rectangle available.
- Treat X as whichever helps. A don't care counts as a 1 when it lets a group grow and as a 0 otherwise, and never needs covering on its own.
- OR the terms together. Each group is one AND term; the whole map is those terms ORed. That is your simplified sum of products.
Don't cares
Sometimes a row of the truth table has no right answer, because the input can never occur or because nothing reads the output in that case. Those rows are free: the minimiser can treat them as 1 where that helps and 0 where it does not.
The usual example is a binary coded decimal digit. Four bits can express sixteen values, but a decimal digit only uses ten of them, so the codes 1010 through 1111 never appear. A circuit deciding whether the digit is five or more does not have to produce anything sensible for those six, and saying so out loud makes it smaller.
| "BCD digit is 5 or more" | Minimal expression | Literals |
|---|---|---|
| Unused codes forced to 0 | ¬a ∧ b ∧ d ∨ ¬a ∧ b ∧ c ∨ a ∧ ¬b ∧ ¬c | 9 |
| Unused codes marked X | a ∨ b ∧ d ∨ b ∧ c | 5 |
Identical behaviour on every input that can actually happen, four fewer literals and a gate saved. Load it above with the BCD ≥ 5 example, then clear the don't care box to watch the expression grow back.
Karnaugh map or boolean algebra?
They give the same answer; they suit different sizes of problem.
| Approach | Best at | Falls apart when |
|---|---|---|
| Karnaugh map | Two to four variables, done by eye in seconds | Past six variables the grid stops being readable |
| Algebraic rewriting | Showing your working, and proofs | It is easy to miss a simplification you did not think of |
| Quine-McCluskey | Any size, and it is mechanical, so a computer can do it | Tedious by hand |
This page runs Quine-McCluskey and draws the result as a map, so the groups you see are guaranteed to be a valid, irredundant cover rather than the first ones a human happened to spot. Irredundant means no group can be dropped; for a handful of awkward functions an exact solver can still find a cover with one term fewer.
Then build it
A simplified expression is worth checking against real gates. Paste it into the simulator with ctrl+E and you get the circuit, wired and running, with fewer gates than the version you started with.
Questions
What is a don't care in a Karnaugh map?
A row whose output genuinely does not matter, because that input combination can never happen or because nothing downstream looks at it. Marking it X lets the minimiser treat it as either 0 or 1, whichever makes the groups bigger. The six unused codes of a binary coded decimal digit are the standard example.
Do don't cares have to be covered?
No, and that is the whole point. A group may swallow a don't care when doing so makes it larger, but leaving one outside every group costs nothing. The groups here are formed from the 1s and the X's together, and then only the 1s have to be covered.
How do I read a Karnaugh map?
Each square is one row of the truth table. The labels along the edges are in Gray code, so neighbouring squares differ in exactly one variable. That is the whole trick: any rectangle of adjacent 1s whose size is a power of two collapses into a single product term, because the variables that change across the rectangle cancel out.
What are the grouping rules?
Groups must be rectangles of 1, 2, 4, 8 or more squares, always a power of two. They may overlap, and they wrap around the edges of the map, so the left column is adjacent to the right column and the top row to the bottom. Bigger groups are better, because each doubling removes one variable from the term.
How are the groups on this page chosen?
By Quine-McCluskey, which is the algebraic equivalent of drawing the rectangles: it finds all the prime implicants, keeps the ones that are essential, covers what is left and then drops any group the others already cover. The groups shown are exactly the terms in the simplified expression.
Why does the map stop at six variables?
Past 6 variables a Karnaugh map is harder to read than the algebra it replaces, which is why real designs switch to Quine-McCluskey or a synthesis tool. The boolean algebra calculator on this site will still simplify up to eight variables.