Functional Completeness - Formal Definition

Formal Definition

Given the Boolean domain B = {0,1}, a set F of Boolean functions ƒ_i: Bn_i → B is functionally complete if the clone on B generated by the basic functions ƒ_i contains all functions ƒ: Bn → B, for all strictly positive integers n ≥ 1. In other words, the set is functionally complete if every Boolean function that takes at least one variable can be expressed in terms of the functions ƒ_i. Since every Boolean function of at least one variable can be expressed in terms of binary Boolean functions, F is functionally complete if and only if every binary Boolean function can be expressed in terms of the functions in F.

A more natural condition would be that the clone generated by F consist of all functions ƒ: Bn → B, for all integers n ≥ 0. However, the examples given above are not functionally complete in this stronger sense because it is not possible to write a nullary function, i.e. a constant expression, in terms of F if F itself does not contain at least one nullary function. With this stronger definition, the smallest functionally complete sets would have 2 elements.

Another natural condition would be that the clone generated by F together with the two nullary constant functions be functionally complete or, equivalently, functionally complete in the strong sense of the previous paragraph. The example of the Boolean function given by S(x, y, z) = z if x = y and S(x, y, z) = x otherwise shows that this condition is strictly weaker than functional completeness.