Karnaugh maps explained: simplifying Boolean expressions by grouping

A Karnaugh map, or K-map, is a grid that lays out a Boolean function's truth table so that neighbouring cells differ in just one input. Circling rectangular groups of 1s in sizes 1, 2, 4, 8 or 16 then gives a simplified expression directly, because each group drops the inputs that change inside it. The Karnaugh map solver I built finds the minimal answer exactly, and this guide shows how to do it by hand.

What a Karnaugh map is

Maurice Karnaugh introduced the method in 1953 as a refinement of Edward Veitch's 1952 chart. It is used in digital electronics and computer science to reduce logic circuits to as few gates as possible. A function of n inputs has 2ⁿ input combinations, and the map has one cell for each. For three inputs A, B and C, the map has 8 cells in 2 rows (A = 0 or 1) and 4 columns (BC). Each cell holds the function's output, 1 or 0, for that combination; the combination number written in binary, with A as the most significant bit, is called the minterm number. The truth table generator produces the table you start from.

Why the labels use Gray code

The columns are labelled 00, 01, 11, 10, not 00, 01, 10, 11. That order is a Gray code, named after Frank Gray: consecutive values differ in exactly one bit. It means any two side-by-side cells differ in a single variable, and so do the cells at opposite edges, because 10 and 00 also differ in one bit. The map therefore wraps round like a ring, left edge to right edge and top to bottom. Seeing why binary counting does not have this property is a good use of the number base converter.

The grouping rules

• Groups contain only 1s (or don't-cares) and must be rectangles of 1, 2, 4, 8 or 16 cells: always a power of two.
• Groups may wrap around the edges and may overlap.
• Make each group as large as possible, and use as few groups as possible to cover every 1.

A group of 2ᵏ cells removes k variables. Inside a group, any input that is 0 in some cells and 1 in others drops out, and the inputs that stay fixed form the product term: a variable fixed at 1 appears plain, one fixed at 0 appears negated (written with a prime, so C' means NOT C).

A worked example

Take F(A, B, C) = 1 for minterms 0, 2, 4, 5 and 6. With columns BC in the order 00, 01, 11, 10, the row A = 0 reads 1 0 0 1 and the row A = 1 reads 1 1 0 1.

• The four cells in columns 00 and 10 are all 1, and those two columns are adjacent because the map wraps. In all four, C = 0, while A and B change. That group is simply C'.
• Minterm 5 (A = 1, B = 0, C = 1) is still uncovered. Pair it with minterm 4 next to it: A = 1 and B = 0 in both, so the group is AB'.

So F = C' + AB'. Written as five separate minterms the function needs 15 literals; the simplified form needs 3. A four-variable example works the same way on a 4 × 4 grid: minterms 0, 1, 2, 5, 6, 7, 8, 9, 10 and 14 simplify to CD' + B'C' + A'BD, which is the solver's default.

Don't-care cells

Sometimes certain input combinations can never happen, or their output does not matter, such as the codes 10 to 15 in a circuit that only ever receives decimal digits 0 to 9 in binary. These cells are marked X. You may treat each X as a 1 if it makes a group larger, and ignore it otherwise; you never need a group that covers only Xs. Don't-cares often turn a messy expression into a short one. Grouping the 0s instead of the 1s gives the product-of-sums form, which the solver also shows.

Beyond four variables

Karnaugh maps work best for up to four inputs. Five and six variables need stacked maps that are hard to read, and by hand it is easy to miss a bigger group or a cheaper set of groups, especially when several answers are equally small. The solver avoids this with the Quine–McCluskey method, which lists every prime implicant (every group that cannot be enlarged) and then searches for the smallest set covering all the 1s. It accepts minterm lists for up to six variables. The variables are bits, so Binary, explained from zero is useful background.