Transistors, Gates, and Boolean Functions

The previous module read a word as a number and then as a vector of bits with an algebra over it. That algebra was abstract: symbols on a page. This lesson grounds it in silicon: every AND, OR, and NOT in that algebra is a small arrangement of switches, and a switch is one transistor. By the end you will be able to take a Boolean function written as a truth table and lay out, gate by gate, a circuit that computes it.

The transistor as a switch

The building block of a digital circuit is the MOS transistor (metal-oxide semiconductor), and for our purposes it behaves as one thing: a switch whose state is controlled by a voltage. It has three terminals — a gate, a source, and a drain — and the voltage on the gate decides whether current may flow between source and drain. We need only two flavors, and they are opposites.

• An NMOS transistor conducts (closes the switch) when its gate is at a high voltage (logic $1$) and is open when the gate is low.
• A PMOS transistor is the mirror image: it conducts when its gate is low (logic $0$) and is open when the gate is high.

We treat a high voltage as the bit $1$ and a low voltage (ground) as the bit $0$. This one convention connects the physics to Boolean algebra: the rest is deciding which switches connect a wire to the high supply and which connect it to ground.

From switches to an inverter

A working gate uses two complementary networks. A pull-up network of PMOS transistors can connect the output to the high supply (drive it to $1$); a pull-down network of NMOS transistors can connect the output to ground (drive it to $0$). The design rule of CMOS logic is that for every input combination exactly one network conducts — never both (which would short the supply to ground) and never neither (which would leave the output floating).

The simplest case is the inverter, the NOT gate. One PMOS pulls up, one NMOS pulls down, and they share the input.

Trace it. With $A=0$: the PMOS conducts (gate is low), the NMOS is open, so the output is tied to the high supply: output $1$. With $A=1$: the PMOS opens, the NMOS conducts, output tied to ground: output $0$. The output is the complement of the input, and at no input do both networks conduct. Nor is the output ever left floating: one path or the other always drives it, which is what lets a CMOS gate's output feed the next gate's input with a clean, restored logic level. And because in steady state the conducting network sees an open circuit on the other side, an idle CMOS gate draws essentially no current; power is spent only while switching, which is why CMOS displaced every earlier logic family.

NAND at the transistor level

The same two-network construction scales to two inputs, and the cheapest useful case is NAND. The output must be $0$ exactly when $A\cdot B=1$, so the pull-down network is two NMOS in series: the path to ground conducts only when both gates are high. By complementarity the pull-up must conduct in every other case, so it is two PMOS in parallel: either input at $0$ opens a path to the supply.

Check the four cases against the truth table. $A=B=1$: both series NMOS conduct, the output is pulled to ground, and both PMOS are open: output $0$. Any input at $0$: the series chain is broken somewhere, so ground is unreachable, while the PMOS with the low gate conducts: output $1$. That is $\overline{A\cdot B}$ in four transistors. A NOR swaps the roles: NMOS in parallel (either input $1$ grounds the output), PMOS in series.

The structural lesson generalizes. A single pull-up/pull-down pair can only compute an inverting function (the NMOS network connects the output to $0$, never to $1$), so the gates CMOS gives you natively are NOT, NAND, and NOR. AND and OR each cost a NAND or NOR plus an inverter. The transistor counts:

Between NAND and NOR, NAND wins on speed: electrons (which carry NMOS current) are two to three times more mobile in silicon than the holes that carry PMOS current, so a series stack hurts far less in the NMOS network, where NAND puts it, than in the PMOS network, where NOR does. Cheapest and fastest of the two-input gates, NAND is the primitive real cell libraries are organized around.

Propagation delay

A gate is not instantaneous. Its output drives a wire plus the gate inputs of everything downstream, and that load is a capacitance: to switch the output the conducting network must charge or discharge that capacitance through the resistance of its transistors. The time from an input change to the output settling at its new value is the gate's propagation delay, written $t_{pd}$.

Three things set the number. Drive strength: wider transistors have lower resistance and switch their load faster, at the price of area and of presenting more input capacitance to the gates that drive them. Fan-out: each extra gate input hung on an output adds capacitance, so a gate driving eight others is markedly slower than one driving one. Fan-in: every extra input adds a transistor to a series stack, raising its resistance, which is why wide gates are slow and an 8-input AND is built as a tree of small ones rather than one monster gate. In a current process a simple gate's delay is a few tens of picoseconds; a signal that must traverse twenty gates in sequence therefore needs on the order of a nanosecond to settle. That chain-of-delays arithmetic — the critical path — is what bounds a processor's clock frequency, and the next lesson does the accounting explicitly.

The seven standard gates

Above the transistor level we stop drawing switches and work with gates as primitives, each defined by a truth table. Seven cover essentially all of digital logic.

Three relationships are worth naming. NAND and NOR are the complements of AND and OR — the bubble on a gate symbol means invert the output. XOR is $1$ exactly when its inputs differ, which makes it the one-bit not equal test and, equivalently, addition modulo $2$; its complement XNOR is the one-bit equality test. These will reappear directly when we build an adder and a comparator.

Functional completeness: NAND is enough

A set of gates is functionally complete if every Boolean function can be built from it alone. AND, OR, and NOT together are complete: any truth table can be written as ANDs of inputs, ORed together, with NOTs where needed. In fact NAND alone is complete, and so is NOR alone. Since NAND is one cheap CMOS gate, a whole processor can in principle be a sea of identical NANDs.

The proof is to build the complete set $\{$NOT, AND, OR$\}$ from NAND:

The NOT comes from tying both NAND inputs to the same signal: $\overline{A\cdot A}=\overline{A}$. The AND is then a NAND followed by that inverter. The OR uses De Morgan's law — $A+B=\overline{\overline{A}\cdot \overline{B}}$ — so we invert each input (two NAND-inverters) and NAND the results. Everything reduces to one gate type, and since NAND is also the cheapest and fastest two-input gate CMOS offers, completeness has practical weight: a synthesis tool can, and often does, map a whole design onto NANDs and inverters.

Trace the OR build case by case to be sure the three NANDs really compute $A+B$. Write $N(x,y)=\overline{x\cdot y}$ for one NAND. The first two gates invert: $\overline{A}=N(A,A)$ and $\overline{B}=N(B,B)$. The third NANDs those: $N(\overline{A},\overline{B})=\overline{\overline{A}\cdot \overline{B}}$, which De Morgan says is $A+B$. The full truth table confirms every row:

The sixth column (three NANDs) and the last column (the OR we wanted) match on all four rows. Counting cost: this OR is three NANDs at four transistors each, twelve in all, versus six for a native CMOS OR — the price of insisting on one gate type. Real synthesis does not literally pay that everywhere; it maps to a library of cells (below) and uses NAND-heavy structures where they help. The point of the exercise is that the mapping always exists, which is what functional completeness guarantees.

From a truth table to a sum-of-products circuit

The everyday job is the reverse: you are handed a Boolean function as a truth table and must produce a circuit. The mechanical procedure is the sum of products (SOP). For each row whose output is $1$, write the product (AND) of the inputs, complementing any input that is $0$ in that row; this product — a minterm — is $1$ for exactly that one input combination. OR all the minterms together, and the result is $1$ in precisely the rows you wanted.

Take a one-bit function $f(A,B,C)$ that is $1$ when at least two of its three inputs are $1$ — the majority function we will need for a full adder's carry. Its $1$-rows are $011$, $101$, $110$, and $111$, giving

where the right-hand form is the simplified version (each pair being $1$ already forces the majority). As a circuit, the simplified majority is three AND gates feeding one OR.

Sum of products always works, being a constructive proof that gates can compute any Boolean function, but it is rarely minimal. The four-minterm form above uses four three-input ANDs and a four-input OR; the simplified $AB+AC+BC$ uses three two-input ANDs and a three-input OR. Same truth table, fewer and smaller gates. Where did the simplification come from, and can we find it mechanically?

Minimizing with a Karnaugh map

The algebra that collapsed four minterms to three products rests on one identity: $X\overline{Y}+XY=X$. Two minterms that agree on every variable but one, where one has that variable true and the other false, merge into a single product with that variable dropped. The Karnaugh map (K-map) is a truth table redrawn so that mergeable pairs sit next to each other, turning a symbol-pushing search into looking for adjacent $1$s.

The row/column ordering does the work: labels run in Gray code ($00,01,11,10$) so that any two neighboring cells — horizontally or vertically, and wrapping around the edges — differ in exactly one variable. A block of adjacent $1$s whose size is a power of two is therefore a single product term, and the bigger the block, the fewer variables it names.

Redraw the majority function on a three-variable map, $A$ down the side, $BC$ across the top:

Read the covers off the map. The two $1$s in the bottom row's right pair share $A=1,B=1$ (their $C$ differs), so they merge to $AB$. The bottom-row middle pair shares $A=1,C=1$: that is $AC$. The vertical pair in column $BC=11$ shares $B=1,C=1$: that is $BC$. Three overlapping pairs cover all four $1$s, and the minimal sum is exactly $AB+AC+BC$ — the answer we pulled out of the air earlier, now found by inspection. The single lonely $1$ never happens here because every $1$ has a neighbor; when a $1$ is isolated, it forces a full three-variable minterm of its own — no simplification exists for that row.

The same map handles don't-cares, written $\times$: a cell you may treat as either $0$ or $1$. Group a $\times$ into a block when doing so grows the block (and shrinks the term), ignore it otherwise. The next lesson uses exactly this freedom to shrink a binary-coded-decimal comparator. K-maps stay readable up to four variables; past that the adjacencies stop being visual and synthesis tools switch to the Quine–McCluskey algorithm and its heuristic descendants, but the principle never changes — merge terms that differ in one variable.

What matters now is that the path truth table $\to$ minterms $\to$ AND-OR circuit is always available, and a small map turns the sprawling minterm form into a tight one.

From ideal gates to fabricated chips

CS:APP draws gates as ideal symbols and stops; two threads from the public hardware literature connect them to the chips actually fabricated.

The transistor stopped being a plane. Every delay estimate here assumes a planar MOSFET — a flat channel under a flat gate. Below roughly the 22 nm node the planar channel became too leaky to switch cleanly off, and industry moved to the FinFET, a channel raised into a thin fin the gate wraps on three sides for tighter electrostatic control (Hisamoto et al. first demonstrated the fully depleted lean-channel transistor in 1989; Intel shipped it in volume at 22 nm in 2012). The three-sided gate is why sub-nanometer-era CMOS still has a usable on/off ratio. The switch abstraction survives the change intact: a FinFET is still a voltage-controlled switch, just a better-behaved one, and the newest gate-all- around nanosheet devices wrap the channel on all four sides for the same reason. Nothing above this paragraph changes; the transistor budget and the NAND-is- cheapest argument hold regardless of the device's cross-section.

You never wire NANDs by hand. Real designs are written in a hardware description language — Verilog or VHDL — at the register-transfer level, and a logic synthesis tool compiles that text into gates, exactly the truth- table-to-circuit path of this lesson run at scale. The synthesizer draws from a standard-cell library: a few hundred pre-characterized cells (inverters, two- and three-input NANDs and NORs, AOI/OAI compound gates, flip-flops), each with a measured area and delay, laid out once by the foundry. Synthesis is then an optimization problem — cover the Boolean network with library cells to minimize delay on the critical path subject to an area budget — and it leans on the same De Morgan and factoring identities we used by hand, plus decades of algorithms (the classic account is De Micheli's Synthesis and Optimization of Digital Circuits, 1994). HCL is a stripped-down teaching stand-in for this flow: the case and in constructs of the next lesson are what a synthesizable subset of Verilog would express as always @(*) blocks. Two-level minimization by K-map is the schoolbook version; Espresso (Brayton et al., 1984) is the heuristic minimizer that made it practical for real multi-output functions.

With single gates in hand, the next lesson steps up to whole combinational blocks and the hardware control language CS:APP uses to describe them.