Karnaugh Map Solver

What is a Karnaugh map?

A Karnaugh map (K-map) is a truth table drawn so that neighbouring cells differ in exactly one variable. To achieve that, rows and columns follow Gray code order (00, 01, 11, 10) instead of binary order. When two 1s sit next to each other, the variable that changes between them can be eliminated: A·B·C + A·B·C' = A·B.

The map wraps around: the last column is adjacent to the first and the last row to the first. That is why the four corners of a 4-variable map can form a single group.

Rules for grouping

1. Groups are rectangles of 1, 2, 4, 8 or 16 cells (powers of 2).
2. Make groups as large as possible: a group of 2^k cells eliminates k variables.
3. Use the fewest groups that cover every 1. A cell can belong to several groups.
4. Don't cares (X) can be treated as 1 if they help enlarge a group, but they never have to be covered.
5. For each group, keep the variables that do not change: uncomplemented if they are 1 and complemented if they are 0.

Sum of products vs product of sums

For the SOP form you group the 1s and each group gives a product term. For the POS form you group the 0s: each group gives a sum term in which variables appear inverted (complemented if they are 1 in the group). Both are correct; depending on the function one can be shorter than the other, and POS is often more convenient for NOR-gate implementations.

How the solver finds the minimal expression

Besides drawing the groups, the tool runs the Quine-McCluskey method: it generates every prime implicant (the largest possible groups), picks the essential ones first (those that are the only cover for some 1) and then tries every combination of the rest to find the cover with the fewest terms and, on a tie, the fewest literals. With 4 variables or fewer this guarantees a minimal expression. If several are equally short, one of them is shown, so yours may differ and still be correct.

Frequently asked questions