Demo 4.7: Bigger Maps and Cells That Do Not Matter
The previous demonstration covered maps of four and eight cells, where you could have checked the answers with algebra if you had wanted to. This one covers sixteen, which is where the algebra stops being worth attempting and the map starts earning its keep.
Two things are genuinely new. The map now wraps top to bottom as well as left to right, which means the four corners of the page are a single group and the top and bottom rows are neighbours. And some circuits have input combinations that simply cannot occur, in which case the output on those rows is yours to choose, and choosing well can collapse a circuit to almost nothing.
Before either of those, though, there is a question worth getting into the habit of asking.
Reading a group
Section titled “Reading a group”When you draw a group and want to know what it says, do not try to recognise the shape. Ask instead:
Which variables did not change across this group?
Write the cells out, one row each, one column per variable, and look down each column in turn. Three things can happen.
- The column is 1 all the way down. That variable is held at 1, so its letter goes into the term.
- The column is 0 all the way down. That variable is held at 0, so its letter goes into the term complemented.
- The column has both a 0 and a 1 in it somewhere. That variable is not deciding anything, because the output is 1 whichever value it takes, so it is left out of the term entirely.
That last case is the one that does the work. If A = 1 appears somewhere in your group and A = 0 appears somewhere else in it, then A cannot be part of what makes the output high, and A disappears.
This is why group size and cost are related so tightly. A group of two has one column with both values in it, so one variable drops out. A group of four has two such columns, a group of eight has three, and a group of sixteen has all four and reduces to the constant 1. Every doubling of the group frees one more variable, and that is where the saving comes from.
The demonstration shows this table for every group, everywhere, including while you are still selecting cells.
How to use it
Section titled “How to use it”Reading a group has nothing to solve. Every cell holds a 1 so that any legal selection works, and there are preset examples along the top for the shapes worth seeing. Select cells and read the workings.
Group it yourself has seven four-variable puzzles. As before, you are told whether your cover is a cheapest one, and that is worked out by searching every possible grouping rather than by comparing against a stored answer.
Cells that don’t matter has four puzzles containing cells marked with a star, meaning that input combination cannot happen. Take a star into a group when it makes the group bigger and leave it alone otherwise.
Bigger Maps, and Cells That Do Not Matter
Four-variable maps, and what to do about input combinations that can never happen.
Walkthrough
Section titled “Walkthrough”Step 1: Read a group you would not have guessed
Section titled “Step 1: Read a group you would not have guessed”Open Reading a group and press The four corners.
Four 1s, one in each corner of the map, about as far apart as anything can be on the page. Look at the workings rather than the picture. The B column reads 0, 0, 0, 0 and the D column reads 0, 0, 0, 0, while A and C each contain both values. So B and D are held, A and C drop out, and the term is B̄·D̄.
Nothing about that reading required you to believe the corners are adjacent. You wrote the cells down and looked at the columns, and the answer came out. That is the point of doing it this way: the procedure does not depend on your intuition about the shape being correct.
Now press One cell, then A pair, then Four in a row, then Eight cells, and watch the literal count fall from four to three to two to one. Each doubling of the group puts both values into one more column and frees one more variable.
Step 2: Two groups instead of seven terms
Section titled “Step 2: Two groups instead of seven terms”Open Group it yourself and select Two fours.
Seven cells hold a 1. Written straight out of the truth table that is seven product terms of four literals each: seven AND gates with four inputs, feeding a seven-input OR. Twenty-eight gate inputs.
Find the horizontal group of four and the vertical group of four. They cross at one cell, which belongs to both. Two terms of two literals, six gate inputs in total, and the circuit drawn underneath is small enough to build on a single chip.
Read the workings for each group as you add it. For the horizontal one, A and B hold and C and D vary. For the vertical one, C and D hold and A and B vary. The same map, the same method, opposite answers.
Step 3: Wrap in both directions
Section titled “Step 3: Wrap in both directions”Select Four corners, then Top and bottom.
The corners you have already read. The second one is the vertical version of the same idea: the rows are labelled 00, 01, 11, 10 down the side, exactly as the columns are along the top, so the first and last rows differ in one bit and are neighbours. The top row and the bottom row together make a group of eight.
Watch how the demonstration draws these. A group that leaves one edge and reappears at the other is shown as two boxes, each left open on the side facing the edge. Use that convention when you sketch by hand. Closing the boxes would suggest a boundary that is not there and would make one group look like two.
Step 4: Learn to stop
Section titled “Step 4: Learn to stop”Select One too many. Eight 1s, and there are three groups of four to be found.
Find them all. Then notice that once you have any two of them, every 1 on the map is already covered, and the third adds a gate and three inputs while changing nothing. The demonstration marks it as not needed and tells you your answer is correct but no longer the cheapest.
This is worth dwelling on because it inverts the habit the earlier puzzles built. Up to now the message has been to look for bigger groups. Here is a group that is exactly as big as the others, perfectly legal, and pure waste. The rule is not “find every group”, it is “cover every 1 as cheaply as possible, then stop”.
Step 5: Use the rows that cannot happen
Section titled “Step 5: Use the rows that cannot happen”Open Cells that don’t matter and select Lamp 4.
A three-bit converter reports pedalling speed on a museum exhibit as codes 000 through 101. The codes 110 and 111 cannot occur, so they are marked with a star. This lamp should light for 100 and 101.
Group just the two 1s first. That gives a legal, correct answer, and the demonstration tells you it is not the cheapest. Start over and take the two stars in as well, making a group of four. Read the workings: A is held at 1, and B and C now both contain 0 and 1, so both drop out. The lamp wires directly to the most significant bit of the converter and needs no gate at all.
You did not change the circuit’s behaviour on any row anyone will ever see. You chose the output on two rows that cannot occur, and chose them to make the group bigger.
Then try Even digit, where six impossible codes turn a five-cell problem into a single group of eight and the entire circuit becomes one inverter. Finally Five or more, which is the comparison a seven-segment driver or a rounding circuit has to make, and which uses stars in all three of its groups.
One caution the demonstration enforces: a group made of nothing but stars is refused. Covering rows that cannot happen buys nothing and costs a gate.
Check your understanding
Section titled “Check your understanding”A group of four cells on a four-variable map. Across those cells, A is 1 every time, B is 0 every time, and C and D each take both values. What is the term?
Which of these are true of a four-variable Karnaugh map? Select all that apply.
Match each observation about a group to what it tells you
A four-bit input holds a decimal digit, so the patterns 1010 to 1111 never occur. How should those six cells be treated on the map?
Why can a group never contain three cells, or six?
Wrap-up
Section titled “Wrap-up”Four-variable maps are the largest size worth doing by hand, and they cover most of what you will meet in this module. Beyond four variables the maps have to be stacked or overlaid and the visual advantage evaporates, which is the point at which the work moves to software.
Four things to carry forward.
- Read a group by asking which variables did not change. Held at 1 gives the letter, held at 0 gives the letter complemented, and taking both values means the variable drops out. That procedure works on any group on any map.
- Group size and literal count are the same fact twice. Every doubling of the group frees one more variable, which is the whole reason larger groups are cheaper.
- The map wraps both ways. The four corners are a group, the top and bottom rows are adjacent, and the drawing convention is to leave a wrapping group open on the side facing the edge.
- Cover every 1 as cheaply as you can and then stop. A group can be legal, large and completely unnecessary, and don’t cares are an opportunity rather than something you have to use.
You now have three ways of getting from a specification to a circuit. Boolean algebra, which is flexible and requires judgement. De Morgan’s theorems, which move inversions around so a circuit can be built from the parts you can actually buy. And Karnaugh maps, which find a cheapest answer by procedure rather than by insight.
What comes next puts them to work. Combinational logic takes real specifications, adders, comparators, decoders and multiplexers, and turns them into circuits using exactly these tools, at which point the reason for all of it becomes considerably more obvious.
© 2026 Derek Molloy, Dublin City University. All rights reserved.