PublicationsManuscripts

A set of Boolean connectives is complete (can generate all Boolean functions) unless one of the following holds:

1. All connectives are 0-preserving (if all inputs are 0 then the output is 0).
2. All connectives are 1-preserving.
3. All connectives are monotone.
4. All connectives are self-dual ($f(\bar{x}) = \overline{f(x)}$).
5. All connectives are affine.

This follows from Post’s classification of all Boolean clones. In particular, these are the five maximal non-trivial clones.

We present a self-contained proof of this classical result.