A Karnaugh map — often shortened to K-map — is a grid-based method for simplifying Boolean expressions by hand. It turns a truth table into the shortest possible logic expression by looking at which outputs sit next to each other, rather than manipulating algebra symbol by symbol.
It was introduced by Maurice Karnaugh in 1953, building on a similar grid Edward Veitch had proposed a year earlier — which is why some textbooks still call it a Veitch diagram. Both names describe the same tool.
Why minimize a Boolean expression at all?
Every AND, OR, and NOT in a Boolean expression becomes a physical logic gate when the circuit is built. Fewer terms and fewer literals per term means fewer gates.
Fewer gates means a cheaper, faster, and less power-hungry circuit. A truth table written directly as a sum of minterms will always work — but it's rarely the smallest circuit that produces the same output. Minimization closes that gap.
From truth table to map
A truth table lists every input combination and its output. A K-map rearranges those same rows into a grid, with one crucial difference: adjacent cells in the grid always differ by exactly one input bit.
Why Gray code ordering matters
That single-bit-difference property comes from Gray code ordering (00, 01, 11, 10) instead of plain binary counting (00, 01, 10, 11) along each axis.
Reading a K-map: worked examples by size
The mechanics stay identical at every size — only the grid dimensions change. Three sizes, worked in full below.
2 variables
Take a function that outputs 1 whenever B is 1, regardless of A — minterms 1 and 3.
| A\B | 0 | 1 |
|---|---|---|
| 0 | 00 | 11 |
| 1 | 20 | 31 |
The two 1s sit in the same column, meaning B is 1 in both and A doesn't matter for either.
Grouping them gives the minimal expression directly: F = B. No algebra needed — the adjacency did the work.
3 variables
With three variables the map still fits on one grid — two rows (for A) by four columns (for B, C in Gray code order 00, 01, 11, 10).
Consider minterms 0, 2, 4, 6 — every case where C is 0. Every 1 in this map has C = 0, and every 0 has C = 1, so the whole function reduces to F = C′ — a single literal, regardless of what A and B are doing.
4 variables: the classic case, worked in full
This is the size most courses use to teach grouping properly — large enough to need genuine grouping decisions, but still fits on one grid.
Setting up the grid
Take F(A,B,C,D) = Σm(0,1,2,5,6,7,8,9,10,14):
| AB\CD | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 00 | 01 | 11 | 30 | 21 |
| 01 | 40 | 51 | 71 | 61 |
| 11 | 120 | 130 | 150 | 141 |
| 10 | 81 | 91 | 110 | 101 |
Grouping the cells
- B′C′ — a four-corner wraparound group covering {0,1,8,9}
- CD′ — a full column of four cells covering {2,6,10,14}
- A′BD — a pair covering the two remaining cells {5,7}
Three groups cover every 1 exactly once between them, with no smaller grouping possible for any of the three.
Writing the final expression
The grouping rules, precisely
- Group sizes must be a power of 2 — 1, 2, 4, 8, 16 cells. Never 3, 5, 6, or 7.
- Groups must be rectangular (including wraparound rectangles — see below), never an irregular shape.
- The map wraps around its own edges. The leftmost and rightmost columns are adjacent, and the top and bottom rows are adjacent, because Gray code ordering makes the first and last entries differ by only one bit too. This is the single most common thing people miss.
- Every required 1 must be covered by at least one group, but groups are allowed to overlap.
- Prefer the largest possible group for every cell before falling back to a smaller one — this is what keeps the final expression minimal.
Don't-care conditions
Some input combinations never actually occur in a real system, or their output genuinely doesn't matter. Marked as X on the map, a don't-care can be treated as either a 0 or a 1 — whichever helps form a bigger group.
They're never required to be covered, only used opportunistically. Full guide: Handling Don't-Care Conditions in K-Maps.
Beyond 4 variables
A single flat grid stops being practical past 4 variables — a 2D grid can't keep every cell adjacent to every cell that's one bit away once there are more than 4 bits to track.
The standard fix: split the extra variables into separate map tiles. A 5-variable function becomes two 4-variable maps; a 6-variable function becomes four. Adjacency between matching cells across tiles still counts. Full walkthrough: Reading 5- and 6-Variable Multi-Tile Karnaugh Maps.
Key takeaways
- A K-map turns a truth table's adjacency into something visible, using Gray code ordering so every neighboring cell differs by exactly one bit.
- Valid groups are always a power-of-2 size (1, 2, 4, 8...) and always rectangular, including wraparound rectangles across the map's edges.
- Always take the largest valid group for each cell — bigger groups mean fewer literals in the final expression.
- Don't-cares can be folded into a group opportunistically but are never required to be covered.
- Past 4 variables, multi-tile layouts keep the same rules working at 5 and 6 variables.
Where to go next
Grouping by eye works well up to about 4 variables, and builds the intuition everything else depends on. Past that, or when a problem needs a provably exact minimal answer, the same logic is formalized as Quine-McCluskey, with Petrick's method handling the cases where obvious essential groups don't fully solve it.