K-Map Solver (Karnaugh Map Simplifier)
Click a cell to cycle 0 → 1 → X (don’t care). The minimal sum-of-products (SOP) expression and its groups update instantly, computed with the Quine-McCluskey algorithm.
Rows/columns use Gray code order (00, 01, 11, 10). Small numbers are minterm indices; A is the most significant bit.
How the solver works
This is the Quine-McCluskey method, the tabular equivalent of circling groups on a Karnaugh map. Each prime implicant corresponds to a largest possible rectangular group of 1, 2, 4 or 8 cells (wrapping around the edges). Don't-care cells may be included in groups to make them larger but never need to be covered. For up to four variables the remaining cover is found by exhaustive search, so the result is guaranteed minimal in number of terms, then literals. When several minimal solutions exist, one of them is shown.
Worked example
Take F(A,B,C,D) = Σm(0, 1, 2, 5, 6, 7, 8, 9, 10, 14), which is preloaded above. Cells 0, 1, 8, 9 (B′C′) form a quad, cells 0, 2, 8, 10 (B′D′) form the corner quad, and cells 2, 6, 10, 14 (CD′) form a column quad. Minterms 5 and 7 are covered by A′BD (cells 5, 7). The solver picks the minimal cover:
Note B′D′ is a prime implicant but redundant, because its cells are already covered by B′C′ and CD′. This is exactly the kind of choice Quine-McCluskey makes systematically.
Karnaugh map layout reference
| Variables | Rows | Columns | Cells | Cell index |
|---|---|---|---|---|
| 2 | A | B | 4 | m = 2A + B |
| 3 | A | BC | 8 | m = 4A + 2B + C |
| 4 | AB | CD | 16 | m = 8A + 4B + 2C + D |
Common Boolean results
| Function | Minterms | Minimal SOP |
|---|---|---|
| XOR (2 var) | 1, 2 | A'B + AB' |
| Majority (3 var) | 3, 5, 6, 7 | AB + AC + BC |
| Corners (4 var) | 0, 2, 8, 10 | B'D' |
| Odd parity (3 var) | 1, 2, 4, 7 | A'B'C + A'BC' + AB'C' + ABC |
| With don’t cares | 1,3,7,11,15 + d(0,2,5) | CD + A'B' (or CD + A'D) |
Tips
- Groups must be rectangles of size 1, 2, 4, 8 or 16 and may wrap around edges and corners.
- Make every group as large as possible, and use as few groups as possible.
- Use don't-cares (X) for input combinations that cannot occur, such as BCD codes 10–15.
- For product-of-sums (POS), solve for the 0s and complement the result with De Morgan's laws.
Frequently asked questions
What is a Karnaugh map?
A K-map is a grid representation of a truth table arranged in Gray code so that adjacent cells differ by one variable. Grouping adjacent 1s visually simplifies Boolean expressions.
How many variables does this K-map solver support?
Two, three and four variables. Beyond four, K-maps become hard to read and tools use Quine-McCluskey or Espresso directly.
What does X mean in a K-map?
X is a don't-care: the output can be 0 or 1. The solver includes X cells in groups only when that makes the expression simpler.
Is the result always minimal?
Yes for 2–4 variables: after essential prime implicants, the solver searches every combination of the remaining prime implicants and keeps the smallest cover, breaking ties by literal count.
Why is the Gray code order 00, 01, 11, 10?
Gray code ensures neighbouring rows and columns differ by exactly one bit, which is what makes adjacent cells combinable.