Design Challenge: Build Every Logic Gate From Transistors and Relays
Build AND, OR, NOT, NAND, NOR, XOR, and XNOR from primitive switching elements (relays and MOSFETs) rather than from pre-made gate symbols, and in doing so understand why NAND and NOR are called 'universal' while the others are built from them in every real chip.
Every earlier lesson in this course treated AND, OR, and NOT as given — black-box symbols you wired together. This project opens the box. You will build all seven basic gates — AND, OR, NOT, NAND, NOR, XOR, XNOR — twice: once conceptually with electromechanical relays (easy to reason about, historically how the first computers were built) and once with CMOS transistor switches (how every gate in a real chip is actually built today). The brief, as given, is simple: 'Create AND, OR, NOT, NAND, NOR, XOR, XNOR using basic gates' — but the deeper version of that brief, and the one this lesson follows, is to create them using nothing but switches, so that 'basic gates' stops being a mystery and becomes a small, fully-understood circuit of transistors or relays. By the end you will have a bill of materials, a schematic, and a truth-table verification for every one of the seven gates, plus a clear argument for why NAND alone (or NOR alone) is enough to build all the others — the fact that makes universal gates the single most important idea in digital hardware design.
1. Requirements and Specification
The functional requirement is unambiguous: each of the seven gates must, for every combination of 1 or 2 binary inputs, produce the output specified by its standard truth table (this course's earlier Logic Gates module gives you those tables to check against). The design requirement is what makes this a project rather than a lookup: you may not use a pre-built AND/OR/NOT/NAND/NOR/XOR/XNOR component as a building block for another gate in this circuit. Every gate must be constructed from primitive controlled switches — either single-pole relays (a coil that pulls a mechanical contact open or closed) or MOSFET transistors (a gate voltage that lets current flow drain-to-source or blocks it) — plus wires, a power rail, and a ground rail.
Two switch conventions must be supported and clearly labeled in your schematic: a Normally-Open (NO) relay contact / an N-channel MOSFET, which closes (conducts) when its control input is HIGH, and a Normally-Closed (NC) relay contact / a P-channel MOSFET, which closes (conducts) when its control input is LOW. This distinction is the entire trick behind building inversion and behind CMOS itself, so the spec explicitly requires both types to appear in your bill of materials.
2. High-Level Architecture: Series, Parallel, and Pull-Up/Pull-Down
Three wiring patterns cover all seven gates, and understanding them up front makes every individual gate a five-minute exercise rather than a fresh puzzle. Switches in SERIES between the power rail and the output node implement AND: current only reaches the output if switch A AND switch B are both closed. Switches in PARALLEL between the power rail and the output node implement OR: current reaches the output if switch A OR switch B is closed (or both). A single switch that connects the output to ground when its input is HIGH, combined with a resistor (or a second, complementary switch) pulling the output HIGH by default, implements NOT — the output is the electrical opposite of the input.
CMOS formalizes this into a clean, symmetric architecture used in every real chip: a PULL-UP NETWORK of P-channel MOSFETs between VDD and the output, and a PULL-DOWN NETWORK of N-channel MOSFETs between the output and ground, built so that exactly one network conducts for any input combination (never both, never neither — this is what keeps CMOS gates from wasting power or short-circuiting). The pull-down network's topology is series-for-AND / parallel-for-OR as above; the pull-up network is always the electrical DUAL of the pull-down network (series becomes parallel and vice versa), which is why a 2-input CMOS NAND gate takes exactly 4 transistors (2 series NMOS pull-down + 2 parallel PMOS pull-up) and naturally computes the INVERTED AND function for free — no extra inverter needed.
3. Detailed Design: Each Gate, Switch by Switch
NOT (inverter): one NMOS from output to ground, gated by the input; one PMOS from VDD to output, gated by the same input. Input HIGH turns the NMOS on (pulls output LOW) and the PMOS off; input LOW does the reverse (pulls output HIGH). This 2-transistor circuit is the seed every other gate builds on.
NAND (universal building block #1): pull-down network = two NMOS in SERIES between output and ground, gated by A and B; pull-up network = two PMOS in PARALLEL between VDD and output, gated by A and B. Output is LOW only when both NMOS conduct, i.e. only when A AND B are both HIGH — everywhere else at least one PMOS pulls the output HIGH. That is exactly NAND's truth table, built with zero explicit inverters.
NOR (universal building block #2): the electrical dual of NAND — pull-down network = two NMOS in PARALLEL (output pulled LOW if A OR B is HIGH), pull-up network = two PMOS in SERIES (output pulled HIGH only if both A AND B are LOW). Output is HIGH only when both inputs are LOW, matching NOR's truth table.
AND = NAND followed by a NOT. OR = NOR followed by a NOT. Both are 'derived' gates in real silicon — no chip designer builds a native AND from scratch; they chain a universal gate into an inverter because it is cheaper and faster in transistor count than any direct construction.
XOR: relay/CMOS designers use a 4-switch bridge — two series pairs, (A AND NOT-B) in parallel with (NOT-A AND B) — so the output conducts when exactly one input is HIGH. In gate-level terms once you already have AND, OR, and NOT: XOR = (A AND NOT B) OR (NOT A AND B). XNOR is simply XOR followed by NOT, or equivalently (A AND B) OR (NOT A AND NOT B).
The single most important design insight to state explicitly in your write-up: NAND alone (or NOR alone) is functionally complete — every other gate in this project, including NOT, AND, OR, XOR, and XNOR, can be rebuilt using only NAND gates wired together. This is why real fabrication libraries standardize on NAND/NOR cells: a chip factory only needs to perfect one or two transistor layouts and can build literally every digital function from them.
4. Testing and Verification
Verify each gate independently before combining any of them: build (or simulate, in a tool like Logisim, Falstad's circuit simulator, or a breadboard with 2N7000/2N3906 transistors and 10k pull resistors) exactly one gate, apply all 4 input combinations (or 2 for NOT), and confirm the output against the textbook truth table for that gate. Do this for all seven gates before wiring any of them together, since a wrong series/parallel choice in one sub-circuit will otherwise be very hard to diagnose once it is buried inside a derived gate like XOR.
Two edge cases catch almost every first-time builder. First, a 'floating' output: if neither the pull-up nor pull-down network conducts for some input combination, the output node is left electrically undefined (neither driven HIGH nor LOW) and will read as random noise on a multimeter or scope — this happens most often in a badly-drawn relay NOT gate that forgets the pull-up resistor. Second, in a relay-only build, contact bounce (the mechanical contact physically vibrating for a few milliseconds as it closes) can make an otherwise-correct AND or OR gate glitch briefly on every input transition; this is not a logic error, and you should note in your test report that any output glitch lasting less than ~5 ms after an input change is expected mechanical settling, not a design flaw.
CMOS Pull-Up / Pull-Down Duality Rule
A_n means 'NMOS gated by signal A' (conducts when A = HIGH); A_p means 'PMOS gated by signal A' (conducts when A = LOW). This duality is what guarantees a valid CMOS gate never has both networks conducting at once (no short circuit) and never has neither conducting (no floating output), for any single-level AND/OR/NOT combination of inputs.
For any gate built as CMOS:
pull-down network (NMOS) conducts <=> output should be driven LOW
pull-up network (PMOS) conducts <=> output should be driven HIGH
pull-up network topology = DUAL of pull-down topology
(series <-> parallel, swapped)
NAND(A,B): pull-down = A_n SERIES B_n | pull-up = A_p PARALLEL B_p
NOR (A,B): pull-down = A_n PARALLEL B_n | pull-up = A_p SERIES B_p
NOT (A): pull-down = A_n | pull-up = A_pCode Examples
Build each gate one at a time in your simulator or on a breadboard, apply these four (A,B) combinations, and check the measured output column against this table before moving to the next gate. NOT is shown as a function of A alone (its own input) for reference. Expected result: All seven columns must match their gate's measured output for all 4 rows.
This is the constructive proof that NAND is functionally complete: tying both inputs of a NAND together gives NOT for free, and chaining NOTs and NANDs reproduces every other gate, including the famously tricky 4-NAND XOR circuit that real standard-cell libraries actually use instead of a dedicated XOR transistor layout. Include this derivation in your write-up as evidence you understand *why* NAND is universal, not just that it is.
NOT(A) = NAND(A, A)
A B | AND OR NOT-A NAND NOR XOR XNOR
0 0 | 0 0 1 1 1 0 1
0 1 | 0 1 1 1 0 1 0
1 0 | 0 1 0 1 0 1 0
1 1 | 1 1 0 0 0 0 1NOT(A) = NAND(A, A)
AND(A,B) = NOT( NAND(A,B) ) = NAND( NAND(A,B), NAND(A,B) )
OR(A,B) = NAND( NOT(A), NOT(B) ) = NAND( NAND(A,A), NAND(B,B) )
NOR(A,B) = NOT( OR(A,B) )
XOR(A,B) = NAND( NAND(A, NAND(A,B)), NAND(B, NAND(A,B)) ) -- 4-NAND XOR
XNOR(A,B) = NOT( XOR(A,B) )CMOS NAND Gate (Pull-Up / Pull-Down Networks)
Output is pulled LOW only when both NMOS conduct (A=1 AND B=1); every other input combination leaves at least one PMOS conducting, pulling OUT HIGH — exactly the NAND truth table, with no separate inverter stage.
VDD
|
+---------+---------+
| |
A -| PMOS PMOS |- B <- pull-up: PARALLEL
| |
+---------+---------+
|
+----- OUT (= NAND(A,B))
|
B -| NMOS
|
A -| NMOS <- pull-down: SERIES
|
GNDImportant Rules
No pre-built gate ICs or gate symbols as building blocks — only individual switches (relay contacts or MOSFETs), wires, and passive components (resistors) are allowed inside each gate's circuit.
Every gate's pull-down network must be the electrical dual of its pull-up network so exactly one network conducts for any input combination (no short circuit, no floating output).
Label every switch in your schematic as NO/NMOS or NC/PMOS so the grader can trace series/parallel logic directly to AND/OR behavior.
Verify each gate in isolation against its truth table before using it inside a derived gate (AND from NAND+NOT, OR from NOR+NOT, XOR from AND/OR/NOT).
This Is Literally How Every CPU Is Built
This project is not a simplified toy version of real chip design — it is real chip design, just at a hand-buildable scale. Every gate on every CPU, GPU, and microcontroller ever fabricated is a pull-up/pull-down CMOS network exactly like the ones in this project, laid out by automated tools instead of by hand, and packed billions-strong onto a few square centimeters of silicon. Standard-cell libraries that chip designers buy from foundries are, at their core, a catalog of pre-verified NAND, NOR, and NOT transistor layouts (plus a few common derived gates like XOR and multiplexers) — exactly the set you just built and verified by hand — that synthesis tools stitch together to implement any Boolean function a designer describes in Verilog.
Wiring the pull-up network with the same series/parallel topology as the pull-down network (e.g., two series PMOS under two series NMOS for a 'NAND').
Make the pull-up network the electrical DUAL of the pull-down network: series NMOS pairs with parallel PMOS, and parallel NMOS pairs with series PMOS.
If pull-up and pull-down share the same topology, there are input combinations where both networks conduct at once (a direct short from VDD to ground, which can destroy the transistors) or where neither conducts (a floating, undefined output). The dual-network rule is the only way to guarantee exactly one network conducts for every input combination.
Building a relay NOT gate with only a single switch to ground and no pull-up path, assuming the output will 'naturally' read HIGH when the switch is open.
Add an explicit pull-up resistor (or a complementary NC/PMOS switch) from the output node to the power rail so the output is actively driven HIGH whenever the pull-down switch is open.
An output node with no path to either rail is 'floating' — it has no defined voltage and will pick up electrical noise, read inconsistently on a multimeter, and behave unpredictably when driving another gate's input downstream.
In a CMOS gate, why must the pull-up network always be the electrical dual of the pull-down network (series becomes parallel and vice versa)? A. It reduces the total transistor count to the minimum possible for any gate B. It guarantees that for every input combination, exactly one of the two networks conducts, avoiding both a VDD-to-ground short and a floating output C. It is required so the gate can be simulated in software before fabrication D. It allows the same physical transistor to be reused in both networks
B. It guarantees that for every input combination, exactly one of the two networks conducts, avoiding both a VDD-to-ground short and a floating output — The dual-network rule is a correctness requirement, not an optimization: it ensures pull-up and pull-down are never both active (which would short VDD to ground) and never both inactive (which would leave the output undefined/floating). Every valid single-output CMOS gate obeys this rule.
Why do real chip fabrication libraries build AND and OR gates as NAND+inverter and NOR+inverter rather than as a single direct 'AND network' or 'OR network'? A. AND and OR gates are physically impossible to build directly with transistors B. A NAND (or NOR) plus a small inverter uses fewer transistors and is faster than trying to build a native non-inverting AND/OR pull structure, so foundries standardize on the inverting universal gates as base cells C. AND and OR gates only work correctly with relays, not with MOSFETs D. It is purely a historical convention with no electrical reason behind it
B. A NAND (or NOR) plus a small inverter uses fewer transistors and is faster than trying to build a native non-inverting AND/OR pull structure, so foundries standardize on the inverting universal gates as base cells — CMOS pull-networks naturally produce an inverted result (that's why NAND/NOR are the 'free' 4-transistor gates); building a non-inverting AND or OR directly would need more transistors and an extra stage anyway, so standard-cell libraries just standardize on NAND/NOR as base cells and derive AND/OR by adding one inverter.
A student builds a relay-based AND gate and, on power-up, sometimes sees the output glitch HIGH for about 2 milliseconds right when both input switches are flipped closed, even though the final settled output is correct. What is the most likely explanation? A. The AND gate's truth table is being computed incorrectly B. One of the relay contacts is wired as NC instead of NO C. Mechanical contact bounce in the relays, which briefly vibrate open/closed on every transition before settling — expected electromechanical behavior, not a logic design error D. The pull-up and pull-down networks are not duals of each other
C. Mechanical contact bounce in the relays, which briefly vibrate open/closed on every transition before settling — expected electromechanical behavior, not a logic design error — Relay contacts are physical metal pieces that physically vibrate for a few milliseconds when actuated ('contact bounce'), causing brief, self-correcting glitches on any transition. Since the design ultimately settles to the correct value, this is expected mechanical behavior (the same reason digital designs debounce physical buttons), not a logic error in the gate's wiring.
Extend your build with an 8th gate: a 2-input multiplexer (MUX) built only from switches (not from AND/OR/NOT sub-blocks), where a SELECT input chooses whether the output follows input A or input B.
Use two NMOS pass transistors: the first has its gate driven by SELECT and its channel between A and OUT; the second has its gate driven by NOT-SELECT (built from your existing inverter) and its channel between B and OUT. When SELECT=1, only the first passes A through; when SELECT=0, only the second passes B through — implementing OUT = SELECT ? A : B with just 3 transistors total (2 pass transistors + 1 inverter for NOT-SELECT).
A MUX is a pass-transistor structure: one switch gated by SELECT connects A to the output, and one switch gated by NOT-SELECT connects B to the output; only one path conducts at a time. Think about how you'd generate NOT-SELECT using switches you have already built.