Truth tables up to renaming

A formula of three letters is a set of corners of a cube: the eight rows of its truth table are the eight corners, and the function picks out the corners where it is true. There are $2^8 = 256$ such sets, so 256 truth functions of three letters. Many of them are the same function in disguise. “$p$ and $q$” and “$q$ and $r$” differ only in which letters are used; “$p$ and $q$” and “$p$ and not $q$” differ by a negated input; “$p$ and $q$” and “not $p$ or not $q$” differ by negating the output. A circuit designer who has built one can build the others with the same gates and a few inverters.

Identify functions that differ by any combination of those three renamings — permuting the letters, negating some of them, negating the result — and the 256 functions of three letters collapse into fourteen classes. Four letters give 222 classes from 65,536 functions; five give 616,126 from about four billion.

Renamings as symmetries of the cube #

The three kinds of renaming are symmetries of the cube of rows. Permuting the letters permutes the cube’s axes; negating a letter reflects the cube across a midplane; together they form the full symmetry group of the cube, $2^n \cdot n!$ elements for $n$ letters — 48 for the ordinary cube. Negating the output is a different kind of move, swapping the filled and empty corners, and it doubles the group to 96 for three letters and 768 for four.

So the fourteen classes are the fourteen essentially different ways to colour the corners of a cube in two colours, where rotations and reflections of the cube and swapping the colours do not count as different. The figure shows them: the constants, which every renaming fixes or swaps; the parity function, true at alternate corners, which also has only one partner; single corners, opposite pairs, faces, and so on up to the colourings with no symmetry left at all, of which there are classes of 48.

The class sizes add up to 256, because every table is in exactly one class. A class’s size is the group’s size, 96, divided by the number of renamings that leave its functions unchanged — the orbit-stabiliser theorem — so a large class means a function with little symmetry and a small class one with a lot.

Two letters, done completely #

For two letters the whole classification fits in a paragraph. There are sixteen connectives of two letters, and up to the three renamings they fall into four classes. The two constants, always true and always false, form one class: negating the output swaps them, and nothing else moves them. The four functions that ignore one letter — $p$, not $p$, $q$, not $q$ — form another. The eight that are true at exactly one row or false at exactly one row form a third: “$p$ and $q$” becomes “$p$ and not $q$” by negating a letter, “$p$ or $q$” by negating everything, and so on round all eight. And exclusive or with its negation, “$p$ if and only if $q$”, form the fourth. Two plus four plus eight plus two is sixteen.

The classes say something a list of connectives hides. The familiar and, or, nand, nor and the two implications are all one function under renaming, which is why any of them can be built from any other with a few negations. Exclusive or is genuinely different: no renaming turns it into and, and no amount of negating inputs and outputs makes a parity gate out of an and-gate. That difference is the reason the two kinds of gate behave so differently in circuits — and why a map that puts neighbouring rows side by side makes and-like functions into single rectangles and parity into a chessboard that no rectangle can simplify.

With only permutations of the letters allowed, the same sixteen fall into twelve classes; with negated letters too, into six. Each extra kind of renaming merges classes, and the output negation, merging every function with its complement, roughly halves what is left.

Counting classes as an average #

Listing classes works for three and four letters. For more letters there are too many tables to list, and the number of classes comes from a theorem instead.

Burnside’s lemma says that the number of classes is the average, over the renamings in the group, of the number of tables each renaming leaves unchanged. The reason is a double count: a class of size $s$ is left unchanged, member by member, by $|G|/s$ renamings at each of its $s$ members, so each class contributes exactly $|G|$ to the total of fixed points, and dividing by $|G|$ counts the classes.

Counting the tables a renaming fixes is easy once the renaming is seen as a shuffle of the rows. A table is unchanged exactly when it is constant along every cycle of the shuffle, so a renaming that splits the eight rows into $c$ cycles fixes $2^c$ tables. A renaming that also negates the output fixes a table only if the table alternates along every cycle, which needs every cycle to have even length, and then it fixes $2^c$ of them too. The identity fixes all 256; a renaming that cycles the rows in two cycles of four fixes four. Summed over all 96, the fixed tables come to 1,344, and Burnside’s lemma gives $1{,}344/96 = 14$.

The same average for more letters needs only the cycle structures of the group’s elements acting on the rows, which is a small computation even when the tables are uncountably many in practice. Counting necklaces the same way — strings of beads up to rotation — proves Fermat’s little theorem, and the truth-table count is the same lemma applied to a larger group acting on a larger set.

One lemma, many counts #

Burnside’s lemma — which was known to Cauchy and Frobenius before William Burnside put it in a textbook in 1897 — is the standard tool wherever objects are counted up to symmetry, and the truth-table count is one of its cleanest applications. George Pólya extended it in 1937 into a method that counts not only the classes but the classes of each composition at once, by keeping track of how many cycles of each length every symmetry has; he built it to count chemical isomers, molecules that differ only in where identical atoms are attached to a symmetric skeleton.

The same averaging counts trees on labelled points up to relabelling, completed sudoku grids up to their symmetries, colourings of a cube’s faces up to rotation, and graphs up to isomorphism. In each case the hard part of the count — deciding which objects are secretly the same — is replaced by an easy part: for each symmetry, count the objects it leaves alone, which is usually a power of the number of colours raised to a number of cycles. Truth tables are colourings of the corners of a cube in two colours, and that is all the counts on this page are.

How many functions, up to renaming #

With Burnside’s lemma the counts run as far as anyone likes, and for up to four letters they can be checked by listing every class directly.

Up to permuting the letters alone, there are 4, 12, 80, 3,984 and 37,333,248 classes for one to five letters. Allowing negated letters as well, 3, 6, 22, 402 and 1,228,158. Allowing the output to be negated too, 2, 4, 14, 222, 616,126 — and for six letters, 200,253,952,527,184. The listings for two, three and four letters agree with Burnside’s averages in every case, which is a check on both.

For few letters the renamings cut the count by much less than the size of the group, because many functions are symmetric and their classes are small. For many letters they cut it by almost exactly the group’s size. That is visible in the figure as the curves running parallel at large $n$, separated by the logarithm of the group’s size, and it is the subject of the next figure but one.

The 222 classes of four letters #

The four-letter classes can all be listed, and their sizes show the distribution of symmetry.

Twenty-four classes have the full 768 tables — functions with no symmetry among the renamings at all — and they already hold more than a quarter of all four-letter tables. The most common size is 384, from functions with exactly one non-trivial symmetry, and the sizes fall away from there to the two classes of size two. The distribution is lopsided because a function with more symmetry has fewer relatives, and most of the tables live in the large classes.

Symmetry disappears as letters are added #

For three letters every table has some symmetry; for four, 28 per cent have none. The trend continues, and it can be measured without listing anything.

If every table had no symmetry, every class would have exactly $|G|$ tables and the number of classes would be exactly the number of tables divided by $|G|$. For five letters that naive count is 91 per cent of the true count; for six it is 99.95 per cent. Almost every function of six letters is moved by every renaming, so almost every class is full, and the count of classes is the count of tables divided by the group’s size, plus a correction that shrinks rapidly. The correction comes from the few symmetric functions, and those become a vanishing fraction because a symmetry is a strong constraint: a renaming with $c$ cycles on the rows fixes only $2^c$ of the $2^{2^n}$ tables, and $c$ is far smaller than $2^n$ for every renaming except the identity.

The size of the correction can be read off a single renaming. Swapping two letters leaves alone the half of the rows where those letters agree and pairs up the other half, so it splits the $2^n$ rows into $3 \cdot 2^{n-2}$ cycles and fixes $2^{3 \cdot 2^{n-2}}$ tables — a fraction $2^{-2^{n-2}}$ of all of them. For four letters that is one table in sixteen; for six, one in 65,536; for ten, one in $2^{256}$. Every other non-trivial renaming fixes an even smaller fraction, so the symmetric tables are swamped. This is a pattern that recurs wherever things are counted up to symmetry: graphs on many vertices almost all have no automorphisms, so the number of unlabelled graphs is the number of labelled ones divided by $n!$; necklaces of many beads almost all have no rotational symmetry. For truth functions it is the reason that, beyond a few letters, “how many essentially different functions are there?” has the simple answer “about all of them, divided by $2^{n+1} n!$”.

The most symmetric functions #

At the other end of the distribution are the functions that renamings mostly leave alone.

The two constants form one class of two tables. The parity of all four letters and its negation form another: negating any letter or the result turns parity into its negation and back, and permuting the letters leaves it unchanged, so 768 renamings produce only two tables. Next come classes of eight and twelve — functions that depend on the letters in highly symmetric ways, like being true on exactly half the cube along one axis. These are the functions that the sensitivity of a cube’s colouring and threshold gates treat as special cases, and their symmetry is what makes them easy to reason about.

Parity is the extreme in another sense too. It is fixed by every permutation of the letters and swapped by every negation, and it is also the function whose formulas in and, or and not must grow like the square of the number of letters — maximal symmetry in one sense, and a proved difficulty in another.

What the counts are used for #

The classes are not only a counting exercise. A logic synthesis program that wants the smallest circuit for every function of four letters needs to solve only 222 problems, not 65,536, because a circuit for one member of a class becomes a circuit for every other member by adding inverters and relabelling inputs. How many gates a truth table needs has been settled for every four-letter function in exactly that way, in a census Donald Knuth published: compute the smallest circuit for one representative of each class and read off the rest. For five letters the 616,126 classes are the reason the same exhaustive answer is at the edge of feasibility, and for six letters, with two hundred trillion classes, it is out of reach.

The same reduction is used to build lookup tables in programs that manipulate Boolean functions — a table indexed by class, with a canonical representative for each, so that a function can be classified by computing its canonical form and looked up in one step. The same idea, under the name Boolean matching, is how chip-design tools decide whether a small piece of a circuit can be implemented by a cell from a library: both are reduced to canonical forms under these renamings and compared, since a cell can be wired with its inputs permuted and inverted for free or nearly so. Computing the canonical form fast is its own problem, solved for practical sizes by clever search and believed hard in general.

What the counts cannot show #

Every count on this page is exact, and the listings and Burnside’s lemma agree wherever both are computed. What the counts do not show is any of the functions’ other properties. Two functions in the same class have the same circuit size and the same formula size, since renamings are free in circuits; but they need not have the same name in any human sense, and a class mixes functions that look nothing alike when written as formulas. The classes are a statement about symmetry under the three renamings and nothing else. Fixing letters to constants is a different operation again: setting $p$ to true leaves “$p$ and $q$” as $q$ but turns “not $p$ and $q$” into false, so two members of one class can respond differently to the same restriction — though over restrictions chosen at random, where every letter is equally likely to be fixed either way, the renamings even out and the whole class behaves alike.

The asymmetry figure also shows a trend through six letters and claims nothing beyond. That the correction vanishes as $n$ grows follows from the fixed-point counts in Burnside’s sum, which can be bounded for every $n$; the figure’s numbers illustrate that bound without proving it.

Still open: canonical forms quickly #

How quickly can a truth function’s class be identified? Given a truth table of $n$ letters, deciding whether two tables are in the same class is a special case of deciding whether two combinatorial objects are equivalent under a group, and for this group no method is known that is fast in the worst case as $n$ grows — the obvious method tries all $2^{n+1}n!$ renamings. Practical programs use invariants to prune the search and are fast on most inputs. Whether the problem is genuinely hard, or has a clever polynomial algorithm in the size of the table, is not settled; it is related to the graph isomorphism problem, whose status was itself transformed only in 2015, when László Babai gave an algorithm far faster than any before it.

Fourteen, as an average #

The 256 truth functions of three letters fall into fourteen classes up to permuting, negating letters and negating the result; four letters give 222, five 616,126, six 200,253,952,527,184. Burnside’s lemma computes each count as the average number of tables a renaming leaves unchanged, and for up to four letters a direct listing agrees. The classes are lopsided — a few tiny ones for the most symmetric functions, like the constants and parity, and many full ones for functions no renaming fixes — and as letters are added almost every function loses all symmetry, so the number of classes approaches the number of tables divided by the size of the group.