Order, lattices, ordered algebraic structures Theorem

Post's functional completeness theorem

Builds on Functional completeness Boolean function Monotone function

Statement

Let $F$ be a set of Boolean functions, that is, of operations on $\set{0, 1}$ of arity at least $1$ . Then $F$ is functionally complete if and only if $F$ has the following five properties.

Some $f \in F$ does not preserve $0$ , that is, $f(0, \dots, 0) = 1$ .
Some $f \in F$ does not preserve $1$ , that is, $f(1, \dots, 1) = 0$ .
Some $f \in F$ is not monotone for the order $0 \le 1$ applied coordinatewise.
Some $f \in F$ is not self-dual, where $f$ is self-dual if $f(\neg x_1, \dots, \neg x_n) = \neg f(x_1, \dots, x_n)$ for all inputs.
Some $f \in F$ is not affine, where $f$ is affine if $f(x_1, \dots, x_n) = c_0 + c_1 x_1 + \cdots + c_n x_n$ modulo $2$ for some $c_i \in \set{0, 1}$ .

Remarks

Each of the five classes is a clone and does not contain all Boolean functions, so a complete $F$ cannot lie inside one of them. The converse is the real content: these five clones are the maximal clones of Post's lattice. One can also prove it directly by building $\neg$ and the constants from the functions that escape the first four classes, and then $\wedge$ from a non-affine function. Example: the NAND operation $x \uparrow y = \neg(x \wedge y)$ maps $(0, 0)$ to $1$ and $(1, 1)$ to $0$ . It is not monotone, since $0 \uparrow 0 = 1 > 0 = 1 \uparrow 1$ , it is not self-dual, since $0 \uparrow 1 = 1 = 1 \uparrow 0$ , and it is not affine. So $\set{\uparrow}$ is functionally complete.

Going deeper

For a student

The result comes from Emil Post's study of the lattice of clones on $\set{0, 1}$ . It is the two-element case of a general picture: a set of operations on a finite set is complete exactly when it is contained in no maximal clone. For larger finite sets the maximal clones are listed by Rosenberg's classification, and the analogue of the theorem has more cases. It explains at once why $\set{\wedge, \vee}$ and $\set{\wedge, \vee, \to}$ are not complete, while $\set{\to, 0}$ is, with $0$ read as a constant unary function.

Reading path

To understand this page from the ground up, read these 4 pages in order. The foundations come first.

Show the path as a graph

Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.

no evidence level

Boolean function concept
Functional completeness concept
Monotone function concept
Post's functional completeness theorem statement

Tag	`WGBR7JHBV4`
URI	`m2://WGBR7JHBV4`
Kind	statement, theorem
Writing	W0 stub
MSC	06E30, 08A40, 03B05
Status	This copy of the site has no build data. Run `m2 status WGBR7JHBV4`.
About	Functional completeness
Uses	Functional completeness, Boolean function, Monotone function