Figure 1. A 4×4 K-map with rows AB and columns CD labelled in Gray code (00, 01, 11, 10). Every horizontally or vertically adjacent pair of cells differs in exactly one variable, so combining them drops that literal.
A Karnaugh map is a truth table re-drawn as a 2-D grid. Each cell is one minterm; the row and column labels say which input combination it represents. The trick is the labelling: rows and columns step in Gray code, not natural binary.
Adjacent cells on a K-map differ in exactly one input variable. That single-bit step is what lets two 1-cells combine into a two-cell group with one fewer literal.
Why Gray ordering matters
Figure 2. 00 → 01 → 11 → 10 — every step toggles a single bit. Natural binary 00 → 01 → 10 → 11 toggles two bits going from 01 to 10, breaking the adjacency we need.
On a K-map two cells are adjacent when they share a side, and also when they live at opposite ends of a row or column (edge wrap, covered below). With Gray-coded axes every adjacency is a one-bit change, so the algebraic identity X⋅Y+X⋅Y′=X applies and the toggling literal drops out.
2-variable and 3-variable maps
Figure 3. 2-var (rows = A, cols = B) and 3-var (rows = A, cols = BC). The 3-var map keeps the same Gray-coded columns 00 / 01 / 11 / 10, so cells (A=0, BC=00) and (A=0, BC=10) wrap around to be adjacent.
Two-variable functions don’t really need a K-map — there are only four cells — but they’re a clean way to see the layout convention. For three variables the rows still split on a single bit (A) and the columns step through two bits (BC) in Gray order.
Grouping rules
A group must be a rectangle of 1, 2, 4, 8, 16, … cells (each axis independently a power of 2). Bigger groups always drop more literals: a group of 2k cells removes k literals.
1 cell → all n literals (a minterm).
2 cells → n−1 literals.
4 cells → n−2 literals.
8 cells → n−3 literals; etc.
To minimise F, cover every 1-cell with the fewest, largest groups. Each group becomes one product term in the minimum SOP; an OR over the groups is the answer.
Edge wrap
Figure 4. The four corners of a 4-variable map form a single 4-cell group: B'·D'. Top wraps to bottom and left wraps to right because the Gray sequence is cyclic — 10 is one bit away from 00.
Don’t-cares
A don’t-care row (output is unspecified) is marked X. The minimiser may treat each X as 0 or 1 — whichever yields a larger group. Cover them only if doing so grows a group.
Don’t-cares are optional coverage. Use an X when it lets a 2-cell group become a 4-cell group; ignore it otherwise.
5 variables — two stacked maps
Beyond four variables the planar adjacency picture breaks down. For five inputs (A,B,C,D,E) the standard convention is two 4×4 maps drawn side-by-side: one for A=0 and one for A=1. Cells in the same (row,col) position on the two maps are adjacent (they differ only in A), so a 2-cell group can bridge the two halves.
Above five variables the visual reading becomes unwieldy and the Quine–McCluskey tabular method (the next topic) takes over.
