Functional Completeness - Characterization of Functional Completeness

Characterization of Functional Completeness

Emil Post proved that a set of logical connectives is functionally complete if and only if it is not a subset of any of the following sets of connectives:

• The monotonic connectives; changing the truth value of any connected variables from F to T without changing any from T to F never makes these connectives change their return value from T to F, e.g., .

• The affine connectives, such that each connected variable either always or never affects the truth value these connectives return, e.g., .

• The self-dual connectives, which are equal to their own de Morgan dual; if the truth values of all variables are reversed, so is the truth value these connectives return, e.g., MAJ(p,q,r).

• The truth-preserving connectives; they return the truth value T under any interpretation which assigns T to all variables, e.g., .

• The falsity-preserving connectives; they return the truth value F under any interpretation which assigns F to all variables, e.g., .

In fact, Post gave a complete description of the lattice of all clones (sets of operations closed under composition and containing all projections) on the two-element set {T, F}, nowadays called Post's lattice, which implies the above result as a simple corollary: the five mentioned sets of connectives are exactly the maximal clones.