Lesson 11: Karnaugh maps (advanced, 15 min)

A Karnaugh map is a truth table folded so that neighbouring cells differ in one input. This advanced lesson, about fifteen minutes, covers Gray-code order, groups of 1, 2, 4 or 8 cells, wraparound at the edges, and reading off a formula the checker confirms.

Level: advanced15 min10 claims in this lesson were confirmed by the exact checker at build time

Arrange a truth table so that neighbouring cells differ in one input, group TRUE cells (wrapping around the edges), and read off a short formula that the checker confirms.

The first step lays out Σm(A, B; 1, 3) on a two-variable map in the order 00, 01, 11, 10 and reads the single group as B. The second groups Σm(A, B, C; 2, 3, 6, 7) into a block of four that removes two inputs, leaving B. The third shows that the edges touch: Σm(A, B, C; 0, 2, 4, 6) wraps to NOT C, and the four corners of a four-variable map, Σm(A, B, C, D; 0, 2, 8, 10), form one group, NOT B AND NOT D. The fourth derives a formula from groups, Σm(A, B, C; 1, 3, 5, 6, 7) becoming C OR (A AND B), with the engine checking the result against the original on every row.

Five equivalences in the lesson are verified at build time, one per derived expression. The exercises ask for the shortest DNF the map gives for three functions, including the four-corner case, and the value of a four-variable indexed form on one row.

The Karnaugh map solver in the tools section draws the map for any formula up to four variables, suggests groups, derives the expression and checks it; the law page on map grouping proves the rule behind a group, and the comparison with Quine–McCluskey explains what to do beyond four variables.

Do this lesson interactively in the app

Steps

1. Gray-code order

A Karnaugh map lays out the rows of a truth table in a grid. Rows and columns follow Gray-code order, 00, 01, 11, 10, so any two neighbouring cells differ in exactly one input.

That is what makes grouping work: two neighbouring TRUE cells differ in one input, which therefore does not matter for them. In Σm(A, B; 1, 3) both cells share B=TRUE, so the function is just B.

f := Σm(A, B; 1, 3) · outputsimple := B · output

Gray-code order

#	A	B	f	simple
0	FFALSE	FFALSE	FFALSE	FFALSE
1	FFALSE	TTRUE	TTRUE	TTRUE
2	TTRUE	FFALSE	FFALSE	FFALSE
3	TTRUE	TTRUE	TTRUE	TTRUE

Open the Karnaugh map of f and select the group of two cells.

equivalent f / simple · holds

2. Groups of 1, 2, 4, or 8

Group TRUE cells in rectangles of 1, 2, 4, or 8 cells. A group of 2ᵏ cells removes k inputs: the ones that change inside the group.

In Σm(A, B, C; 2, 3, 6, 7) all four cells have B=TRUE while A and C vary, so one group of four gives just B. Use groups that are as large and as few as possible.

f := Σm(A, B, C; 2, 3, 6, 7) · outputsimple := B · output

Groups of 1, 2, 4, or 8

#	A	B	C	f	simple
0	FFALSE	FFALSE	FFALSE	FFALSE	FFALSE
1	FFALSE	FFALSE	TTRUE	FFALSE	FFALSE
2	FFALSE	TTRUE	FFALSE	TTRUE	TTRUE
3	FFALSE	TTRUE	TTRUE	TTRUE	TTRUE
4	TTRUE	FFALSE	FFALSE	FFALSE	FFALSE
5	TTRUE	FFALSE	TTRUE	FFALSE	FFALSE
6	TTRUE	TTRUE	FFALSE	TTRUE	TTRUE
7	TTRUE	TTRUE	TTRUE	TTRUE	TTRUE

Select the group of four in the map of f and compare the derived expression with simple.

equivalent f / simple · holds

3. Wraparound: the edges touch

The map wraps around: the left and right edges are neighbours, and so are the top and bottom edges. Columns 00 and 10 differ only in the first bit.

So Σm(A, B, C; 0, 2, 4, 6), every row with C=FALSE, forms one group of four across the edges: NOT C. With four inputs even the four corners form a group: Σm(A, B, C, D; 0, 2, 8, 10) is NOT B AND NOT D.

edges := Σm(A, B, C; 0, 2, 4, 6) · outputnot_c := NOT C · outputcorners := Σm(A, B, C, D; 0, 2, 8, 10) · outputcorner_term := NOT B AND NOT D · output

Wraparound: the edges touch

#	A	B	C	D	edges	not_c	corners	corner_term
0	FFALSE	FFALSE	FFALSE	FFALSE	TTRUE	TTRUE	TTRUE	TTRUE
1	FFALSE	FFALSE	FFALSE	TTRUE	TTRUE	TTRUE	FFALSE	FFALSE
2	FFALSE	FFALSE	TTRUE	FFALSE	FFALSE	FFALSE	TTRUE	TTRUE
3	FFALSE	FFALSE	TTRUE	TTRUE	FFALSE	FFALSE	FFALSE	FFALSE
4	FFALSE	TTRUE	FFALSE	FFALSE	TTRUE	TTRUE	FFALSE	FFALSE
5	FFALSE	TTRUE	FFALSE	TTRUE	TTRUE	TTRUE	FFALSE	FFALSE
6	FFALSE	TTRUE	TTRUE	FFALSE	FFALSE	FFALSE	FFALSE	FFALSE
7	FFALSE	TTRUE	TTRUE	TTRUE	FFALSE	FFALSE	FFALSE	FFALSE
8	TTRUE	FFALSE	FFALSE	FFALSE	TTRUE	TTRUE	TTRUE	TTRUE
9	TTRUE	FFALSE	FFALSE	TTRUE	TTRUE	TTRUE	FFALSE	FFALSE
10	TTRUE	FFALSE	TTRUE	FFALSE	FFALSE	FFALSE	TTRUE	TTRUE
11	TTRUE	FFALSE	TTRUE	TTRUE	FFALSE	FFALSE	FFALSE	FFALSE
12	TTRUE	TTRUE	FFALSE	FFALSE	TTRUE	TTRUE	FFALSE	FFALSE
13	TTRUE	TTRUE	FFALSE	TTRUE	TTRUE	TTRUE	FFALSE	FFALSE
14	TTRUE	TTRUE	TTRUE	FFALSE	FFALSE	FFALSE	FFALSE	FFALSE
15	TTRUE	TTRUE	TTRUE	TTRUE	FFALSE	FFALSE	FFALSE	FFALSE

Compare edges with not_c, and corners with corner_term.

equivalent edges / not_c · holdsequivalent corners / corner_term · holds

4. From groups to a checked formula

Each group becomes an AND-term of the inputs that stay constant inside it; the groups are joined with OR. For Σm(A, B, C; 1, 3, 5, 6, 7), the group of four with C=TRUE gives C and the pair 6, 7 gives A AND B, so the result is C OR (A AND B).

Tangibool checks the derived expression exactly against the map. Cells excluded by confirmed assumptions may be marked “don’t care”, and the result is then labelled as valid only within that scope.

f := Σm(A, B, C; 1, 3, 5, 6, 7) · outputderived := C OR (A AND B) · output

From groups to a checked formula

#	A	B	C	f	derived
0	FFALSE	FFALSE	FFALSE	FFALSE	FFALSE
1	FFALSE	FFALSE	TTRUE	TTRUE	TTRUE
2	FFALSE	TTRUE	FFALSE	FFALSE	FFALSE
3	FFALSE	TTRUE	TTRUE	TTRUE	TTRUE
4	TTRUE	FFALSE	FFALSE	FFALSE	FFALSE
5	TTRUE	FFALSE	TTRUE	TTRUE	TTRUE
6	TTRUE	TTRUE	FFALSE	TTRUE	TTRUE
7	TTRUE	TTRUE	TTRUE	TTRUE	TTRUE

Compare f with derived.

equivalent f / derived · holds

Exercises

1. Find the simplest formula for Σm(A, B, C; 0, 2, 4, 6): a DNF with at most one operator. (write-equivalent)
2. Simplify Σm(A, B, C, D; 0, 2, 8, 10), the four corners of a 4-input map. Use a DNF with at most three operators. (write-equivalent)
3. Find a DNF with at most two operators for Σm(A, B, C; 1, 3, 5, 6, 7). (write-equivalent)
4. f := Σm(A, B, C, D; 5, 7, 13, 15). What is f for A=TRUE, B=TRUE, C=FALSE, D=TRUE? (predict-output)

Do this lesson interactively in the app

Questions

Why Gray-code order rather than binary?

So that adjacent cells differ in exactly one input, which is what makes a group of cells correspond to dropping that input. In binary order 01 and 10 would sit side by side and differ in two.

Does a map find the shortest expression?

It derives a cover with no removable term and checks it exactly. The engine calls that irreducible rather than smallest, because the smallest cover among several irreducible ones is a separate question.

Related

Guides

• Binary to Gray code

Laws

• Karnaugh map grouping rule: adjacent cells drop the variable that changes

Tools

• Karnaugh map solver: 2 to 4 variables, groups, SOP and POS, don’t-cares from assumptions

Practice

• Karnaugh map exercises with answers: 2 variables
• Karnaugh map exercises with answers: 3 variables
• Karnaugh map exercises with answers: 4 variables

See also

• Karnaugh map solver: 2 to 4 variables, groups, SOP and POS, don’t-cares from assumptions
• Karnaugh map grouping rule: adjacent cells drop the variable that changes
• Karnaugh map (K-map): meaning and examples
• Gray code: meaning and examples
• Prime implicant: meaning and examples
• Four-variable K-map: Σm(0, 2, 5, 7, 8, 10, 13, 15) simplified
• Karnaugh map vs Quine–McCluskey
• Lesson 10: Normal forms: DNF, CNF, minterms, and maxterms (advanced, 15 min)

Lessons

• Lesson 1: NOT, AND, OR: the basic operators (beginner, 10 min)
• Lesson 2: XOR: exclusive OR and parity (beginner, 10 min)
• Lesson 3: Grouping and precedence (beginner, 12 min)
• Lesson 4: Truth tables (beginner, 12 min)

Generated from the Tangibool engine, semantics tangibool-semantics/1, engine 1.0.0, build 2026-11-07. Every table, map, simplification and verdict on these pages was computed by the Tangibool engine when the site was built, and every claim was re-checked by the same exact checker the app uses. Limits are stated where they apply. © 2026 Foreranger LTD.