Matpic
mathematics, in pictures
Concept

Functional completeness

A set of logical connectives is functionally complete when every truth function can be built from them alone. Post's theorem says a set fails exactly when it lies inside one of five maximal families, such as the connectives that preserve truth.

Named by 2 essays across one field — each of them below, with the objects they name alongside it.

Post's five classes, and which connectives escape them. A table of connectives against the five closed classes, with the completeness verdict for each.

One connective is enough

Of the sixteen ways to combine two truth values, exactly two can build all the others by themselves. Which two is not obvious, and the reason turns out to be five properties that a connective either has or escapes.

logic · Truth functions What each connective of two letters can express on its own. Three-letter fragment sizes of the clones generated by single binary connectives: false 4, nor 256, not x but y 38, not x 6, x but not y 38, not y 6, xor 8, nand 256, and 7, iff 8, y 3, if x then y 38, x 3, if y then x 38, or 7, true 4.

What an incomplete set of connectives can say

Nand alone can express every truth function, and Post's five properties say exactly which sets of connectives can. That answers the question at the top. Below it lies a whole landscape: and alone expresses 7 of the 256 functions of three letters, xor 8, implication 38, and the sixty-four sets that can be drawn from and, or, not, xor and the two constants fall into just 22 different classes of expressible functions. The classes fit together into Emil Post's lattice of 1941 — countably infinite, completely described, and on three letters small enough to draw.

logic · Truth functions

Named alongside it

The objects these essays reach for when they reach for this one.

Truth functionAffine functionCloneClosureConnectiveDualityLatticeMonotone functionPost classesSelf-dual functionSheffer stroke

All concepts