A Karnaugh map — often shortened to K-map — is a grid-based method for simplifying Boolean functions. It arranges minterms so that neighboring cells differ in one input bit, making useful combinations visible. Grouping the 1s produces a sum-of-products (SOP) form; grouping the 0s produces a product-of-sums (POS) form. A K-map helps find a minimum two-level form under a stated cost measure; it does not by itself identify the lowest-cost circuit for every technology or gate model.
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.
Combining adjacent minterms can reduce the number of literals and product terms in a two-level expression. That often gives a simpler implementation than writing one minterm per truth-table row. Physical area, delay, and power still depend on the available gates, fan-in, loading, and circuit structure; a factored multi-level circuit can have a different cost. See two-level vs. multi-level logic for that trade-off.
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.
How to solve a 4-variable K-map: a complete worked example
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.
- Use maximal groups as candidates. A larger group removes more literals from its term, but selecting the largest group for each cell independently does not always give the smallest cover.
How to choose a minimum cover
First identify the prime implicants: every maximal valid group that cannot be expanded without including a specified 0. Then select every essential prime implicant, because each is the only candidate covering at least one required 1. If some 1s remain, compare combinations of the remaining prime implicants until every required 1 is covered. Do not make that choice one cell at a time: the groups overlap, so one candidate can cover several remaining cells at once.
The cost rule matters. A larger group has fewer literals in its individual term, but a complete expression is a set of terms; a locally largest choice can leave cells that require extra terms. In this site's solver, the cover search minimizes the number of terms first, then the total literal count among covers with that term count. Follow the cost rule stated in your problem. When no prime implicant is essential, Petrick's method evaluates the remaining cover choices systematically; see also essential and non-essential prime implicants.
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.
- Use maximal groups as candidates, then choose a minimum cover across the whole map; a largest-group-first choice for each cell is not enough.
- 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 for learning and for small maps. The same prime-implicant and cover-selection problem can be handled systematically with Quine-McCluskey, with Petrick's method resolving the remaining cover when essential groups are not enough.