What is a Functionally Complete Set?
Definition1
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.
Kim Young-Hoon and Heo Jae-Seong, Quantum Information Theory (2020), p88 ↩︎