---
title: Transistors, Gates, and Boolean Functions
module: Digital Logic
moduleNumber: 3
lessonNumber: 1
order: 301
summary: >
  A processor is built from millions of transistor switches. We start at the MOS
  transistor as a voltage-controlled switch, build the CMOS inverter and NAND
  transistor by transistor, meet the seven standard gates with their truth
  tables, show that NAND alone is functionally complete, price each gate in
  transistors and in time, and turn any truth table into a sum-of-products
  circuit.
topics: [Digital Logic]
sources:
  - book: Bryant & O'Hallaron
    ref: "CS:APP — §3.1 / §4.2 Logic Design and the Hardware Control Language"
  - book: Bistriceanu
    ref: "Computer Architecture Notes — §2 Basic Organization of a Computer"
---

The previous module read a word as a number and then as a
[vector of bits](/computer-architecture/foundations/boolean-algebra-and-bit-manipulation)
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.

> **Definition (MOS transistor).** A three-terminal voltage-controlled switch.
> An NMOS device closes the source–drain path when its gate input is $1$; a PMOS
> device closes it when its gate input is $0$. A logic gate is a network of these
> switches that drives its output high or low for each combination of inputs.

## 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.

$$
% caption: A CMOS inverter, transistor by transistor. The PMOS (bubbled gate)
% caption: conducts when A = 0 and ties the output to V_DD; the NMOS conducts when
% caption: A = 1 and ties it to ground. Exactly one path conducts for either input,
% caption: so out = NOT A. Two transistors, one gate.
\begin{tikzpicture}[font=\footnotesize,>=stealth]
  \definecolor{acc}{HTML}{2348F2}
  % supply
  \node[anchor=south] at (0,3.45) {$V_{DD}$ (logic 1)};
  \draw (-0.35,3.45) -- (0.35,3.45);
  \draw (0,3.45) -- (0,3.05);
  % PMOS: source lead, channel, drain lead, gate plate, bubble
  \draw (0,3.05) -- (0,2.65) -- (-0.3,2.65);
  \draw (-0.3,2.65) -- (-0.3,2.05);
  \draw (-0.3,2.05) -- (0,2.05) -- (0,1.65);
  \draw (-0.45,2.55) -- (-0.45,2.15);
  \draw (-0.57,2.35) circle (0.12);
  \draw (-1.8,2.35) -- (-0.69,2.35);
  \node[anchor=west] at (0.3,2.35) {PMOS: conducts when $A=0$};
  % NMOS: drain lead, channel, source lead, gate plate
  \draw (0,1.65) -- (0,1.15) -- (-0.3,1.15);
  \draw (-0.3,1.15) -- (-0.3,0.55);
  \draw (-0.3,0.55) -- (0,0.55) -- (0,0.15);
  \draw (-0.45,1.05) -- (-0.45,0.65);
  \draw (-1.8,0.85) -- (-0.45,0.85);
  \node[anchor=west] at (0.3,0.85) {NMOS: conducts when $A=1$};
  % shared input trunk
  \draw (-2.6,1.6) node[anchor=east] {$A$} -- (-1.8,1.6);
  \draw (-1.8,2.35) -- (-1.8,0.85);
  \fill (-1.8,1.6) circle (1.1pt);
  % output tap between the two devices
  \draw (0,1.6) -- (1.7,1.6) node[anchor=west, text=acc] {$\text{out}=\overline{A}$};
  \fill (0,1.6) circle (1.1pt);
  % ground symbol
  \draw (0,0.15) -- (0,0.0);
  \draw (-0.3,0.0) -- (0.3,0.0);
  \draw (-0.2,-0.12) -- (0.2,-0.12);
  \draw (-0.1,-0.24) -- (0.1,-0.24);
  \node[anchor=north] at (0,-0.34) {GND (logic 0)};
\end{tikzpicture}
$$

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.

$$
% caption: A CMOS NAND gate: two PMOS in parallel pull up, two NMOS in series pull
% caption: down. Ground is reachable only when A and B are both 1, so the output is
% caption: NOT(AB). Four transistors, one gate.
\begin{tikzpicture}[font=\footnotesize,>=stealth]
  \definecolor{acc}{HTML}{2348F2}
  % supply rail
  \node[anchor=south] at (0,3.72) {$V_{DD}$};
  \draw (-1.2,3.6) -- (1.2,3.6);
  % PMOS A (left branch, gate on the left)
  \draw (-1.2,3.6) -- (-1.2,3.1) -- (-1.5,3.1);
  \draw (-1.5,3.1) -- (-1.5,2.5);
  \draw (-1.5,2.5) -- (-1.2,2.5) -- (-1.2,2.0);
  \draw (-1.65,3.0) -- (-1.65,2.6);
  \draw (-1.77,2.8) circle (0.12);
  \draw (-2.7,2.8) -- (-1.89,2.8);
  % PMOS B (right branch, mirrored, gate on the right)
  \draw (1.2,3.6) -- (1.2,3.1) -- (1.5,3.1);
  \draw (1.5,3.1) -- (1.5,2.5);
  \draw (1.5,2.5) -- (1.2,2.5) -- (1.2,2.0);
  \draw (1.65,3.0) -- (1.65,2.6);
  \draw (1.77,2.8) circle (0.12);
  \draw (2.7,2.8) -- (1.89,2.8);
  % output rail joining the two branches, label above its center
  \draw (-1.2,2.0) -- (1.2,2.0);
  \node[anchor=south, text=acc] at (0,2.08) {$\text{out}=\overline{A\,B}$};
  \fill (0,2.0) circle (1.1pt);
  % NMOS A (top of the series stack, gate on the left)
  \draw (0,2.0) -- (0,1.6) -- (-0.3,1.6);
  \draw (-0.3,1.6) -- (-0.3,1.0);
  \draw (-0.3,1.0) -- (0,1.0) -- (0,0.7);
  \draw (-0.45,1.5) -- (-0.45,1.1);
  \draw (-2.7,1.3) -- (-0.45,1.3);
  % NMOS B (bottom of the stack, mirrored, gate on the right)
  \draw (0,0.7) -- (0,0.4) -- (0.3,0.4);
  \draw (0.3,0.4) -- (0.3,-0.2);
  \draw (0.3,-0.2) -- (0,-0.2) -- (0,-0.5);
  \draw (0.45,0.3) -- (0.45,-0.1);
  \draw (2.7,0.1) -- (0.45,0.1);
  % input trunks
  \node[anchor=east] at (-2.75,2.8) {$A$};
  \draw (-2.7,2.8) -- (-2.7,1.3);
  \node[anchor=west] at (2.75,2.8) {$B$};
  \draw (2.7,2.8) -- (2.7,0.1);
  % ground symbol
  \draw (0,-0.5) -- (0,-0.62);
  \draw (-0.3,-0.62) -- (0.3,-0.62);
  \draw (-0.2,-0.74) -- (0.2,-0.74);
  \draw (-0.1,-0.86) -- (0.1,-0.86);
\end{tikzpicture}
$$

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:

| Gate | Transistors | Why |
| --- | --- | --- |
| NOT | 2 | one complementary pair |
| NAND, NOR | 4 | 2 series + 2 parallel |
| AND, OR | 6 | NAND/NOR + inverter |
| XOR, XNOR | 8+ | no single two-network form |

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}$.

$$
% caption: Propagation delay. The input steps at the dashed left line; the output
% caption: only finishes moving t_pd later, after the transistors have charged or
% caption: drained the load capacitance. Delays add along a chain of gates.
\begin{tikzpicture}[font=\footnotesize,>=stealth]
  \definecolor{acc}{HTML}{2348F2}
  \node[anchor=east] at (-0.3,1.7) {in};
  \draw (0,1.4) -- (1.5,1.4) -- (1.5,2.0) -- (5.5,2.0);
  \node[anchor=east, text=acc] at (-0.3,0.5) {out};
  \draw[acc, thick] (0,0.8) -- (1.7,0.8) -- (2.9,0.2) -- (5.5,0.2);
  \draw[dashed, black] (1.5,1.4) -- (1.5,-0.35);
  \draw[dashed, black] (2.3,0.5) -- (2.3,-0.35);
  \draw[<->] (1.5,-0.2) -- (2.3,-0.2);
  \node[anchor=north] at (1.9,-0.4) {$t_{pd}$};
\end{tikzpicture}
$$

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](/computer-architecture/digital-logic/combinational-logic-and-hcl)
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.

$$
% caption: The standard gates and their truth tables. AND is 1 when both inputs
% caption: are 1; OR when either is; XOR when they differ; NAND, NOR, XNOR are the
% caption: complements of AND, OR, XOR; NOT inverts its single input.
\begin{tikzpicture}[font=\footnotesize,>=stealth,
  cell/.style={draw, minimum size=5.5mm, inner sep=0pt}]
  \definecolor{acc}{HTML}{2348F2}
  % top row: AND, OR, XOR, NOT
  \node[text=acc] at (0.55,2.55) {AND};
  \foreach \r/\a/\b/\o in {0/0/0/0,1/0/1/0,2/1/0/0,3/1/1/1}{
    \node[cell] at (0,1.9-\r*0.55) {\a};
    \node[cell] at (0.55,1.9-\r*0.55) {\b};
    \node[cell,fill=acc!8] at (1.1,1.9-\r*0.55) {\o};}
  \node[text=acc] at (3.05,2.55) {OR};
  \foreach \r/\a/\b/\o in {0/0/0/0,1/0/1/1,2/1/0/1,3/1/1/1}{
    \node[cell] at (2.5,1.9-\r*0.55) {\a};
    \node[cell] at (3.05,1.9-\r*0.55) {\b};
    \node[cell,fill=acc!8] at (3.6,1.9-\r*0.55) {\o};}
  \node[text=acc] at (5.55,2.55) {XOR};
  \foreach \r/\a/\b/\o in {0/0/0/0,1/0/1/1,2/1/0/1,3/1/1/0}{
    \node[cell] at (5.0,1.9-\r*0.55) {\a};
    \node[cell] at (5.55,1.9-\r*0.55) {\b};
    \node[cell,fill=acc!8] at (6.1,1.9-\r*0.55) {\o};}
  \node[text=acc] at (7.775,2.55) {NOT};
  \foreach \r/\a/\o in {0/0/1,1/1/0}{
    \node[cell] at (7.5,1.9-\r*0.55) {\a};
    \node[cell,fill=acc!8] at (8.05,1.9-\r*0.55) {\o};}
  % bottom row: NAND, NOR, XNOR (complements of the row above)
  \node[text=acc] at (0.55,-0.9) {NAND};
  \foreach \r/\a/\b/\o in {0/0/0/1,1/0/1/1,2/1/0/1,3/1/1/0}{
    \node[cell] at (0,-1.55-\r*0.55) {\a};
    \node[cell] at (0.55,-1.55-\r*0.55) {\b};
    \node[cell,fill=acc!8] at (1.1,-1.55-\r*0.55) {\o};}
  \node[text=acc] at (3.05,-0.9) {NOR};
  \foreach \r/\a/\b/\o in {0/0/0/1,1/0/1/0,2/1/0/0,3/1/1/0}{
    \node[cell] at (2.5,-1.55-\r*0.55) {\a};
    \node[cell] at (3.05,-1.55-\r*0.55) {\b};
    \node[cell,fill=acc!8] at (3.6,-1.55-\r*0.55) {\o};}
  \node[text=acc] at (5.55,-0.9) {XNOR};
  \foreach \r/\a/\b/\o in {0/0/0/1,1/0/1/0,2/1/0/0,3/1/1/1}{
    \node[cell] at (5.0,-1.55-\r*0.55) {\a};
    \node[cell] at (5.55,-1.55-\r*0.55) {\b};
    \node[cell,fill=acc!8] at (6.1,-1.55-\r*0.55) {\o};}
\end{tikzpicture}
$$

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:

$$
% caption: NOT, AND, and OR each built from NAND gates alone. Tying both NAND
% caption: inputs together makes an inverter; an AND is a NAND followed by that
% caption: inverter; an OR inverts both inputs first (De Morgan), then NANDs them.
\begin{tikzpicture}[font=\footnotesize,>=stealth,
  g/.style={draw, minimum width=12mm, minimum height=8mm, inner sep=1pt}]
  \definecolor{acc}{HTML}{2348F2}
  % NOT from NAND
  \node[g,fill=acc!8] (n1) at (0,3) {NAND};
  \draw (-1.8,3) node[anchor=east] {$A$} -- (n1.west);
  \draw (n1.east) -- ++(1.0,0) node[anchor=west,text=acc] {$\overline{A}$};
  \node[anchor=west] at (-1.6,3.7) {NOT: tie inputs};
  % AND from NAND + NAND-inverter
  \node[g] (a1) at (0,1.1) {NAND};
  \node[g,fill=acc!8] (a2) at (2.4,1.1) {NAND};
  \draw (-1.8,1.35) node[anchor=east] {$A$} -- (a1.160);
  \draw (-1.8,0.85) node[anchor=east] {$B$} -- (a1.200);
  \draw (a1.east) -- (a2.west);
  \draw (a2.east) -- ++(1.0,0) node[anchor=west,text=acc] {$AB$};
  \node[anchor=west] at (-1.6,1.8) {AND: NAND then invert};
  % OR from NAND: invert each input, then NAND
  \node[g] (o1) at (0,-1.0) {NAND};
  \node[g] (o2) at (0,-2.2) {NAND};
  \node[g,fill=acc!8] (o3) at (2.4,-1.6) {NAND};
  \draw (-1.8,-1.0) node[anchor=east] {$A$} -- (o1.west);
  \draw (-1.8,-2.2) node[anchor=east] {$B$} -- (o2.west);
  \draw (o1.east) -| ($(o3.west)+(-0.4,0)$) |- (o3.160);
  \draw (o2.east) -| ($(o3.west)+(-0.4,0)$) |- (o3.200);
  \draw (o3.east) -- ++(1.0,0) node[anchor=west,text=acc] {$A\!+\!B$};
  \node[anchor=west] at (-1.6,-0.3) {OR: invert inputs, then NAND};
\end{tikzpicture}
$$

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:

| $A$ | $B$ | $\overline{A}$ | $\overline{B}$ | $\overline{A}\cdot\overline{B}$ | $N(\overline{A},\overline{B})$ | $A+B$ |
| --- | --- | --- | --- | --- | --- | --- |
| $0$ | $0$ | $1$ | $1$ | $1$ | $0$ | $0$ |
| $0$ | $1$ | $1$ | $0$ | $0$ | $1$ | $1$ |
| $1$ | $0$ | $0$ | $1$ | $0$ | $1$ | $1$ |
| $1$ | $1$ | $0$ | $0$ | $0$ | $1$ | $1$ |

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

$$
f = \overline{A}\,B\,C \;+\; A\,\overline{B}\,C \;+\; A\,B\,\overline{C} \;+\;
A\,B\,C \;=\; A\,B \;+\; A\,C \;+\; B\,C,
$$

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.

$$
% caption: The majority function AB + AC + BC as a sum-of-products circuit. Three
% caption: AND gates compute the pairwise products; one OR gate sums them. Output
% caption: is 1 whenever at least two inputs are 1.
\begin{tikzpicture}[font=\footnotesize,>=stealth,
  g/.style={draw, minimum width=12mm, minimum height=8mm, inner sep=1pt}]
  \definecolor{acc}{HTML}{2348F2}
  % input rail
  \foreach \y/\lab in {2.4/A, 1.6/B, 0.8/C}
    \node[anchor=east] at (-3.0,\y) {$\lab$};
  % AND gates
  \node[g] (ab) at (0,2.7) {AND};
  \node[g] (ac) at (0,1.4) {AND};
  \node[g] (bc) at (0,0.1) {AND};
  % OR gate
  \node[g,fill=acc!8] (or) at (3.2,1.4) {OR};
  % vertical input lines with taps (route on the left, no crossings)
  \draw (-3.0,2.4) -- (-1.4,2.4); % A trunk
  \draw (-3.0,1.6) -- (-1.6,1.6); % B trunk
  \draw (-3.0,0.8) -- (-1.8,0.8); % C trunk
  % A into AB and AC
  \draw (-1.4,2.4) |- (ab.160);
  \draw (-1.4,2.4) |- (ac.160);
  % B into AB and BC
  \draw (-1.6,1.6) |- (ab.200);
  \draw (-1.6,1.6) |- (bc.160);
  % C into AC and BC
  \draw (-1.8,0.8) |- (ac.200);
  \draw (-1.8,0.8) |- (bc.200);
  % AND outputs into OR (route to a common vertical bus before the OR)
  \draw (ab.east) -| (2.0,2.7) |- (or.150);
  \draw (ac.east) -- (or.180);
  \draw (bc.east) -| (2.0,0.1) |- (or.210);
  \draw (or.east) -- ++(1.2,0) node[anchor=west,text=acc] {$f$};
\end{tikzpicture}
$$

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:

$$
% caption: The majority function on a Karnaugh map. Rows are A; columns are BC in
% caption: Gray-code order 00 01 11 10 so neighbors differ in one bit. The three
% caption: overlapping pairs of adjacent 1s are AB, AC, and BC — read straight off
% caption: the map as the minimal cover.
\begin{tikzpicture}[font=\footnotesize,>=stealth,
  cell/.style={draw, minimum size=8mm, inner sep=0pt}]
  \definecolor{acc}{HTML}{2348F2}
  % column headers: BC in Gray order
  \foreach \c/\lab in {0/{00}, 1/{01}, 2/{11}, 3/{10}}
    \node at (0.9+\c*0.8,1.55) {\lab};
  \node[anchor=east] at (0.4,1.55) {$BC$};
  % row headers: A
  \node at (0.1,0.85) {$0$};
  \node at (0.1,0.05) {$1$};
  \node[anchor=east] at (-0.15,0.45) {$A$};
  % cells: value of majority(A,B,C). row A=0: BC=00,01,11,10 -> 0,0,1,0
  %                                   row A=1: BC=00,01,11,10 -> 0,1,1,1
  \foreach \c/\v in {0/0, 1/0, 2/1, 3/0}
    \node[cell] at (0.9+\c*0.8,0.85) {\v};
  \foreach \c/\v in {0/0, 1/1, 2/1, 3/1}
    \node[cell,fill=acc!8] at (0.9+\c*0.8,0.05) {\v};
  % groupings, drawn as rounded rectangles around adjacent 1-pairs
  % AB: A=1, B=1 -> cells (A=1, BC=11) and (A=1, BC=10): columns 2,3 bottom row
  \draw[acc, thick] (2.15,-0.3) rectangle (3.85,0.4);
  \node[anchor=west, text=acc] at (4.0,0.05) {$AB$};
  % AC: A=1, C=1 -> BC=01 and BC=11: columns 1,2 bottom row
  \draw[acc, thick] (1.4,-0.42) rectangle (3.1,0.28);
  \node[anchor=west, text=acc] at (4.0,-0.55) {$AC$};
  % BC: B=1,C=1 -> BC=11, both rows: column 2, both rows
  \draw[acc, thick] (2.28,-0.18) rectangle (2.92,1.28);
  \node[anchor=west, text=acc] at (4.0,0.85) {$BC$};
\end{tikzpicture}
$$

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](/computer-architecture/digital-logic/combinational-logic-and-hcl)
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.

> **Takeaway.** A transistor is a voltage-controlled switch; complementary
> pull-up and pull-down networks make the inverting gates NOT (2 transistors),
> NAND, and NOR (4 each) almost for free, while AND/OR pay for an extra inverter.
> The seven standard gates each have a truth table, NAND alone is functionally
> complete, and any truth table converts mechanically to a sum-of-products
> circuit of ANDs feeding an OR. None of it is instant: every output charges a
> load through its transistors, and those propagation delays add up along a path.

With single gates in hand, the next lesson steps up to whole **combinational
blocks** and the [hardware control language](/computer-architecture/digital-logic/combinational-logic-and-hcl)
CS:APP uses to describe them.