Building a Full Adder from NAND Gates

Compose a one-bit full adder entirely from NAND gates, showing how a single universal gate builds arithmetic.

The full adder

A full adder takes three inputs - two bits A and B plus a carry-in Cin - and produces a sum bit S and a carry-out Cout. Chaining n of them makes an n-bit ripple-carry adder, the arithmetic core of a processor.

Logic

The truth of it: S = A XOR B XOR Cin, and Cout = majority(A,B,Cin) = AB + Cin(A XOR B). We need XOR, AND, and OR - all of which reduce to NAND, because NAND is functionally complete: every Boolean function can be built from NAND alone.

NAND building blocks

• NOT a = NAND(a,a).
• AND a,b = NOT(NAND(a,b)).
• OR a,b = NAND(NOT a, NOT b).
• XOR built from four NANDs sharing an intermediate term.

def nand(a,b): return 1-(a&b)
def xor(a,b):
    t=nand(a,b); return nand(nand(a,t),nand(b,t))
def full_adder(a,b,cin):
    ab=xor(a,b); s=xor(ab,cin)
    c1=nand(a,b); c2=nand(ab,cin)
    cout=nand(c1,c2)             # = AB + Cin(A xor B)
    return s,cout
for a in (0,1):
    for b in (0,1):
        for c in (0,1):
            print(a,b,c,'->',full_adder(a,b,c))

Why NAND

Chip fabrication favors a single, cheap, universal gate; NAND (and NOR) fit this. Because NAND is complete, an entire processor's logic can be laid out from copies of one cell, simplifying design and manufacturing. This worked adder shows the path from one primitive gate up to binary arithmetic - the same path silicon takes.