Lecture
Functional completeness of a set of logical operations or Boolean functions — is the ability to express all possible truth-table values by means of formulas built from elements of this set. Mathematical logic usually uses the following set of operations: conjunction (
), disjunction (
), negation (
), implication (
) and equivalence (
). This set of operations is functionally complete. But it is not a minimal functionally complete system, because:
Thus 
is also a functionally complete system. But can also be expressed (in accordance with De Morgan's law) as:
can also be defined through in a similar way.
Also 
can be expressed through 
as follows:
So 
and one of 
is a minimal functionally complete system.
Post's criterion describes the necessary and sufficient conditions for the functional completeness of sets of Boolean functions. It was formulated by the American mathematician Emil Post in 1941.
Criterion:
A set of Boolean functions is functionally complete if and only if it is not entirely contained in any of the precomplete classes.
Completeness criterion (Post's theorem): A system S of Boolean functions is complete if and only if it includes at least one function: not preserving the constant 0, not preserving the constant 1, non-self-dual, non-linear and non-monotone.
The table lists the properties possessed by the elementary Boolean functions (the symbol * - marks a property that the given function possesses).
| Name | Notation |
Non-preservation of constant 0 |
Non-preservation of constant 1 |
Non- self-duality |
Non- linearity |
Non- monotonicity |
| Const. 0 | 0 | * | * | |||
| Const. 1 | 1 | * | * | |||
| Neg. | ¬ | * | * | * | ||
| Conj. | & | * | * | |||
| Disj. | v | * | * | |||
| Impl. | → | * | * | * | * | |
| Equiv. | ∼ | * | * | * | ||
| Sum mod 2 | ⊕ | * | * | * | ||
| Sheffer stroke | | | * | * | * | * | * |
| Peirce arrow | ↓ | * | * | * | * | * |
Using Post's theorem and this table, one can build bases from elementary functions according to the following rule. Choose any elementary Boolean function and, if necessary, supplement it with other functions so that all of them together satisfy the theorem on functional completeness. Through the functions of this basis one can express all other Boolean functions.
Sets of one element
(Sheffer stroke), 
(Peirce arrow)
Sets of two elements
Sets of three elements
, 
(see Zhegalkin algebra), 
(inverse to the previous one)
Definition. A set of functions N is called a functionally complete system (FCS) if any Boolean function is representable as a superposition of functions from N.
We agree to omit the arguments when listing the functions of the set N and to regard the term ''system'' in this context as a synonym for a set.
Example 1. The set N1={
, 
, –} is a functionally complete system, since any Boolean function except the constant 0 can be represented by a perfect DNF, that is, a superposition of functions from N1, and the constant 0 – by the formula xx . •
Example 2. The set N2={, 
, 1} is an FCS, since any Boolean function can be represented by a Zhegalkin polynomial, that is, a superposition of functions from N2, and the polynomial 0 – by the formula 1 1. •
The following theorem makes it possible to reduce the question of the functional completeness of some systems to the question of the completeness of other systems.
Theorem on two functionally complete systems. If two sets N1 and N2 of Boolean functions are given and it is known that N1 – is a functionally complete system, and every function from N1 is representable as a superposition of functions from N2, then N2 is also a functionally complete system.
Proof. Consider an arbitrary Boolean function f(x1, …, xn). It can be represented as a superposition of functions from the set N1={f0,f1 …, fm}, since N1 – is an FCS:
By the condition of the theorem, each of the functions f0, f1 …, fm can be represented as a superposition of functions from N2, hence the function f(x1, …, xn) is representable as a superposition of functions from N2, and therefore N2 – is an FCS. •
Example 1. N1={ , –,}, N2={, –}. As shown earlier, N1 – is an FCS. Conjunction and inversion are contained in N2, and disjunction is representable as a superposition of functions from N2: x y = 
, hence N2 – is an FCS. •
Example 2. N1={, –}, N2={↓ }. As shown in the previous example, N1 – is an FCS. Inversion and conjunction can be represented as a superposition of the Peirce arrow: x = x↓ x, xy =
= (x↓ x)↓ (y↓ y), therefore N2 – is an FCS. •
Comments