What is a Functionally Complete Set?

Definition¹

Let’s assume that a set of Boolean functions $\left\{ f_{k} \right\} = \left\{ f_{k} : \left\{ 0, 1 \right\}^{n_{k}} \to \left\{ 0, 1 \right\} \right\}_{k\in \Gamma}$ is given. $\Gamma$ is a finite set. If any Boolean function

$$\left\{ 0, 1 \right\}^{n} \to \left\{ 0, 1 \right\}\quad (n \in \mathbb{N})$$

can be expressed by the compositions of $\left\{ f_{k} \right\}$, then the set $\left\{ f_{k} \right\}$ is called functionally complete.

Theorem

The set of $\text{NOT}$ gates and $\text{AND}$ gates $\left\{ \lnot, \land \right\}$ is functionally complete.

Explanation

In other words, all Boolean functions can be made by repetitions of $\text{NOT}$ and $\text{AND}$. There are infinitely many sets that are functionally complete, which are not unique. For instance, because $a \land b = \lnot(\lnot a \lor \lnot b)$, $\left\{ \lnot, \lor \right\}$ is also a functionally complete set. From this theorem, it can be proven that a set is functionally complete if it can be shown to produce both $\text{AND}$ gates and $\text{NOT}$ gates.

Examples of functionally complete sets:

• $\text{NAND}$ gates
• $\text{NOR}$ gates
• $T$(Toffoli gates)
• $F$(Fredkin gates)
• $\left\{ \lnot, \lor \right\}$
• $\left\{ \oplus, \land \right\}$

Of course, there are cases where a duplication function is needed. If these results are described in the language of computer circuits, it can be stated as follows. All logical operations can be:

• implemented in circuits using only $\text{NOT}$ gates and $\text{AND}$ gates.
• implemented in circuits using only $\text{NAND}$ gates and duplication functions.
• implemented in circuits using only $\text{NOR}$ gates and duplication functions.
• implemented in circuits using only Toffoli gates.
• implemented in circuits using only Fredkin gates.

Universal Gates

Especially, when a set composed solely of itself $\left\{ f \right\}$ is functionally complete, such a $f$ is called a universal gate. A universal gate can express all Boolean functions by itself. $\text{NAND}$, $\text{NOR}$, $T$, $F$ are universal gates.