Implement All Logic Gates Using Only NAND

NAND as a Universal Gate

The NAND gate (NOT-AND) outputs 0 only when both inputs are 1. Every other basic gate can be built from NAND alone, which is why foundry standard-cell libraries often ship millions of identical NAND2 cells.

Truth table for NAND(A, B):

Building Other Gates

• NOT: tie both inputs together: NAND(A, A)
• AND: invert a NAND: NAND(NAND(A,B), NAND(A,B))
• OR: apply De Morgan: NAND(NOT A, NOT B)
• XOR: combine four NAND stages (classic textbook construction)

For example, NOT(1) becomes NAND(1,1) = 0, and AND(1,0) chains two NAND calls to yield 0.

cCopy
Loading…

For this exercise, you will implement each derived gate as a pure function of nand(a, b) only. This task asks you to prove universality in code, the same reduction step nand2tetris uses before students wire their first ALU.

Working Through the Exercise

Keep the relevant datasheet, ISA manual, or architecture textbook chapter open while you implement. When your output disagrees with the reference trace on the same program, the bug is usually a mis-decoded opcode, a stale register read, or a flag bit left unchanged after arithmetic.

• Trace first: walk one failing input by hand before changing random lines
• Read the manual: skim the official doc for the mechanism named in this task
• Compare baselines: save measurements from the prior step so speedups are honest

For this exercise, you will use those habits while implementing the requirement in the starter code. Microarchitectural product names change across CPU generations, but the control ideas (fetch, bypass, cache lines, vector lanes) stay stable enough to debug from first principles.