Maps of 5 or more variables

OK, OK. I am starting to get it, but all of this has been with 4 variables, right? What about functions with more variables?

Good question. A 4-variable map has 16 cells; with 5 it is 32, with 6 it is 64, and every extra variable doubles the map. That is when a strategy helps, and one of the most common is to split the problem into 4-variable sub-maps.

# 4-variable sub-maps

The idea is to fix the extra variables. With 5 variables (A, B, C, D and E) you draw a map of B, C, D and E for when A is 0, and an identical one for when A is 1. Each one is a 4-variable map like the ones you already know, and together they cover the 32 combinations. With 6 variables you fix A and B, and you get 4 sub-maps: AB = 00, 01, 11 and 10, in Gray code again.

In algebra this has a name, the Shannon expansion: the function is split into what it does when A is 0 and what it does when A is 1.

Inside each sub-map you group just like before. What is new is that you can now also group across sub-maps, and that brings a rule that is not so intuitive at first sight.

# Grouping across sub-maps

Picture the sub-maps one above the other, like the floors of a building. Two sub-maps are neighbours if their fixed variables differ in only one (A = 0 and A = 1, or AB = 01 and AB = 11). Then every cell is a neighbour of the one at the same position in the other sub-map, and a group can go through the floors.

The rules of the previous page still hold, and these are added:

1. A group across sub-maps takes exactly the same cells in each of them. The variables that tell those sub-maps apart change and drop out of the term.
2. The sub-maps involved are also 1, 2, 4… and they must be neighbours of each other. In fact the grid of sub-maps is itself a Karnaugh map of the fixed variables, with its rectangles and its touching edges. That way the whole group still has 2ⁿ cells.
3. Sub-maps that differ in two or more variables are not neighbours, even if they are close in the drawing. With 6 variables, AB = 00 and AB = 11 cannot be grouped together.
4. As in any Gray code, the list is cyclic: with 6 variables, the first sub-map (AB = 00) and the last one (AB = 10) are neighbours.

# Why doesn't the solver mirror the sub-maps?

If you look in textbooks you will see that many draw the second sub-map reversed, as a mirror of the first. In the solver (4-variable sub-maps option) and in the stacked view above we do not: all the sub-maps have the same orientation. That way the neighbours across sub-maps sit at exactly the same position, and comparing cell by cell is enough.

But the textbooks' mirror is not a whim either: it is what appears when you join the sub-maps into a single 5-variable map. Let's see it.

# From the stack to the full map: the reflection

In a single 5-variable map the columns carry 3 bits in Gray code: 000, 001, 011, 010, 110, 111, 101 and 100. The left half is A = 0 and the right half A = 1, and the BC bits on the right (10, 11, 01, 00) are the ones on the left in reverse. It is the reflected binary code again: the second half is the mirror of the first.

What was the same place on the upper and lower floors in the stacked view is, in the full map, a reflection about the axis that separates the two halves. Column 001 has its neighbour in column 101: at the same distance from the axis, but on the other side. And the columns touching the axis (010 and 110) are ordinary neighbours, side by side.

# And with 6, 7… n variables

The idea extends unchanged, as long as the right reflection is respected. With k bits on an axis, the reflected Gray code has a mirror axis in the middle; each half is itself a reflected code with its own axis in the middle, and so on down to pairs. Two positions on the same axis are neighbours if they are symmetric about one of those axes, inside the block that axis splits.

That is why every cell of an n-variable map has exactly n neighbours, one per variable: some next to it, some across the border and the rest by mirror. The solver draws the mirror axes as thicker lines, the thicker the larger the block they split. Pick the number of variables and tap a cell.

With that, the usual grouping rule can be stated in general: on each axis, a group takes the positions where some of that axis's variables are fixed and the rest take all their values. In a map of up to 4 variables that is a line or a contiguous block (counting the edges); with more variables it can be a block together with its mirrors. The total is still 2ⁿ cells, and a group split into several rectangles of the same color is still a single group.

# How far does this go?

In theory, to any number of variables. In practice, from 6 on the mirrors multiply and it is easy to get it wrong by eye. Luckily sub-maps are not the only way to arrange a large map: on the next page we will see another variant of the K-Map, proposed by Matthew V. Mahoney, the Mahoney maps or M-Maps. They are built by mirroring the map again and again, alternating each new variable between the columns and the rows, and that is why they extend naturally to any number of variables.