Demo 4.6: Reading the Map
Everything you have done so far has depended on noticing things. Spotting that a term has the shape of the absorption rule, spotting that a bar should come off before the one underneath it, spotting that an expression needs to get bigger before it can get smaller. That works, and it is worth being able to do, and it is not something you can rely on at nine in the morning under exam conditions.
Maurice Karnaugh, working at Bell Labs in 1953 on telephone switching logic, produced a way of getting the same answers without the noticing. His method replaces judgement with a procedure: draw the truth table in a particular arrangement, circle the largest rectangles you can find, and read the answer off. It is faster than algebra, it is much harder to get wrong, and it tells you when you have finished.
The arrangement is the whole trick. A Karnaugh map is a truth table with its rows moved around, and the order they are moved into is chosen so that cells sitting next to each other on the page differ in exactly one variable. Once that is true, a pair of neighbouring 1s means “these two rows agree about everything except one thing, so that thing does not matter”, which is a literal disappearing from a product term.
This demonstration covers two and three variables. Four-variable maps, which wrap in both directions at once, and don’t-care cells come next.
How to use it
Section titled “How to use it”Why this layout puts a truth table beside a map. Click any output value in the table to change it and watch the corresponding cell fill. Click a cell on the map and the four cells physically touching it are marked, counting round the edges.
Then use the switch above them to put the columns into plain binary order instead of Gray code. Click around the map again. Cells that still look adjacent are now marked in rose, because they differ in two variables rather than one. That is the argument for Gray code in a single click, and it is worth spending a minute on.
Switch back afterwards and leave it there. Plain binary is in the demonstration only so that you can see what goes wrong without Gray code. Every map in this module, and every map you are asked to draw, has its columns in the order 00, 01, 11, 10.
Group it yourself has five short puzzles. Click cells to build a group and you are told at once whether it is legal, and if it is not, exactly what is wrong with it. Add the group and it appears as a coloured ring on the map and a product term in the list. The circuit you have designed is drawn as you go.
When every 1 is covered you are told whether your answer is a cheapest one. That is worked out by searching every possible grouping rather than by comparing against a stored answer, so if there is more than one cheapest solution, yours will be accepted.
Karnaugh Maps
Finding the cheapest circuit by looking at a picture instead of by being clever with algebra.
Walkthrough
Section titled “Walkthrough”Step 1: Find out why the order matters
Section titled “Step 1: Find out why the order matters”Open Why this layout and click the cell in the map for A = 0, B = 0, C = 0. Four cells light up, and the message underneath tells you that every one of them differs from your cell in exactly one variable. Notice that two of those four are reached by going off one edge of the map and reappearing at the other.
Now switch the columns to Plain binary and click the same cell, then a few of its neighbours.
Some of the cells physically touching your cell are now marked in rose. Under binary order the columns run 00, 01, 10, 11, so the second and third columns differ in two bits at once. Two cells sitting side by side no longer have anything in common, and a group drawn over them would simplify to nothing at all.
That is why the columns run 00, 01, 11, 10. It is not a convention anyone chose for the look of it, and it is not something to memorise. It is the only ordering in which physical closeness on the page means logical closeness in the function.
Step 2: Watch what a group actually does
Section titled “Step 2: Watch what a group actually does”Switch back to Gray code and open Group it yourself on First group. Two 1s on a two-variable map. Select both.
Before you add the group, read the message. It tells you the group is legal and gives you its product term. The two cells agree that B = 1 and disagree about A, so A takes both values across the group and cannot be part of what decides the output. It drops out, and one literal has gone.
That is all a group ever does. Keep the variables that stay the same across the cells, discard the ones that vary. A group of two loses one literal, a group of four loses two, a group of eight loses three. Larger groups are cheaper for exactly that reason.
Step 3: Learn not to stop too early
Section titled “Step 3: Learn not to stop too early”Select Do not stop early. Three 1s on a two-variable map.
Group the column of two first. There is one 1 left over, and the obvious thing is to take it on its own as a group of one, which is perfectly legal. Do that and see what happens: you are told the answer is correct but not the cheapest, along with what the cheapest costs.
That message is worth reading carefully. Your circuit works. It would pass every test you gave it and it would function correctly on a board for twenty years. It simply costs more than it needs to, and nothing about testing it would ever reveal that.
Press Start over and do it again, but this time pair the leftover 1 with the cell next to it, the one already inside your first group. Cells may belong to as many groups as you like, and reusing them is not a loophole, it is how larger groups get formed at all. This one habit accounts for most of the difference between students who get minimal answers and students who do not.
Step 4: Fall off the edge of the map
Section titled “Step 4: Fall off the edge of the map”Select Off the edge. Four 1s, sitting in the leftmost and rightmost columns, about as far apart as it is possible to be on the page.
They are a single group of four. Select all four and the demonstration confirms it.
The reason is the column ordering again. The first column is 00 and the last is 10, which differ in one bit, so they are neighbours in the only sense that counts. Roll the map into a cylinder and they are touching. A map has no edges, and the drawing is a flat representation of something that wraps.
Look at how the group is drawn. It appears as two boxes, one at each edge, and each one is left open on the side facing the edge. That is deliberate and it is the convention you should use when sketching by hand. Closing the boxes would suggest a boundary that is not there and would make one group look like two.
Missing a wrapping group is the most common way of ending up with a more expensive answer than necessary, because there is nothing on the page to suggest the two halves belong together.
Step 5: Put both ideas together, and look at what you built
Section titled “Step 5: Put both ideas together, and look at what you built”Select Both at once. Six 1s, and the cheapest answer is two groups of four that share two cells between them, one of which wraps round the edge.
Take your time. If you get stuck, group four cells that clearly belong together first and see what is left over.
When you have it, look at the circuit drawn underneath. Six 1s on a map means six rows of the truth table producing an output, and writing that straight out as a sum of products would give six product terms of three literals each: six AND gates with three inputs apiece and a six-input OR gate. What you have instead is two gates.
That reduction took you about a minute and required no algebra, no judgement about when to make an expression bigger, and no risk of misapplying a rule. That is what Karnaugh maps are for.
Check your understanding
Section titled “Check your understanding”Why do the columns of a three-variable Karnaugh map run 00, 01, 11, 10 instead of 00, 01, 10, 11?
Which of these are legal groups on a Karnaugh map? Select all that apply.
Match each idea to what it does for you
You cover every 1 on a map and produce a working expression, but it uses three product terms where two would do. What has gone wrong with the circuit?
A three-variable map has four 1s in the leftmost and rightmost columns. What should you do?
Wrap-up
Section titled “Wrap-up”A Karnaugh map turns simplification from something you have to be clever at into something you can be systematic about. Write the truth table into the map, find the largest groups you can, read the terms off.
Four things to carry forward.
- The ordering is the idea. Gray code makes physical closeness on the page mean logical closeness in the function, and nothing else about the map works without it.
- A group discards the variables that vary across it. Bigger groups discard more, so always take the largest group a cell can belong to rather than the first one you see.
- The map wraps, and cells can be reused. These are the two places where larger groups hide, and missing them is what separates a correct answer from a cheap one.
- Covering the 1s gives a correct circuit. Only covering them with the largest possible groups gives the cheapest one, and testing will never tell you the difference.
Everything here has been at two or three variables, where you could probably have got the same answers with algebra. That is deliberate: the method is easier to trust on problems you can check by hand.
The next demonstration moves to four variables, where the map is sixteen cells and wraps top to bottom as well as left to right, and where the algebra genuinely does become too tedious to be reliable. It also introduces don’t-care cells, which cover the common situation where some input combinations simply cannot happen and you are free to choose whatever output makes the circuit cheapest.
© 2026 Derek Molloy, Dublin City University. All rights reserved.