What an incomplete set of connectives can say

One connective is enough settled the most famous question about connectives: which sets of them can express every truth function? Nand can, alone, and so can nor; and and or together cannot, however they are combined, because everything built from them is monotone — turning an input from false to true never turns the output from true to false — and some truth functions are not. Emil Post found in 1941 that exactly five such obstacles exist. A set of connectives is complete if and only if, for each of five classes — the functions that keep false as false, the functions that keep true as true, the monotone functions, the self-dual functions, the affine functions — it contains at least one connective outside the class.

That is a statement about the top of a structure. Every set of connectives, complete or not, expresses something, and what it expresses is closed in a precise sense: anything built from things it can express can also be expressed. Such a closed set of truth functions is called a clone, and Post’s achievement was not only the completeness criterion but a description of every clone there is. This essay computes the clones’ footprints on three letters — the 256 truth functions of $x$, $y$ and $z$ — and draws the part of Post’s picture that lies below the top.

Closing up #

What a set of connectives can express is computed by closure. Start with the three projections — the functions that just return $x$, $y$ or $z$, written as their truth tables, eight bits each. Feed any of them into a connective, in any combination, and add the result to the list; then do it again with the longer list, and again, until nothing new appears. Every function on the final list can be written as a formula in $x$, $y$, $z$ and the connectives, and every such formula’s function is on the list, so the list is the three-letter part of the clone the connectives generate. A truth function of three letters is a choice of true or false at each of the eight corners of a cube, so its truth table is an eight-bit number from 0 to 255, and the 256 numbers are the 256 functions. The projection $x$ is the number whose bits are set exactly at the corners where $x$ is true, 240 in the numbering used here, and $y$ and $z$ are 204 and 170. With truth tables as eight-bit numbers, applying a connective to three tables is a handful of bitwise operations, and every closure in this essay finishes in a fraction of a second.

The hero runs the closure for each of the sixteen binary connectives. Two of them, nand and nor, reach all 256 functions. The rest stop well short. And reaches only 7: $x$, $y$, $z$, the three pairwise conjunctions and the conjunction of all three. Or reaches the mirror-image 7. Xor and iff reach 8 each, and the two implications and their negations reach 38. The constant connectives, false and true, add a constant to the three projections and reach 4; the projections themselves reach only 3.

The table of properties says why. And is monotone, keeps false, keeps true — three of the five classes contain it, and its clone is inside all three. Xor keeps false and is affine, a sum modulo two of its inputs, and everything built from sums modulo two is again such a sum; there are only eight such functions of three letters without a constant term. Implication escapes four classes and is caught by only one, keeping true, which is why it expresses so much more than the others — 38 functions, every one of them true when all three letters are true.

Pairs #

Two connectives together express everything when, between them, they escape all five classes.

Of the 120 pairs of different connectives, 53 are complete, and in all 136 cells of the triangle — each connective alone and each pair — the closure computed directly agrees with Post’s criterion, which needs no closure at all. Implication with false is complete, which is the classical presentation of propositional logic with $\to$ and $\bot$. And with not is complete, and or with not, and xor with and — provided the constant true can be made, which it cannot from xor and and alone, so that pair falls short and needs a constant. Counting the 53 is a small exercise in the criterion. A pair escapes the keep-false class if either connective turns all-false into true, and similarly for the other four classes; the 53 complete pairs are exactly those in which the two connectives’ five yes-or-no profiles, from the hero’s table, never agree on a yes. Most complete pairs are a connective that negates something together with one that combines asymmetrically, such as not with and, or a constant with an implication. The pattern is visible in the triangle as whole rows and columns: nand’s and nor’s rows are fully shaded, the projections’ are shaded only where the other connective is itself complete.

Three letters, and what is complete alone #

A single function of three letters can also express everything, and how many do is a question with a definite answer.

There are 56 of them. Each must turn all-false into true and all-true into false — otherwise it keeps a constant — which already confines it to the 64 functions whose number is odd and below 128, and the five properties remove eight more: the monotone ones (there are none with those two values), the self-dual ones and the affine ones among the 64. The closure confirms the count independently, closing each of the 256 functions under composition and finding exactly these 56 reaching everything. Among them are nand and nor applied to all three letters at once, the function that is true when $x$ is false or when $y$ and $z$ disagree, and dozens with no everyday name. Every one of them is a generalisation of nand: a single connective from which a whole logic can be built.

Twenty-two clones from six connectives #

The familiar connectives — and, or, not, xor and the two constants — can be combined in sixty-four sets, and each set generates a clone. Many sets generate the same one, and the computation sorts them.

The 64 sets give just 22 different clones, and the drawing arranges them by inclusion. At the bottom is the clone of the projections alone, 3 functions. Above it are the constants, the negations, the pure conjunctions and disjunctions, each a small clone. Higher up, and with or together make the 18 monotone functions with no constant; adding both constants gives all 20 monotone functions, the Dedekind number for three letters. Not with xor gives the 16 affine functions. And with xor gives 128, every function that keeps false. And with not reaches the top, 256.

The inclusions are the lattice’s order. A clone sits above another if it contains it, and the lines join each clone to the next ones up. Two clones always have a smallest clone containing both — the clone generated by their union — and a largest clone inside both — their intersection — which is what makes the picture a lattice, and the whole structure of all clones is Post’s lattice. Most of the 64 sets are redundant in an obvious way — adding a constant to a set that can already make it changes nothing — and the 22 classes are what is left once every such redundancy is collapsed. Six connectives, sixty-four combinations, twenty-two genuinely different vocabularies: that ratio is a first measure of how much of Post’s lattice the everyday connectives can reach.

Climbing from the bottom #

The drawing can be read from the bottom up as a story of what each connective adds. The projections alone express only themselves. Adding a constant adds one function; adding not doubles the projections into six; adding and gives the conjunctions. Each of these steps is small because each of these connectives is trapped in several classes at once.

The big steps come when a set escapes a class it was in. And with or, both monotone, can never leave the monotone class, and they stop at 18 functions; and with xor escapes monotonicity — xor is not monotone — and jumps to 128, every function that keeps false; one more escape, from keeping false, reaches everything. Each escape is a doubling or more of what can be said, and the five classes are the five walls the climb can hit.

That reading also explains why and-and-or formulas are special: monotone functions are exactly the ones they express, the monotone clone with constants is the whole of what monotone circuits compute, and lower bounds for monotone circuits — some of the few strong lower bounds known in complexity theory — are statements about how expensive it is to stay inside that wall. The affine wall has a meaning of its own: affine functions are the ones that linear algebra over two elements handles completely, and a problem whose constraints are all affine can be solved by Gaussian elimination however many letters it has.

How the walls grow with more letters #

The five maximal clones look comparable on three letters, and they are not. On $n$ letters there are $2^{2^n}$ truth functions in all. Exactly half of them keep false, and half keep true, whatever $n$ is — those two walls always enclose half of everything. The self-dual functions are determined by their values on half the rows, so there are $2^{2^{n-1}}$ of them, the square root of the total. The affine functions are sums modulo two of some of the letters, with or without a constant, so there are only $2^{n+1}$ of them — 16 on three letters, 32 on four, 2,048 on ten, against a total with more than three hundred digits. And the monotone functions are counted by Dedekind’s numbers: 3, 6, 20, 168, 7,581 for one to five letters, growing doubly exponentially but a vanishing share of all functions.

So a random truth function of many letters is outside the monotone, self-dual and affine classes almost surely, and inside each of the other two with probability one half. It is complete on its own exactly when it turns all-false into true and all-true into false and avoids the three small classes: with probability tending to one quarter. On three letters the share is 56 of 256, a little under a quarter, and the limit is approached quickly. A connective picked at random is, one time in four, a nand in disguise.

Post’s lattice #

Post found every clone of Boolean functions, and there are countably infinitely many. Most are finitely generated, like the ones drawn here; the infinite ones come in a few families of nested chains, and those chains are the reason three letters cannot show the whole picture. A typical chain is the clone of functions $f$ with the property that any $k$ inputs on which $f$ is false share a common false letter, for $k = 2, 3, 4, \ldots$: each condition implies the previous, each clone is strictly smaller, and the difference between consecutive ones appears only among functions of at least $k$ letters. On three letters those clones beyond the first couple look identical.

So the three-letter footprint is a faithful picture of the finite part of the lattice and a blurred picture of the infinite chains. That is the general situation: functions of more letters can always tell apart more clones, and no fixed number of letters sees them all. Post’s description, worked out by hand over many years and published in full in 1941, remains one of the few complete classifications of an infinite algebraic structure of its kind. Its analogue for three-valued logic is known to have uncountably many clones, as Yuri Yanov and Albert Muchnik showed in 1959, and nobody expects a description of those.

Why the five are the only obstacles #

The completeness criterion is a statement about the top of the lattice: the clone of all functions has exactly five clones directly below it, the maximal clones, and a set of connectives is complete exactly when it is not contained in any of them.

Their three-letter footprints are 128 functions keeping false, 128 keeping true, 20 monotone, 16 self-dual and 16 affine. The lists of binary connectives inside each show the criterion at work: every connective except nand and nor sits in at least one class, and the constant connectives sit in three or four, which is why they express so little. Two of the classes are enormous and three are small, and the small ones are the interesting ones: monotone, self-dual and affine are each a strong structural restriction, while keeping false or keeping true only fixes one value.

Why these five? Each is defined by a relation that its functions respect: keeping false respects the one-point relation $\{0\}$, monotone functions respect the order $0 \le 1$, self-dual functions respect the relation $x \ne y$, affine functions respect the relation $x \oplus y \oplus z = w$. Every clone is exactly the set of functions respecting some family of relations — a theorem of the 1960s, by Bodnarchuk, Kaluzhnin, Kotov and Romov and independently by David Geiger — and the maximal clones are those defined by a single minimal relation. On two values there are only five such relations, and that is why there are only five obstacles to completeness.

Three letters and no more #

Only three letters. As counting truth tables up to renaming showed, the number of truth functions grows doubly exponentially with the number of letters, and three is the largest number at which every closure here is instant. Each clone is computed on functions of $x$, $y$ and $z$, which separates all 22 clones drawn but would not separate the infinite chains of Post’s lattice, whose members differ only on functions of more letters. Two sets of connectives with the same three-letter footprint could in principle express different functions of four letters; for the sets drawn here they do not, which is a fact about these connectives that the figures do not check.

Only the clones these generators reach. The 22 clones are those generated by subsets of six connectives. Post’s lattice has clones that none of those subsets generates — the clone generated by the majority function alone, for instance, which contains every function built from majorities and nothing else — and the drawing is a piece of the lattice, not all of it.

Expressible is not efficient. A clone records what can be expressed, not how many connectives it takes. How many gates a truth table needs is a separate question, and two complete sets can differ greatly in how compactly they express the same function.

Still open: how hard is the lattice to climb #

Post’s lattice is completely described, and its open questions are about computation. Given a finite set of connectives, deciding which clone it generates is easy in principle — check the defining relations — and fast in practice. The harder questions concern what each clone makes difficult. For which clones is satisfiability of formulas built from its functions easy, and for which is it hard? Harry Lewis answered that in 1979: satisfiability is hard exactly when the connectives can express $x \wedge \neg y$, and easy for every clone below that point. Analogous classifications for counting the satisfying assignments, for deciding equivalence of formulas, and for the many problems of constraint satisfaction lean on the same lattice — every clone is the shadow of a family of relations, and the complexity of a problem often depends only on which clone its relations define. Those classifications are the active frontier; the relation that defines a problem and the clone of functions that respect it turn out to be two descriptions of one thing.