A Karnaugh map lays out a truth table as a grid in which neighbouring cells differ by just one input. Circling groups of 1s then gives the simplest sum-of-products expression directly, without pages of algebra. This lesson covers the layout, the grouping rules and how to solve a logic problem with a K-map.
A Karnaugh map (K-map) is a grid with one cell for each row of the truth table. The rows and columns are labelled in Gray code order (00, 01, 11, 10), so cells that are next to each other, including across the edges, differ in exactly one input. Each 1 is circled in a group of 1, 2, 4 or 8 neighbouring cells forming a rectangle; groups must be as large as possible and as few as possible, may overlap and may wrap round the edges. Each group gives one product term containing only the inputs that do not change inside it, and the terms are ORed together to give a sum of products. The benefit: a systematic, visual method that gives the simplest expression with less risk of error than Boolean algebra.
Fig. 1: a four-input K-map. The four corner cells are neighbours because the map wraps round, giving B.D; the centre square gives B.D
Section 01
Setting up the map.
Each cell is one row of the truth table. For three inputs, A labels the rows and BC the columns; for four inputs, AB labels the rows and CD the columns. The order 00, 01, 11, 10 is the key: 01 is followed by 11, not 10, so only one bit changes between neighbours.
Gray code: 00, 01, 11, 10. Each step changes one bit, and so does the jump from 10 back round to 00, which is why the map wraps round.
Filling it in: find the row of the truth table (for example A = 1, B = 0, C = 1) and put its output in the cell for row 1, column 01.
Why it works: two neighbouring 1s differ in one input only, so the term X.Y + X.Y = X: that input disappears. A group of four removes two inputs, a group of eight removes three.
Benefits over algebra: a systematic, visual method; easier to spot the groups than the right law; less chance of error; it always gives the simplest sum of products if the rules are followed.
The truth table and K-map for the lab's starting three-input example (1s for rows 1, 3, 4, 5 and 7):
A
B
C
X
0
0
0
0
0
0
1
1
0
1
0
0
0
1
1
1
1
0
0
1
1
0
1
1
1
1
0
0
1
1
1
1
A \ BC
00
01
11
10
0
0
1
1
0
1
1
1
1
0
Examiner trap
Labelling the columns 00, 01, 10, 11 (binary order) is the most common mistake: then neighbouring cells 01 and 10 differ in two inputs, and every group in that part of the map is wrong.
Section 02
The grouping rules.
Click the cells of the map in the lab to add 1s, and watch the groups and the simplest expression appear. Try making groups that wrap round the edges and the four corners.
Groups contain only 1s, and their size must be a power of 2: 1, 2, 4 or 8. A group of 3 or 6 is never allowed.
Groups are rectangles (rows or squares), never diagonal.
Make each group as large as possible, and use as few groups as possible.
Groups may overlap: a 1 can be in more than one group if that makes a group bigger.
Groups may wrap round from the left edge to the right edge, from the top to the bottom, and the four corners of a four-input map form one group.
For each group, keep only the inputs that have the same value in every cell of the group: write the letter if it is 1 throughout, with a bar if it is 0 throughout.
Worked example A three-input map
Find the simplest expression for the K-map below.
A \ BC
00
01
11
10
0
0
1
1
0
1
1
1
1
0
The whole column BC = 01 and the whole column BC = 11 are 1s: together they make a square of four. In these cells C = 1 throughout, while A and B both change, so the group gives C.
The 1 in row A = 1, column 00 is not yet covered. Group it with its neighbour in column 01 (overlapping the first group), making a pair.
In that pair A = 1 and B = 0 throughout, while C changes: the term is A.B.
OR the terms together.
Answer: X = C + A.B
Worked example Corners and wrap-round
Find the simplest expression for the four-input K-map in Fig. 1 (1s in cells 0, 2, 5, 7, 8, 10, 13 and 15).
The four corner cells (0, 2, 8, 10) are all 1s and are neighbours because the map wraps round. In them B = 0 and D = 0 throughout: B.D.
The centre square (5, 7, 13, 15) has B = 1 and D = 1 throughout: B.D.
Every 1 is now in a group of four, the largest possible.
Answer: X = B.D + B.D
Your turn
Find the simplest expression for this map.
AB \ CD
00
01
11
10
00
1
0
0
1
01
1
0
1
1
11
1
0
1
1
10
1
0
0
1
The columns CD = 00 and CD = 10 are neighbours (wrap round) and are all 1s: a group of eight with D = 0, giving D. Cells 7, 15, 6 and 14 make a square with B = 1 and C = 1, giving B.C. X = D + B.C.
Examiner trap
Do not stop at the first groups you see. A pair inside a possible group of four gives a term with an extra letter, which loses the simplification mark.
Stage 1 · Learn
Check what the sim just showed you
Four quick checks. Each correct answer earns XP and records this skill on your profile.
Quick check+10 XP
Why are the columns of a K-map labelled 00, 01, 11, 10?
Quick check+10 XP
Which group size is NOT allowed in a K-map?
Quick check+10 XP
In a four-input K-map, how many letters are in the term from a group of four 1s?
Quick check+10 XP
In the lab's starting three-input map (1s in cells 1, 3, 4, 5 and 7), which expression appears?
Section 03
Solving a logic problem.
Exam questions often start with a problem statement. Work in a fixed order: truth table, K-map, groups, expression, then the circuit if asked.
Worked example A majority vote
Three judges press a button (A, B, C) to pass a contestant. The light X comes on if at least two judges press their buttons. Find the simplest expression for X.
Truth table: X = 1 for the rows 011, 101, 110 and 111 (rows 3, 5, 6 and 7).
A
B
C
X
0
0
0
0
0
0
1
0
0
1
0
0
0
1
1
1
1
0
0
0
1
0
1
1
1
1
0
1
1
1
1
1
Put the 1s into the K-map.
A \ BC
00
01
11
10
0
0
0
1
0
1
0
1
1
1
Cell 7 (A = B = C = 1) has three neighbouring 1s. No group of four fits, so make three overlapping pairs: cells 6 and 7 give A.B; cells 5 and 7 give A.C; cells 3 and 7 give B.C.
OR the three terms together. Check: the canonical expression had four terms of three letters; the result has three terms of two letters.
Answer: X = A.B + A.C + B.C
Your turn
A sprinkler X switches on when the water tank is not empty (B = 1) and at least one of these is true: the soil is dry (A = 1), the temperature is high (C = 1), the timer is on (D = 1). Use a K-map to find the simplest sum-of-products expression.
The 1s are cells 5, 6, 7, 12, 13, 14 and 15 (the rows AB = 01 and AB = 11 except cell 4).
AB \ CD
00
01
11
10
00
0
0
0
0
01
0
1
1
1
11
1
1
1
1
10
0
0
0
0
Groups of four: row 11 gives A.B; columns 01 and 11 in the middle two rows give B.D; columns 11 and 10 in the middle two rows give B.C. X = A.B + B.C + B.D, which is B.(A + C + D).
Examiner trap
Every group must be checked for the inputs that stay the same. If an input is 0 in some cells of a group and 1 in others, it must not appear in that term.
Stage 2 · Exam
Exam-style questions
Unlocks once the four checks above are done. Worth more XP, written to A Level Paper 3 and Paper 4 standard.
Finish the four checks above to unlock the exam questions
Exam style+20 XP
In a four-input K-map the only 1s are in the four corners. What is the expression?
Exam style+20 XP
A three-input function is 1 for rows 3, 5, 6 and 7 only. What is its simplest expression?
Exam style+20 XP
Which is a benefit of using a Karnaugh map rather than Boolean algebra?
Exam style+20 XP
A three-input function is 1 for rows 0, 1, 2 and 3 only. What does the K-map give?
Skill unlocked
Karnaugh maps, mastered.
This skill is now recorded on your profile. Keep the chain going.