NAND and NOR: the universal gates

A NAND gate is universal: NOT, AND, OR, and therefore any circuit at all, can be built from NAND gates only. The same is true of NOR. In CMOS chips a NAND gate needs just four transistors, fewer than AND (which is a NAND followed by a NOT), so real circuits are often mostly NAND and NOR.

Everything from NAND

Why does the OR work? (A NAND A) is A', so the result is (A' · B')' which by De Morgan is A + B.

def nand(a, b):
    return 1 - (a & b)

def not_(a):
    return nand(a, a)

def and_(a, b):
    return not_(nand(a, b))

def or_(a, b):
    return nand(not_(a), not_(b))

def xor_(a, b):
    m = nand(a, b)
    return nand(nand(a, m), nand(b, m))

for a in [0, 1]:
    for b in [0, 1]:
        ok = (and_(a, b), or_(a, b), xor_(a, b)) == (a & b, a | b, a ^ b)
        print(a, b, "AND", and_(a, b), "OR", or_(a, b), "XOR", xor_(a, b), "correct:", ok)

Converting a circuit

A sum of products (an OR of ANDs) becomes NAND–NAND directly: replace every AND gate and the final OR gate with NAND gates. By De Morgan, ((AB)'(CD)')' = AB + CD. In the same way, a product of sums becomes NOR–NOR.

def nand(a, b):
    return 1 - (a & b)

# F = AB + CD, built from three NAND gates
wrong = 0
for row in range(16):
    a, b, c, d = (row >> 3) & 1, (row >> 2) & 1, (row >> 1) & 1, row & 1
    if nand(nand(a, b), nand(c, d)) != (a & b) | (c & d):
        wrong += 1
print("rows where NAND-NAND differs from AB + CD:", wrong)

Early chips such as the famous 7400 contained four NAND gates each, and whole computers, including the Apollo Guidance Computer that flew to the Moon, were built from NOR gates alone.

Mark lesson complete