Constructing Logic Gates from Truth Tables

When I played Turing Complete in October 2021, I wondered whether there was a systematic way to construct a circuit from a truth table. Later, while reading Mendelson's Introduction to Mathematical Logic, functional completeness supplied the answer. Every Boolean function can be represented using AND, OR, and NOT; NOR alone is also sufficient.

This is an existence result. The circuit produced by the general construction can be much larger than necessary, so simplification is a separate problem.

From a truth table to a formula

Let $n\ge1$ and $f:\{0,1\}^n\to\{0,1\}$. The symbols $x_1,\ldots,x_n$ are propositional variables; an assignment gives each symbol a truth value. Formulas are built from these symbols by negation and the binary connectives $\wedge$ and $\vee$, with parentheses specifying their structure.

For a row $a=(a_1,\ldots,a_n)$, define the literal

and its minterm $C_a=\bigwedge_{j=1}^{n}\ell_{a,j}$. This formula is true exactly on the assignment $a$.

Now take the disjunction of all minterms whose rows have output one:

On any input, precisely its own minterm is true. Therefore $D$ has the same truth value as $f$ on every input. This is disjunctive normal form (DNF).

There can be anywhere from $0$ to $2^n$ true rows. For the constant-false function, use $x_1\wedge\neg x_1$; for the constant-true function, use $x_1\vee\neg x_1$. The assumption $n\ge1$ ensures $x_1$ is available. Zero-input functions would require a separate convention for constants.

Example: simplify before building

Consider a function true on $(0,0,0)$ and $(0,0,1)$ and false on the other six assignments. The construction gives

Factoring out the shared conjunction,

The output does not depend on $x_3$. A single two-input NOR gate implements the whole function.

A Python construction

The function below accepts a complete truth table. Each row contains $n$ input bits followed by one output bit. It rejects missing, duplicate, or malformed rows rather than silently treating an incomplete table as a complete function.

from itertools import product


def convert_to_dnf(truth_table):
    rows = [tuple(row) for row in truth_table]
    if not rows or len(rows[0]) < 2:
        raise ValueError("Provide a complete table with at least one input.")
    n = len(rows[0]) - 1
    if any(len(row) != n + 1 for row in rows):
        raise ValueError("Every row must have the same length.")
    if any(type(bit) not in (int, bool) or bit not in (0, 1)
           for row in rows for bit in row):
        raise ValueError("Inputs and outputs must be bits.")
    inputs = [row[:-1] for row in rows]
    if len(rows) != 2**n or len(set(inputs)) != 2**n:
        raise ValueError("Each input assignment must occur exactly once.")

    terms = []
    for row in rows:
        if row[-1] == 1:
            literals = [f"x_{j + 1}" if bit else f"¬x_{j + 1}"
                        for j, bit in enumerate(row[:-1])]
            terms.append("(" + " ∧ ".join(literals) + ")")
    if not terms:
        return "(x_1 ∧ ¬x_1)"
    if len(terms) == 2**n:
        return "(x_1 ∨ ¬x_1)"
    return " ∨ ".join(terms)


truth_table = [
    (*bits, int(bits[0] == 0 and bits[1] == 0))
    for bits in product((0, 1), repeat=3)
]
print(convert_to_dnf(truth_table))

The output is a formula, not a minimized circuit or a physical wiring plan. The construction can contain exponentially many terms because a truth table already has $2^n$ rows.

Why NOR alone is enough

Define $A\downarrow B=\neg(A\vee B)$. Then

Each identity can be checked on the four possible pairs of truth values. Replacing every NOT, OR, and AND in a DNF formula with its NOR construction yields a NOR-only formula for the same function. That proves functional completeness.

The result concerns finite combinational Boolean circuits. Memory, timing, and sequential behavior require additional structure; functional completeness alone does not build an entire computer.

The game that prompted the question

I recommended the game on Zhihu on October 23, 2021. Some of its construction puzzles were difficult for me then, and I put the algorithm question aside while preparing for exams. Learning the logic later gave me a reason to return to it.