Compound Gates
Part of Basic Computing
Compound gates combine multiple basic logic operations into single efficient circuits — the building blocks from which all practical digital systems are assembled.
Why This Matters
Real digital designs rarely use isolated AND, OR, and NOT gates. Instead, they use compound gates — circuits that implement two-level logic (an AND or OR followed by an inversion) in a single hardware stage. The most important compound gates are NAND and NOR, which are actually more fundamental than AND and OR because their transistor implementations are simpler and faster.
Understanding compound gates matters for circuit construction because NAND and NOR gates are the native building blocks of CMOS and TTL logic families. Knowing how to build any function from NAND gates alone — a result from Boolean algebra — means needing to stock only one gate type, simplifying component procurement and inventory management in resource-constrained environments.
Compound gates also include multiplexers, demultiplexers, and exclusive OR gates — components that appear in virtually every significant digital circuit from memory addressing to error detection.
NAND and NOR: Universal Gates
NAND (Not-AND): output is 0 only when ALL inputs are 1; otherwise output is 1. Truth table for 2-input NAND:
| A | B | A NAND B |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
NOR (Not-OR): output is 1 only when ALL inputs are 0; otherwise output is 0.
NAND and NOR are universal: any Boolean function can be built from NAND gates alone (or from NOR gates alone). This is proven by implementing NOT, AND, and OR from NANDs:
- NOT A = A NAND A (connect both inputs together)
- A AND B = NOT(A NAND B) = (A NAND B) NAND (A NAND B)
- A OR B = NOT(NOT A AND NOT B) = (A NAND A) NAND (B NAND B)
Using only 74HC00 (quad 2-input NAND) chips, any logic circuit can be constructed. The 74HC00 contains four NAND gates; one chip provides NOT, AND, and OR with gates to spare.
NAND universality in CMOS: a CMOS NAND gate uses fewer transistors than a CMOS AND gate (AND = NAND + NOT = 4 transistors + 2 transistors, whereas NAND is 4 transistors). Using NAND directly is structurally simpler.
NOR-only implementation is equally valid. Historical context: the Apollo Guidance Computer used exclusively NOR gates, simplifying manufacturing by requiring only one gate type across the entire machine.
XOR and XNOR
XOR (Exclusive OR): output is 1 when inputs DIFFER; output is 0 when inputs are the SAME. Truth table:
| A | B | A XOR B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
XOR is essential for addition (XOR gives the sum bit without carry) and parity calculation. A chain of XOR gates over N bits produces 1 if an odd number of bits are 1 — this is the basis of simple parity error detection.
XOR from NAND gates (4 gates total):
- G1 = A NAND B
- G2 = A NAND G1
- G3 = B NAND G1
- XOR = G2 NAND G3
XNOR (Exclusive NOR): opposite of XOR — output is 1 when inputs are the SAME. Used for equality testing: A XNOR B = 1 means A equals B. Testing N-bit equality: XNOR each pair of corresponding bits, then AND all results.
Multiplexers
A multiplexer (MUX) selects one of N data inputs based on a binary selection code, routing it to the output. Essential for data routing in ALUs, memory addressing, and bus systems.
2-to-1 MUX: one select input (S), two data inputs (D0, D1), one output (Y).
- When S=0: Y = D0
- When S=1: Y = D1
Gate implementation: Y = (NOT S AND D0) OR (S AND D1)
4-to-1 MUX: two select inputs (S1, S0), four data inputs (D0–D3).
- When S1S0 = 00: Y = D0
- When S1S0 = 01: Y = D1
- When S1S0 = 10: Y = D2
- When S1S0 = 11: Y = D3
A MUX can also implement arbitrary Boolean functions: connect the data inputs to constants (0 or 1) based on the desired truth table. A 4-to-1 MUX can implement any 2-variable function; an 8-to-1 MUX can implement any 3-variable function.
Demultiplexer (DEMUX): opposite operation — routes one input to one of N outputs based on selection code. Used for address decoding (select which memory chip is active based on address bits).
AND-OR-INVERT (AOI) Gates
AOI gates implement the function NOT(A·B + C·D) in a single stage — two AND operations followed by NOR. These appear in standard cell libraries because this two-level structure maps efficiently to CMOS.
AOI-22 (2-input AND, 2-input AND, NOR): Y = NOT(A·B + C·D)
The AOI pattern is important for designers because it reveals how to decompose complex functions into two-level logic. Sum-of-Products (SOP) form maps directly to AND-OR (AOI) structure; Product-of-Sums (POS) maps to OR-AND (OAI) structure.
Practical NAND-Only Circuit Design
Converting any circuit to NAND-only: apply De Morgan’s theorem systematically.
- Convert all gates to AND, OR, NOT form
- Replace all AND gates with NAND-NAND: A AND B = NOT(NOT(A AND B)) — one NAND produces NAND output, a second NAND with tied inputs inverts it back to AND
- Replace all OR gates using De Morgan: A OR B = NOT(NOT A AND NOT B) = NOT A NAND NOT B — so invert both inputs then NAND
- Absorb adjacent inversions: if a NAND output feeds an inverter (NAND with tied inputs), replace both with AND (cancellation)
This process always terminates in a NAND-only circuit. The result may use more gates than a mixed-gate design, but uses only one component type.
For a survival electronics kit, stocking a supply of 74HC00 (NAND) chips allows construction of any logic circuit. One hundred 74HC00 chips provide 400 NAND gates — sufficient for a complete simple CPU when used judiciously.