NAND Gate Explained: The Universal Gate That Can Build Every Logic Circuit

In the previous post in this series, we built the buffer — the gate that restores a signal, regenerates its strength, and copies truth without changing it. Step back and look at what this series has assembled so far: AND, OR, NOT, and buffer. Four gates, each wired from humble relays, each earning its place.

Here is a question worth sitting with for a moment: what if you did not need four gate types? What if one single configuration of one relay could, in sufficient combinations, produce every logic circuit that exists — AND, OR, NOT, adders, flip-flops, the whole stack of everything a computer ever does?

That gate exists. It is called the NAND gate, and it is the subject of this post. Meeting it properly is one of the most satisfying moments in all of digital logic — not because it is complicated, but because the reason for its power turns out to be so simple and so deep that once you see it you cannot unsee it.

NOT-AND: the output rule in one name

The name “NAND” is a contraction: Not AND. The entire output rule lives inside those four letters.

You know how AND works from Post 2 of this series: two relays in series; both coils must energize for the output to be 1. One lamp lit, three lamps dark.

NAND flips every row. The output is 0 only when both inputs are 1. Every other case the output stays at 1. Three lamps lit, one dark.

In plain English: NAND says “yes to everything, except when both inputs agree.” Only unanimous agreement shuts it off. That single inversion — one extra NOT bolted to the AND’s exit — is what makes all the difference.

Building NAND from relays: the NC contacts that write De Morgan’s law in wire

The obvious construction is compound: build an AND gate from two relays in series, then invert the output through a third relay’s NC contact. Three relays, correct, workable.

But there is a two-relay construction that is more elegant — and that reveals something deeper.

Recall from the NOT gate post that a relay’s normally-closed (NC) contact is already an inverter: the contact bridges the output circuit at rest, and the coil’s energization pulls it open. Take two relays driven by inputs A and B, and wire their NC contacts in parallel — two separate branches from supply to the output lamp, either of which can carry current on its own.

Work through every combination:

• A off, B off. Both coils are dormant. Both NC contacts sit closed. Current flows through both branches. Output is 1.
• A on, B off. Relay A’s coil energizes, pulling its NC contact open. But relay B’s coil is still off, so B’s NC contact remains closed. Current reaches the lamp through B’s branch. Output is 1.
• A off, B on. The mirror image. A’s NC contact stays closed, carrying current. Output is 1.
• A on, B on. Both coils energize. Both NC contacts are pulled open simultaneously. Neither branch carries current. The lamp goes dark. Output is 0.

This is NAND — not as a compound of multiple gate types, but as a single direct wiring of two relays. And now look at the structural logic hiding in those four rows. Two NC contacts in parallel are the circuit implementation of $\neg A \text{ OR } \neg B$: not-A, or not-B. That expression and $\neg(A \cdot B)$ — not-(A and B) — are exactly equal. We built a mathematical theorem in copper and iron.

That theorem has a name and a history.

The mathematician who wrote the law: Augustus De Morgan

In the late 1840s, a logician named Augustus De Morgan was formalizing the algebra of propositions in close correspondence with George Boole, whose name would eventually label the whole enterprise. De Morgan published Formal Logic in 1847 — the same year Boole published his own foundational work — and the two men exchanged letters debating the precise shape of the logical calculus they were building together. De Morgan’s most enduring contribution was a pair of transformation laws so compact they fit on a single line:

$\neg(A \cdot B) = \neg A + \neg B$ $\neg(A + B) = \neg A \cdot \neg B$

In words: NOT of (A AND B) equals (NOT A) OR (NOT B). And NOT of (A OR B) equals (NOT A) AND (NOT B). Negate an entire expression, and you simultaneously flip every AND to OR and every OR to AND, while inverting each individual input.

De Morgan was writing about syllogisms — he was not thinking about copper wire. But ninety years later, when Claude Shannon proved that relay networks and Boolean algebra were the same thing, De Morgan’s laws became load-bearing structure. The two laws guarantee that AND and OR are perfect duals of each other: every logic function expressible with both binary operations can be re-expressed using just one, combined with NOT. That algebraic symmetry is the precise reason a single gate type is enough.

The truth table: NAND in physical clothing

Three rows produce a lit lamp. Only the bottom row — both inputs on — goes dark. Compare this with AND’s truth table and the relationship is exact: every 0 in AND’s output becomes a 1 here, and AND’s single 1 becomes the single 0. NAND is AND’s precise logical negative, row for row.

Try it yourself

Below is a live relay NAND gate, running a genuine electromechanical simulation in your browser — two coils, two NC contacts in parallel, one output lamp. Before you interact with anything, make a prediction for all four rows. Which combinations will you find with the lamp lit? Which one will leave it dark?

Three things to pay close attention to:

1. Contrast with AND. The AND gate from Post 2 lit the lamp on the one row where both inputs are 1 — every other row left it dark. This gate does the opposite. Hold both truth tables in your mind simultaneously, row by row, and notice that one is the exact column-flip of the other. Same relays, different contact pins, completely opposite behavior.

2. Turn on one input, then the other. While only A is on, the lamp is still lit. Now bring B on — and listen for the click as the lamp goes dark. That click is NAND doing the one thing it ever refuses: both at once. No individual input can extinguish the output; only unanimous agreement can.

3. Release one input and watch the lamp return. Drop either A or B back to 0 and the lamp immediately lights again. NAND’s natural state is 1. It defaults to yes and can be driven to no only by both inputs cooperating simultaneously. That disposition is fundamental to why NAND gates, wired in feedback loops, naturally form memory cells — but that is a story for a later post in this series.

The profound part: NAND is universal

Now for the idea that makes this gate famous in every computer science curriculum and every chip design textbook. It is called functional completeness, and its consequences are remarkable.

The claim: using only NAND gates — nothing else — you can build any Boolean function. NOT, AND, OR, XOR, multiplexers, adders, counters, flip-flops. Every circuit that exists.

The proof is constructive. You show how to build each primitive operation from NAND, and then note that all other functions are built from those primitives.

NOT from NAND. Tie both inputs of a NAND gate to the same signal A. The gate computes $\neg(A \cdot A) = \neg A$. Both inputs receiving the same value, the AND evaluates to A, and the NAND’s built-in inversion gives NOT A. One gate, inputs joined — a perfect inverter.

AND from NAND. Take a NAND gate computing $\neg(A \cdot B)$, then feed its output into a second NAND used as a NOT (inputs tied). The second gate computes $\neg(\neg(A \cdot B)) = A \cdot B$. Two NAND gates give AND.

OR from NAND. This is where De Morgan steps in directly. His first law states:

$\neg A + \neg B = \neg(A \cdot B)$

So to compute $A + B$, first compute $\neg A$ and $\neg B$ (one NAND-as-NOT for each), then NAND the two results: $\neg(\neg A \cdot \neg B) = A + B$. Three NAND gates — each input inverted, then the inverted inputs NANDed — produce OR.

Write it out as a table of what you now have:

And since every Boolean function is a combination of NOT, AND, and OR, every Boolean function is a combination of NANDs. The proof is complete.

This is not a theoretical curiosity. It is why semiconductor factories optimize one gate type. A chip foundry that perfects a single NAND cell can synthesize any logic circuit by tiling that one cell in the right patterns. The 7400-series NAND chips from Texas Instruments and Fairchild in the 1960s became the standard vocabulary of a generation of hardware engineers. You could design a full computer from a single part number’s datasheet; a factory could stock one bin and ship everything.

De Morgan’s law, written in the 1840s to describe the structure of syllogisms, had become — a century later — the organizing principle of industrial electronics.

What you just learned — and what comes next

From two relays, wired NC-contacts-in-parallel:

• NAND is NOT-AND. The output is 1 for every input combination except the one where all inputs are simultaneously 1.
• The physical construction reveals De Morgan’s law directly. Two NC contacts in parallel implement $\neg A \text{ OR } \neg B$, which equals $\neg(A \cdot B)$ — the De Morgan dual materializes in the wiring itself.
• NAND is functionally complete — a universal gate. NOT from one NAND with inputs tied; AND from NAND then NAND-as-NOT; OR from two NAND-inverters feeding a final NAND.
• The historical thread: De Morgan and Boole in the 1840s, Shannon in 1937, the 7400 series in the 1960s — the same algebraic symmetry running from a Victorian correspondence to a printed circuit board.

There is a twin to the NAND gate: equally universal, equally elegant, and chosen — above NAND and every other option — as the sole building block of the Apollo Guidance Computer, the machine that calculated humanity’s first trajectories to the Moon. That gate is NOR, and Post 9 is where we meet it. The reason NASA’s engineers chose NOR over NAND is a design story that touches radiation hardness, manufacturing yield, and the specific constraints of building logic for a spacecraft in 1965. It is worth every detail.

Want to jump ahead and explore? Every gate in this series lives in the DigiSim Relay Lab — wire both inputs of the NAND circuit to the same node and listen to a universal gate become an inverter. One connection, one gate type, the whole of logic within reach.