One connective is enough

Give somebody ∧, ∨ and ¬ and they can write any formula at all. Take away the ¬ and they can write almost nothing.

The first bar is the surprise. ↑ alone — the single connective not both — writes all 256, and it does it without being given negation, or conjunction, or anything else. The third bar, the familiar ∧, ∨, ¬, also writes all 256 and needs three connectives to do it. The second bar is ∧ and ∨ together, which most people would guess is nearly enough, and it reaches 18.

What the bars are measuring #

The measurement has to be said precisely or the numbers mean nothing.

Fix three variables $p$, $q$, $r$. There are $2^3 = 8$ assignments and therefore $2^8 = 256$ functions of them. Start with the three projections — the functions “read $p$”, “read $q$”, “read $r$” — and then close under composition: any function already in the pool may be fed into any connective of the basis, and the result joins the pool. Repeat until nothing new appears.

What comes out is exactly the set of functions that basis can write as a formula, because a formula is a composition tree with variables at the leaves. So the bar is not an estimate. It is a count of expressible functions, obtained by expressing them.

Two details of the setup are doing work, and both were choices.

Starting from projections and nothing else. A basis is asked what it can build out of variables. Handing it the constants $⊤$ and $⊥$ for free would be handing it two of the sixteen connectives before the count starts, and it changes the answer: ∧ and ∨ with constants available reach 20 rather than 18, picking up the two constants themselves.

Three variables rather than two. A basis that can write every two-variable function might still fail at three. Nothing in the definition of a formula limits how many variables it mentions, so completeness has to mean every arity. Three is enough to make the counts here honest and small enough to compute exhaustively; the general statement is a theorem and this figure is an instance of it.

The sixteen, and what most of them are #

Six of the sixteen ignore at least one input: the two constants, the two projections $p$ and $q$, and the two negated projections. Those cannot help a basis, because a connective that ignores an input cannot combine anything.

Of the remaining ten, the ones with ordinary names — ∧, ∨, →, ←, ↔, ⊕ — are the ones that ordinary language has a word for, and there is no reason to expect that to be a mathematically natural class. It is not. ↑ and ↓, which English handles only as a phrase, are the two that turn out to matter, and they were not noticed for that reason until the twentieth century.

Why “and” and “or” together get stuck #

The second bar is a good place to start, because the reason it stops is visible without any theory.

Suppose every input is true. Then $p ∧ q$ is true, $p ∨ q$ is true, and so is any formula built out of them, all the way up. So no formula in ∧ and ∨ alone can be false when everything is true. That rules out negation immediately, and it rules out 128 of the 256 functions at a stroke.

There is a second, subtler restriction. Turning an input from false to true never turns ∧ or ∨ from true to false, and that property survives composition: if every part is monotone in that sense, the whole is. So every formula in ∧ and ∨ is monotone. Exclusive-or is not — turning $q$ on when $p$ is on turns the output off — so ⊕ is out of reach too, along with everything else non-monotone.

Between them these two facts cut 256 down to 18, and the figure’s count agrees.

That is the shape of every impossibility in this essay, and it is worth naming, because it recurs everywhere in the field: find a property that every basis element has and that composition preserves, then exhibit a target function that lacks it. The property is doing the work; the search is over properties rather than over formulas, of which there are infinitely many.

The five properties, which turn out to be all of them #

The question is now obvious. How many such properties are there? If there were a hundred, deciding completeness would be a hundred checks and nobody could be sure the list was finished.

There are five.

The five are:

Keeps 0. The connective returns false when every input is false. ∧, ∨ and ⊕ do; ↑ and → do not.

Keeps 1. It returns true when every input is true. The mirror image, and a different class: ⊕ keeps 0 and does not keep 1.

Monotone. Turning an input on never turns the output off. ∧ and ∨ are; ¬, ⊕, → and ↑ are not.

Self-dual. Flipping every input flips the output. None of the six above is, which is a little unfair to the class — the standard example is majority of three, which is self-dual and not much else.

Affine. The connective is an exclusive-or of some of its inputs and possibly a constant, so each input either always matters or never does, independent of the others. ⊕ and ¬ are; ∧ is not, because whether $q$ matters depends on $p$.

Each is closed under composition, which is what makes it usable: a formula built entirely from monotone connectives is monotone, from affine ones is affine, and so on for all five. So if every member of a basis lies in one of the five classes, everything the basis writes lies in that class too, and any function outside it is unreachable.

Post’s criterion is the converse, and it is the theorem: a set of connectives is functionally complete exactly when, for each of the five classes, some member of the set lies outside it. Not “at least these five must be escaped and possibly more” — five is the complete list, and escaping all five is sufficient as well as necessary.

The measurement behind the table #

A theorem quoted in a caption is a claim about a literature, not about a picture, so the figure above does not quote it.

Every cell is computed from the connective’s own four rows: monotone by comparing all sixteen pairs of inputs, self-dual by checking all four complementary pairs, affine by trying all eight ways of writing it as an exclusive-or of its inputs and a constant. Then the verdict in the last column is computed a second time, by the closure of the first figure, and the two are asserted to agree.

That is the only honest way to put Post’s criterion on a page here. The criterion says a five-column test predicts what a closure computation will find; the two are calculated independently and compared, on every row, every time the figure is drawn. If the criterion were wrong about any connective in the table, the figure would refuse to draw.

Why NAND, specifically #

Read the ↑ row: five dots and no ticks. It escapes every one of the five classes, and it is the only one in the table that does.

That is not luck, and there is a reason it is ↑ and ↓ rather than anything else. Negation escapes three of the five, so ¬ alone gets a long way and fails at monotone and affine — it is affine, and being affine is exactly why ¬ on its own cannot build ∧. Conjunction escapes two — it is not affine and not self-dual — and fails at the other three. Put them together and every column is covered, which is why ∧ with ¬ is complete and needs both.

↑ is “not both”, which is $¬(p ∧ q)$: a conjunction and a negation fused into one symbol. It inherits the escapes of both halves and so covers all five columns by itself.

Exactly two of the sixteen escape all five, and they are ↑ and ↓. Every other single connective lies in at least one class and is therefore stuck inside it forever. There is no near miss and no third case.

Five more bases, and the two that are near misses #

The criterion is only worth having if it predicts cases nobody would guess, so here are five that are not the textbook ones.

Implication alone reaches 38. It escapes four of the five classes and lies inside keeps 1 — a formula built from → is true when everything is true, so nothing false-at-the-top is writable, and $¬p$ in particular is not.

Implication with $⊥$ reaches all 256. Adding the constant false is enough, because $p → ⊥$ is $¬p$ and the missing column is filled. This is the pairing that constructive systems are usually presented in, and the figure is the reason they can afford to look so sparse.

Exclusive-or alone reaches 8, which is as small as a basis gets without being useless. It is affine and keeps 0, so everything it writes is an exclusive-or of some subset of the variables — and with three variables there are exactly $2^3 = 8$ such subsets. The count is not an accident of the search; it is the class being enumerated.

Exclusive-or with conjunction reaches 128 and no further. This is the near miss worth staring at. It escapes four of the five: not monotone, not self-dual, not affine, does not keep 1. It lies inside keeps 0, because both connectives return false on all-false inputs, and 128 is exactly half of 256 — the half that is false at the bottom row. Everything else in the language is available and one row of one column is not, and no amount of cleverness recovers it. Two connectives, four escapes, and the single missed column costs half the language.

That pair also has a name: over the two-element field it is multiplication and addition, so the functions it writes are exactly the polynomials with no constant term. The logical statement and the algebraic one are the same statement, and neither is a metaphor for the other.

Negation with either ∧ or ∨ reaches everything, and the pair is redundant in a specific way — given ¬, each of ∧ and ∨ defines the other, so the usual three-connective toolkit contains one connective more than it needs. It is kept because de Morgan’s laws are easier to read than to derive, not because anything is missing without it.

What “enough” does and does not mean #

Two things get read into functional completeness that are not in it.

It says nothing about length. Everything writable in ∧, ∨, ¬ is writable in ↑ alone, and the ↑ version is usually far longer. Rebuilding conjunction costs three uses of ↑ and rebuilding exclusive-or costs four, and those costs multiply through a formula. The theorem is about what is expressible, not about what is convenient, and every one of the 256 functions is expressible either way.

It says nothing about naturalness. A basis of one is minimal in a count of symbols and terrible for reading. The familiar three are longer to specify and shorter to write with, and the choice between them is a choice about who is doing the reading — which is a design question rather than a mathematical one, and the mathematics is silent about it.

The place where it does mean something is when a substrate is fixed rather than chosen. If the thing available happens to be one operation, everything else has to be built out of it or not exist. That is why the result gets quoted about circuits, and why the same argument shows up wherever a system has one primitive and a question about what it can reach — including, in a different field entirely, the eight-bit rules whose whole vocabulary is three cells and a lookup table.

The habit worth taking away #

This essay has an unusual shape for a mathematical argument, and the shape is the point rather than the result.

The question “which sets of connectives are enough” is a question about an infinite collection: every finite set of connectives, and for each, every formula it can write. Nothing about it is obviously finite.

Post’s answer converts it into five yes-or-no questions about each connective’s own four rows. The infinite search over formulas is gone, replaced by twenty bits of information about the basis, and the conversion is exact — no basis is misclassified, no case is left over.

That conversion is what a good invariant does, and it is the same move as the parity argument that settles the bridges or the count that settles which solids exist: a question about all the arrangements, answered by a property that each piece either has or lacks. The specific five are Post’s; the move is the field’s, and it is worth recognising the next time a question looks like it needs a search.

Who found it, and how late it was #

The history is short and the dates are the interesting part.

↑ is called the Sheffer stroke, after a 1913 paper of Henry Sheffer showing that one connective suffices — though Charles Sanders Peirce had the same result in an unpublished manuscript of 1880, which is a common enough shape in this field to be worth noting rather than remarking on. Russell and Whitehead thought it important enough to rewrite the foundations of Principia Mathematica around it in the second edition.

Post’s classification came in the 1920s and was published in full in 1941, and it is a strictly larger result: not here is a connective that suffices but here is exactly which sets suffice, and why the list of obstructions stops at five. The gap between the two is the gap between an example and a theory, and it took about twenty-five years.

What makes the dates worth stating is how elementary the material is. Everything in this essay is finite, checkable by hand in an afternoon, and involves no object more sophisticated than a table of four rows. It was nevertheless not settled until the twentieth century, because nobody had asked the question in a form that had an answer. The subject did not need a new technique; it needed somebody to notice that “which sets of connectives are enough” was a question at all.

There is a coda that is not usually mentioned with the criterion, and it makes the five look less arbitrary. The five classes are not a list somebody assembled — they are the maximal closed classes, the ones that are as large as a proper closed collection of connectives can be, and every closed class that is not everything sits inside one of them. There are infinitely many closed classes altogether, arranged in a lattice that Post worked out in the 1920s and published in 1941, and the five maximal ones are its top layer. Completeness is escaping the top layer, because escaping it means escaping everything below.