Functional completeness

Concept in mathematical logic

In logic, a functionally complete set of logical connectives or Boolean operators is one that can be used to express all possible truth tables by combining members of the set into a Boolean expression. A well known complete set of connectives is Each of the singleton sets and is functionally complete. However, the set is incomplete, due to its inability to express NOT. A gate (or set of gates) that is functionally complete can also be called a universal gate (or a universal set of gates). In a context of propositional logic, functionally complete sets of connectives are also called (expressively) adequate. From the point of view of digital electronics, functional completeness means that every possible logic gate can be realized as a network of gates of the types prescribed by the set. In particular, all logic gates can be assembled from either only binary NAND gates, or only binary NOR gates.

Modern texts on logic typically take as primitive some subset of the connectives: conjunction ; disjunction ; negation ; material conditional ; and possibly the biconditional Further connectives can be defined, if so desired, by defining them in terms of these primitives. For example, NOR (the negation of the disjunction, sometimes denoted ) can be expressed as conjunction of two negations:

Similarly, the negation of the conjunction, NAND (sometimes denoted as ), can be defined in terms of disjunction and negation. Every binary connective can be defined in terms of , which means that set is functionally complete. However, it contains redundancy: this set is not a minimal functionally complete set, because the conditional and biconditional can be defined in terms of the other connectives as

It follows that the smaller set is also functionally complete. (Its functional completeness is also proved by the Disjunctive Normal Form Theorem.) But this is still not minimal, as can be defined as

Alternatively, may be defined in terms of in a similar manner, or may be defined in terms of :

No further simplifications are possible. Hence, every two element set of connectives containing and one of is a minimal functionally complete subset of .

Given the Boolean domain , a set F of Boolean functions fi : Bni → B is functionally complete if the clone on B generated by the basic functions fi contains all functions f : 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 fi. 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 f : 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 1=S(x, y, z) = z if 1=x = y and 1=S(x, y, z) = x otherwise shows that this condition is strictly weaker than functional completeness.

Apart from logical connectives (Boolean operators), functional completeness can be introduced in other domains. For example, a set of reversible gates is called functionally complete, if it can express every reversible operator. The 3 input Fredkin gate is functionally complete reversible gate by itself – a sole sufficient operator. There are many other three input universal logic gates, such as the Toffoli gate. In quantum computing, the Hadamard gate and the T gate are universal, albeit with a slightly more restrictive definition than that of functional completeness.

There is an isomorphism between the algebra of sets and the Boolean algebra, that is, they have the same structure. Then, if we map boolean operators into set operators, the "translated" above text are valid also for sets: there are many "minimal complete set of set theory operators" that can generate any other set relations. The more popular "Minimal complete operator sets" are and If the universal set is forbidden, set operators are restricted to being falsity (Ø) preserving, and cannot be equivalent to functionally complete Boolean algebra.