Expressively complete boolean functions

[Joseph S. Myers]

On Sat, 16 Dec 2006, Gabriel Cunningham wrote:

> A set S of boolean functions is said to be expressively complete if every
> boolean function (in any number of variables) can be written in terms of the
> members of S. For instance, the set {AND, NOT} is expressively complete, as
> is the single-member set {NAND}. We'll call a boolean function expressively
> complete if the set containing only that function is expressively complete.

The characterisation of complete sets is Post's functional completeness 
theorem: a complete set is one that, for each of the following five 
classes of functions (each of which is clearly closed under composition), 
contains a function not in that set (these may all be the same function).

(1) Functions with f(1, 1, ..., 1) = 1.

(2) Functions with f(0, 0, ..., 0) = 0.

(3) Functions which depend only on the parity of the number of 1s in some 
subset of their inputs (such as (a XOR b XOR c) or NOT(a XOR c)).

(4) Monotone functions (functions such that if f(a, b, c) = 1, a <= A, b 
<= B and c <= C, then f(A, B, C) = 1; this is equivalent to functions that 
can be formed from 0, 1, AND and OR).

(5) Functions such that f(a, b, c) = NOT f(NOT a, NOT b, NOT c) for all 
inputs.

-- 
Joseph S. Myers
jsm at polyomino.org.uk