Functional completeness

Summary

A set of operations on a finite set $A$ is functionally complete if every finitary operation on $A$ can be built from it by composition. In other words, the clone it generates is the clone of all operations. For $A = \set{0, 1}$ this is the familiar notion for sets of logical connectives, such as $\set{\wedge, \neg}$. Criteria for functional completeness are given by Post's lattice in the two-valued case and by maximal clones in general.