Logic Gates and Universal Gates: Building Any Circuit from NAND or NOR
Logic gates are the smallest building blocks of digital hardware. Each gate takes one or more binary inputs and produces an output defined by a truth table. NAND and NOR are called universal gates because any Boolean function can be built from only one of them. This matters in practice: CMOS NAND gates are compact and fast, standard-cell libraries are rich in NAND and NOR cells, and in a lab you can often finish a whole design with a few 7400 chips. This tutorial covers the seven basic gates, the common 74xx ICs, logic voltage levels, and step-by-step conversion of circuits into NAND-only and NOR-only form.
The Seven Basic Gates
Two-input truth table for all gates A B | AND OR NAND NOR XOR XNOR ----+------------------------------- 0 0 | 0 0 1 1 0 1 0 1 | 0 1 1 0 1 0 1 0 | 0 1 1 0 1 0 1 1 | 1 1 0 0 0 1 NOT: Y = A' (0 -> 1, 1 -> 0)
| Gate | Expression | Output is 1 when | Common TTL/CMOS IC |
|---|---|---|---|
| NOT | Y = A' | Input is 0 | 7404 (hex inverter) |
| AND | Y = AB | All inputs are 1 | 7408 (quad 2-input) |
| OR | Y = A + B | Any input is 1 | 7432 (quad 2-input) |
| NAND | Y = (AB)' | Any input is 0 | 7400 (quad 2-input) |
| NOR | Y = (A + B)' | All inputs are 0 | 7402 (quad 2-input) |
| XOR | Y = A'B + AB' | Inputs differ (odd number of 1s) | 7486 (quad 2-input) |
| XNOR | Y = AB + A'B' | Inputs are equal | 74266 (open-collector) or XOR plus NOT |
The XOR gate deserves special attention. For more than two inputs it outputs 1 when an odd number of inputs are 1, which makes it the basis of parity generators and checkers. It is also a controlled inverter: A XOR 0 = A, and A XOR 1 = A'. Adders, comparators, CRC circuits and Gray-code converters are all built around XOR.
Logic Levels and Noise Margin
A real gate does not see a perfect 0 or 1; it sees a voltage. The datasheet defines the input voltage that is guaranteed to be read as low (VIL max) or high (VIH min), and the output voltage the gate guarantees when driving low (VOL max) or high (VOH min). For standard 5 V TTL these are VIL = 0.8 V, VIH = 2.0 V, VOL = 0.4 V and VOH = 2.4 V.
Noise margin (TTL, 5 V) NM(high) = VOH(min) - VIH(min) = 2.4 - 2.0 = 0.4 V NM(low) = VIL(max) - VOL(max) = 0.8 - 0.4 = 0.4 V Any noise smaller than 0.4 V added to a valid output still produces a valid input at the next gate.
Unused inputs must never be left floating, especially in CMOS, where a floating input can drift into the undefined region and cause both output transistors to conduct. Tie unused AND or NAND inputs high and unused OR or NOR inputs low, or tie them to a used input.
Building Every Gate from NAND or NOR
To prove a gate is universal, you show that NOT, AND and OR can be built from it, because those three are a complete set. The constructions below follow directly from De Morgan's theorem.
| Function | Using NAND only | NAND count | Using NOR only | NOR count |
|---|---|---|---|---|
| NOT A | NAND(A, A) | 1 | NOR(A, A) | 1 |
| A AND B | NOT(NAND(A, B)) | 2 | NOR(A', B') | 3 |
| A OR B | NAND(A', B') | 3 | NOT(NOR(A, B)) | 2 |
| A XOR B | Four-NAND structure | 4 | Five-NOR structure | 5 |
| A XNOR B | XOR plus inverter | 5 | Four-NOR structure | 4 |
XOR from four NAND gates N1 = (A . B)' N2 = (A . N1)' N3 = (B . N1)' Y = (N2 . N3)' = A XOR B Check A=1, B=0: N1 = (1.0)' = 1 N2 = (1.1)' = 0 N3 = (0.1)' = 1 Y = (0.1)' = 1 correct
Converting a Circuit to NAND-NAND or NOR-NOR
Any two-level SOP expression converts directly to NAND-NAND. Replace each AND gate in the first level with a NAND, and replace the final OR with a NAND. The double inversions cancel, which you can see by applying De Morgan's theorem to the output.
F = AB + CD = ((AB + CD)')' double complement = ((AB)' . (CD)')' De Morgan Circuit: N1 = NAND(A, B), N2 = NAND(C, D), F = NAND(N1, N2) Three gates -> one 7400 IC with one gate spare.
In the same way, a POS expression such as F = (A + B)(C + D) maps to NOR-NOR: two NOR gates at the input level feeding one NOR at the output. For multi-level circuits, use bubble pushing: draw an AND gate with inverted inputs as an OR, and an OR gate with inverted inputs as an AND, then cancel any pair of bubbles on the same wire. Wherever a single bubble is left over, insert a NAND or NOR wired as an inverter.
Worked lab example
Suppose a majority-vote circuit must output 1 when at least two of three inputs are 1. Its minimal SOP is F = AB + BC + AC. As NAND-NAND it needs three 2-input NANDs and one 3-input NAND. Using a 7400 for the first level and a 7410 (triple 3-input NAND) for the output, the whole circuit fits in two chips. Verify all eight input combinations with LEDs before calling it done.
Common Mistakes
- Forgetting that NAND-NAND realises SOP and NOR-NOR realises POS, not the other way round.
- Leaving unused CMOS inputs floating, which causes random outputs and extra supply current.
- Missing the power pins: most 14-pin 74xx chips use pin 14 for VCC and pin 7 for GND.
- Assuming XNOR is always available as a standard push-pull IC. Often it is easier to use XOR followed by an inverter.
Summary
The seven basic gates are defined by their truth tables, and XOR is the workhorse of arithmetic and parity. NAND and NOR are universal: NOT, AND and OR can each be built from either, and any SOP circuit maps directly to NAND-NAND while any POS circuit maps to NOR-NOR. Real gates have voltage thresholds and noise margins, and unused inputs must be tied to a valid level. With these skills you are ready to build adders, multiplexers and decoders in the next topic.