Why Are AND, OR, and NOT Gates Functionally Complete?

In classical computing, a set of logic gates is functionally complete if it can be used to express every possible Boolean function. The combination of AND, OR, and NOT gates forms a functionally complete set because any truth table, regardless of its number of inputs, can be systematically translated into a logical expression using only these three operations. This foundational property allows complex digital circuits, from simple adders to modern microprocessors, to be constructed from a minimal set of basic building blocks.

Understanding Functional Completeness

A Boolean function maps \(n\) binary inputs, each taking a value of \(0\) (false) or \(1\) (true), to a single binary output. For \(n\) inputs, there are \(2^n\) possible input combinations, and consequently \(2^{2^n}\) possible Boolean functions. A set of logic gates is said to be functionally complete (or universal) if every one of these \(2^{2^n}\) functions can be represented as a finite composition of gates from that set.

The three fundamental operations are defined as follows for inputs \(A\) and \(B\):

  • NOT (Negation): Represented as \(\neg A\) or \(\overline{A}\), it outputs \(1\) if \(A = 0\), and \(0\) if \(A = 1\).
  • AND (Conjunction): Represented as \(A \land B\) or \(A \cdot B\), it outputs \(1\) if and only if both \(A = 1\) and \(B = 1\).
  • OR (Disjunction): Represented as \(A \lor B\) or \(A + B\), it outputs \(1\) if at least one of \(A\) or \(B\) is \(1\).

Proof by Disjunctive Normal Form

To prove that \(\{\text{AND}, \text{OR}, \text{NOT}\}\) is functionally complete, we can show that any arbitrary truth table can be converted into an equivalent Boolean expression using Disjunctive Normal Form (DNF), also known as a sum of products.

Consider an arbitrary Boolean function \(f(x_1, x_2, \dots, x_n)\). To construct its DNF expression:

  1. Identify every row in the truth table where the output \(f\) is \(1\).
  2. For each such row, create a minterm—an AND expression of all \(n\) variables. If a variable \(x_i\) is \(1\) in that row, use \(x_i\) directly; if \(x_i\) is \(0\), use its negation \(\neg x_i\).
  3. Combine all the resulting minterms using OR operations.

Each minterm evaluates to \(1\) for its specific input combination and \(0\) for all other combinations. When these minterms are joined by OR gates, the overall expression evaluates to \(1\) if and only if the inputs match one of the rows where \(f = 1\). If a function outputs \(0\) for every possible input, it can still be represented using these gates as \(x_1 \land \neg x_1\).

Because every possible truth table can be represented in this way, and DNF uses only AND, OR, and NOT operations, the set \(\{\text{AND}, \text{OR}, \text{NOT}\}\) is guaranteed to be functionally complete.

Redundancy and Minimal Complete Sets

While \(\{\text{AND}, \text{OR}, \text{NOT}\}\) is functionally complete, it is not minimal. Using De Morgan's laws, either AND or OR can be eliminated without losing completeness:

\[A \lor B = \neg(\neg A \land \neg B)\]

\[A \land B = \neg(\neg A \lor \neg B)\]

This means that \(\{\text{AND}, \text{NOT}\}\) and \(\{\text{OR}, \text{NOT}\}\) are each functionally complete on their own. Furthermore, single gates like NAND (\(\neg(A \land B)\)) and NOR (\(\neg(A \lor B)\)) are individually functionally complete because they can be used to construct NOT, AND, and OR gates. Nevertheless, \(\{\text{AND}, \text{OR}, \text{NOT}\}\) remains the standard conceptual basis for Boolean algebra and digital logic design due to its intuitive mapping to human reasoning and truth tables.