Imagine you have designed a logic circuit and its truth table works perfectly — but the circuit uses ten gates. Every gate costs money, heat and space, and it is one more thing that can fail. An identical circuit built from three gates would be cheaper, faster and cooler. So the real engineering question isn't just "does it work?" but "what is the simplest expression that gives this exact truth table?"

You could hunt for a simpler form using the algebra of Boolean algebra and De Morgan's laws — but that is fiddly, and it is easy to miss a simplification. A Karnaugh map (K-map, invented by Maurice Karnaugh in 1953) turns the whole job into something you can do by eye. You plot the truth-table 1s onto a special grid, draw a few loops around them, and read the simplified expression straight off the loops. Simplification becomes a picture.

The secret ingredient: Gray-code labelling

A K-map is a grid with one cell for every row of the truth table. The magic is in how the rows and columns are labelled. Instead of ordinary binary counting (00, 01, 10, 11), the labels go in Gray-code order:

Look closely: from each label to the next, exactly one bit changes. 00 \to 01 flips the right bit; 01 \to 11 flips the left bit; 11 \to 10 flips the right bit again. This is the whole point of a K-map: because neighbours differ in only one variable, any two cells that touch (side by side, or above and below) differ in exactly one input. That "one input changed" is precisely the situation Boolean algebra can collapse — because X\!\cdot\!\bar{Y} + X\!\cdot\!Y = X. Adjacency on the map is simplification in disguise.

If you labelled the columns in plain binary order (00,01,10,11), then columns 01 and 10 would sit next to each other even though they differ in two bits — and the trick would break. The Gray-code order is not decoration; it is what makes the map work.

A two-variable map, start to finish

Take the expression F = \bar{A}B + AB. Its truth table has 1s wherever B = 1. A two-variable map is a 2 \times 2 grid: A labels the two rows (0,1) and B labels the two columns (0,1). Write each output into its cell, then loop the adjacent 1s. Press play.

Both 1s sit in the B = 1 column, so they form a group of two. To read the term, keep only the variable that stays the same across the whole loop: here A changes (0 then 1) so it drops out, while B is 1 throughout. The group reads simply B — so F = \bar{A}B + AB = B. Two terms became one.

Reading a term from a loop

Every loop turns into one product (AND) term, and the rule is always the same:

• a variable that is 1 across the whole loop appears as itself (A);
• a variable that is 0 across the whole loop appears negated (\bar{A});
• a variable that changes inside the loop disappears.

This is why bigger loops are better: doubling the size of a loop makes one more variable change inside it, so one more variable vanishes. A loop of 2^{k} cells eliminates k variables:

That is the reason loop sizes are always powers of two — 1, 2, 4, 8, \dots — never 3, 5 or 6.

A three-variable map

With three inputs we need 8 cells, arranged as a 2 \times 4 grid. A labels the two rows; the pair BC labels the four columns in Gray-code order (00, 01, 11, 10). Consider a circuit whose output is 1 for the four combinations

Four terms, three literals each — but the map tells a much simpler story. Watch the two loops appear.

The top loop sits entirely in A = 0, B = 1 while C changes — so it reads \bar{A}B. The bottom loop sits in A = 1, B = 0 with C changing — so it reads A\bar{B}. The whole expression collapses to

— the exclusive-OR of A and B, with C gone entirely because it never mattered. Notice how the loop reaches across from column 11 to column 10: that only works because Gray-code labelling makes those two columns adjacent.

A four-variable map — and the torus trick

Four inputs give a full 4 \times 4 grid: AB labels the rows (Gray order 00,01,11,10) and CD labels the columns the same way. Take

(that is, the output is 1 for those eight minterms). Plotted out, two beautiful groups of four appear.

The four cells in the middle all share B = 1 and D = 1 (with A and C changing), so that loop reads BD. The four corners look separated — but a K-map behaves like a torus: the left edge is glued to the right edge and the top edge to the bottom, so the four corners are all neighbours and form one legal group of four. They share B = 0 and D = 0, giving the term \bar{B}\bar{D}. So

Eight minterms of four literals each, tamed into two tidy terms. Reaching that by pure algebra would take real effort; on the map it is almost automatic.

Seeing why a variable can vanish

The three-variable example simplified to \bar{A}B + A\bar{B} with C nowhere in sight. If that feels like a trick, let a program print the full truth table and label each row with its minterm number. Press Run and check: the output depends only on A and B — the value of C never changes F, which is exactly why the loops were free to stretch across the C direction.

Rows 2,3 (both 1) and rows 4,5 (both 1) are exactly the two loops from the map — each a pair that differs only in C.