The map that puts neighbours side by side

Every truth function has a formula, and the construction that produces one produces a bad one.

Take the rows that came out true, describe each completely, and string the descriptions together with ∨. A function true in half of sixteen rows gets a formula with eight terms of four letters each — thirty-two letters for something that might be sayable in three. The construction proves that a formula exists. Nothing in it makes an effort.

The improvement is not an algebraic trick. It is a change of address.

Why the order is not counting order #

The columns run $00, 01, 11, 10$, which looks like a mistake and is the whole method.

In counting order the third column would be $10$, and $01$ and $10$ differ in two letters. So two squares side by side would sometimes be one change apart and sometimes two, and nothing about being side by side would mean anything.

The order used instead is a Gray code: consecutive entries differ in exactly one bit, and the last entry differs from the first in exactly one bit as well. It exists for every length that is a power of two, and it is built by reflection — write the code for $n-1$ bits, write it again backwards, put a $0$ in front of the first copy and a $1$ in front of the second. The join in the middle is where the two copies meet, and the reflection is exactly what makes it a single change.

The consequence is worth stating plainly, because it is what the rest of the essay lives on. Two squares that touch on this grid differ in one letter, and squares that touch round the edges do too. The grid is not a rectangle with an interior and a boundary; it is the surface of a torus, drawn flat with the seams cut open, and its adjacency is the adjacency of the cube of assignments with the surface unrolled.

What a rectangle is #

Now the payoff. Shade the squares where the function is true.

A rectangle on this grid, of width and height a power of two and allowed to wrap round the edges, corresponds to a conjunction of literals: the letters that are constant across the rectangle, each in whichever form it takes there, and the letters that vary are simply left out.

That is the correspondence the whole method rests on, and it goes both ways. A single square is a conjunction of all the letters. A rectangle of two squares drops one letter. A rectangle of four drops two. A rectangle covering the whole map drops all of them and is the constant true.

So short formula and large rectangle are the same thing said twice, and the problem “write this function shortly” becomes “cover these squares with few large rectangles”.

Covering, and the two words for a good rectangle #

A rectangle entirely inside the shaded set is called an implicant: everything in it makes the function true, so the corresponding conjunction implies the function.

An implicant is prime when it cannot be enlarged — every way of doubling it takes in a square where the function is false. Those are the rectangles worth using, because using a non-prime one means having written a longer conjunction than necessary.

Three prime implicants and only two needed. That is the ordinary situation, and it is the reason minimisation is a search rather than a formula: the primes are found first, and then a subset of them has to be chosen. Choosing badly gives a correct formula that is longer than it needed to be, and nothing local settles which primes to keep.

The generator does the choosing by brute force — every subset of the primes, smallest first, until one covers everything — which is honest at this size and would not be at any size. That is not a shortcoming of the drawing. Choosing a smallest cover from a set of primes is the set-cover problem, and set cover is one of the standard hard problems. The map makes the primes visible; it does not make the choice easy, and at four variables a person doing it by eye is doing something that stops working at eight.

Four variables, where it earns its keep #

Three variables is a demonstration. Four is where the method was actually used.

The wrapping rectangle is the piece that a table cannot show and a person using the map has to be told about once. Squares in the first and last column are neighbours, and so are squares in the first and last row; the four corners of the map form a $2×2$ rectangle. The map is a flat drawing of a surface that has no edge, and the seams are where the reader has to supply what the paper cannot.

Six primes, three used. Half the primes are redundant, and which half is not visible until the cover is chosen.

Reading a formula off the picture, and the two mistakes #

It is worth walking one map slowly, because the two errors people make are both errors of not trusting the correspondence.

A rectangle of four squares in a four-variable map drops two letters and keeps two. Which two is not a choice: they are the letters whose value is the same at every square of the rectangle, and the other two vary within it and are therefore irrelevant to it. A reader who writes down three letters for a rectangle of four has kept a letter that varies, and the resulting conjunction is not an implicant — it is false somewhere inside its own rectangle.

The first mistake is using rectangles that are not maximal. A $1×2$ block sitting inside a $2×2$ block is a legal implicant and a wasteful one: it names one more letter than it needs to. Nothing about the drawing punishes it, and the resulting formula is correct. It is simply longer, and since the entire point of the exercise is length, a correct-but-long answer is a failed answer that looks like a success.

The second is missing the wrap. Two squares in the first and last columns are neighbours, and so are the four corners. A reader who treats the map as a rectangle with a boundary sees a scattering of isolated squares where there is a single rectangle, and again produces a correct, longer formula. This is the error that the drawing actively invites: the seams are the one piece of information the flat picture cannot carry, and the reader has to hold it.

Both mistakes have the same signature — a correct formula that is longer than necessary — which means neither is caught by checking the answer. Only comparing against a smaller answer catches them, and there is nothing to compare against unless the smaller answer has already been found. That is why the figures here compute the minimum by exhaustive search over subsets of the primes rather than by following the eye: the search cannot miss a rectangle, and it cannot forget a seam.

Where the method has nothing to offer #

Every technique in this field has a case it was not built for, and it is more useful to know the case than the technique.

Parity is the worst case for this method and it is worth understanding why, because the reason is structural rather than unlucky.

Changing any one letter flips the value of exclusive-or. That is what exclusive-or is. So no two adjacent squares ever agree, the shaded set contains no domino, and every prime implicant is a single square. The minimal cover has four terms of three letters each, which is exactly the formula the mechanical construction produced at the start of this essay. The method achieved nothing.

And the failure is not a small corner of the space. There are eight such functions on three letters — parity, its negation, and the versions on each subset of the letters — but the deeper point is that the property responsible, changing one input always changes the output, is precisely the property the map’s whole layout was designed to exploit. The map wins when neighbouring assignments agree. Parity is the function for which neighbouring assignments never agree, and the better a method is at exploiting local agreement, the worse it does on a function with none.

The same function is the standard hard case elsewhere for the same reason. It is the affine class that stopped exclusive-or’s own closure at eight functions, and it is the reason ⊕ and ∧ together reach 128 and no further. A function with no local structure is invisible to every method that reads local structure, and there is no repair.

The other normal form, drawn the same way #

Everything above has been about the shaded squares. There is a mirror-image method that works from the unshaded ones, and it is worth a paragraph because the symmetry is exact and the two answers are usually different lengths.

Cover the false squares with rectangles instead. Each such rectangle is a conjunction of literals that is true exactly there, so its negation is a disjunction of literals that is false exactly there — and stringing those disjunctions together with ∧ gives a formula false at precisely the false squares, which is to say the original function. That is conjunctive normal form, obtained by running the identical procedure on the complement.

Nothing says the two covers have the same size. A function with four true squares in a twelve-square map has a small job on one side and a large one on the other, and which side is cheaper depends entirely on the function. So a minimisation is really two minimisations, and the shorter answer wins.

That is a small observation with a long shadow. The two normal forms are not two notations for one thing; they are two coverings of two complementary sets, and the asymmetry between them is the reason that converting a formula from one to the other can blow up exponentially. Parity is again the example: it is $2^{n-1}$ terms in either form, so neither side helps, and a function that is one short clause in one form can need exponentially many terms in the other.

The cube again, and what the map threw away #

It is worth putting the two pictures side by side, because the map is the cube with something removed.

What the cube keeps is shape: a subcube is a face, an edge, a corner, and the dimension of the piece is the number of letters dropped. What the map keeps is adjacency on a page, which is the part a person can scan.

What the map gives up is honesty about the geometry. The cube has no seams; the map has two, and a reader who forgets them will miss the wrapping rectangles every time. That is the standard trade for a flat drawing of a surface that does not want to be flat — the same trade, in a very different subject, that a map of the sphere has to make, and for the same reason: something has to be cut before anything can be laid out.

At five variables the trade stops paying. The map becomes two four-variable maps side by side with adjacency between corresponding squares, which is no longer something the eye reads; at six it is four maps. Beyond that the drawing has stopped helping and the algorithms take over. Quine and McCluskey turned the same idea into a procedure that does not need a picture, and modern minimisers do not resemble either.

What it was actually used for #

The method has a date and a purpose, and both are worth stating because they explain the shape it has.

Maurice Karnaugh published it in 1953, at Bell Labs, for designing switching circuits — relay networks and then transistor logic, where a formula is a piece of hardware and every term in it is components that cost money, take up space and can fail. Edward Veitch had published a similar chart a year earlier with the rows in a different order; Karnaugh’s contribution was the Gray code, which is the only part that matters.

That origin explains two things about the technique that look arbitrary from a purely logical standpoint.

It stops at four or five variables because a designer’s problems did. A circuit block with more inputs than that was decomposed into smaller blocks before anyone reached for a map, so the method was never asked to scale and was not built to.

It cares about term count rather than about anything a logician would measure. Two formulas with the same number of terms are equally good here even if one is far easier to reason about, because the thing being minimised is gates. A method built for proof rather than for hardware would count something else and would look different.

There is a third feature that only makes sense from the hardware side and is worth knowing about, because it is where the method is still genuinely useful: don’t-care squares. A designer often knows that certain input combinations never occur — a four-bit code where only ten of the sixteen values are legal, for instance. Those squares can be filled in either way, whichever makes the rectangles bigger, and the freedom is often worth more than the cleverness. A map with six don’t-cares in it frequently minimises to half the size of the same function with those squares forced, and there is no way to see that from a formula.

What survives when the drawing does not #

That is the honest closing note, and it is not the usual one.

The map is obsolete as a tool. Nobody minimises a twenty-variable function by eye, and nobody has for a long time. What survives is the reformulation, and the reformulation is what mattered all along: a formula is a covering of a set of corners by subcubes, and shortness is largeness of pieces. Every method that came after, including the ones that never draw anything, is working on that problem.

That is worth separating from the drawing carefully. The picture is a way of seeing a covering problem at a size where a person can see it. The covering problem is what is true. A reader who takes away only the grid has taken the disposable half; a reader who takes away shortness is a geometry has the part that is still load-bearing three sizes past the point where the grid can be printed.

There is a last observation that belongs to this collection rather than to the subject. The map’s whole content is an ordering — a Gray code, chosen so that neighbours are neighbours — and the ordering is not a fact about truth functions at all. It is a fact about how to lay them out. Nothing was proved by drawing the map; what was gained was that the proof became visible, which is a different thing and is the claim this site is built around. The same shaded set in counting order is the same function and shows nothing, and the difference between the two pictures is entirely in where the squares were put.