# Lecture 5. Boolean algebra

## 5.1 Overview and motivation

Lecture 4 introduced the Boolean domain $\{0,1\}$, the operators $\wedge$ (AND), $\vee$ (OR), $\neg$ (NOT), their truth tables, and the basic identities — commutativity, associativity, distributivity, De Morgan, absorption, and the complement laws. We take all of that as known and use it freely. Throughout these notes we write $\overline{A}$ for the complement of $A$ (equivalently $\neg A$), and we use the overline $\overline{\cdot}$ consistently for negation.

That algebra was, in Lecture 4, a set of *rules*. This lecture puts the rules to work. Every question below is ultimately about **cost**: a Boolean function can be written in infinitely many equivalent ways, and in hardware each operator we write becomes a physical gate that occupies silicon area, dissipates power, and adds delay. A processor contains billions of gates; shaving one gate off a circuit that is instantiated a million times matters. So the central engineering problem is: *given the behaviour we want (a truth table), find the cheapest formula that produces it.* This lecture develops the theory and the algorithms that answer that problem.

We proceed through five questions.

- **How many functions are there, and how do they relate?** — the counting principle $2^{2^n}$ and the sixteen functions of two variables.
- **How few operators do we need?** — *functionally complete* bases, culminating in the single-gate bases NAND ($\uparrow$) and NOR ($\downarrow$). We prove completeness rigorously.
- **How is Boolean algebra realised in hardware?** — logic gates, integrated circuits, and translating a formula into a gate network.
- **How do we describe a function canonically?** — the canonical normal forms (CDNF and CCNF, plus the XOR-based ANF) read off a truth table, proved to exist and to be unique.
- **How do we make a formula as small as possible, systematically?** — algebraic minimization, Karnaugh maps, and the Quine–McCluskey algorithm, with a cost comparison before and after.

Everything here is *combinational*: an output depends only on the present inputs, with no memory. Because there are only two truth values, every function of $n$ variables is completely described by a finite truth table of $2^n$ rows — a fact we lean on constantly. Adding memory (state that depends on past inputs) turns combinational logic into *sequential* logic, taken up in Lecture 14 (Automata theory, including Mealy/Moore sequential machines); the minimization techniques here still apply to the combinational "next-state" and "output" blocks inside a sequential machine.

> **Remark (why this is not just algebra).** In Lecture 4 two formulas were "equal" if the identities could transform one into the other. Here we adopt the *semantic* definition: two formulas are equal iff they have the same truth table. The identities are *sound and complete* for this semantics (Boolean algebra is complete over $\{0,1\}$), so the two notions coincide — but the truth-table view is what makes the algorithms below possible, because a truth table is a finite object we can compute on directly.

---

## 5.2 Boolean functions and how many there are

**Boolean function.** A **Boolean function of $n$ variables** is a map

$$
f : \{0,1\}^n \longrightarrow \{0,1\}.
$$

Its domain has $2^n$ points (the rows of a truth table), and to each point it assigns one output bit. Two Boolean functions are equal iff they agree on all $2^n$ inputs.

Because a function is fixed exactly by choosing the output bit for each of the $2^n$ input rows, and each choice is independent with $2$ options, we get the fundamental counting principle.

> **Theorem 5.1 (Counting Boolean functions).** There are exactly $2^{\,2^n}$ distinct Boolean functions of $n$ variables.
>
> *Proof.* A function is determined by its output column: a string of $2^n$ bits, one per input row. Distinct output columns give distinct functions (they differ on some row), and every output column arises from some function. Hence functions of $n$ variables are in bijection with bit-strings of length $2^n$, of which there are $2^{2^n}$. $\blacksquare$

| $n$ | inputs $2^n$ | functions $2^{2^n}$ |
|---|---|---|
| 0 | 1 | 2 (the constants $0,1$) |
| 1 | 2 | 4 ($0,\ 1,\ A,\ \overline{A}$) |
| 2 | 4 | 16 |
| 3 | 8 | 256 |
| 4 | 16 | 65 536 |
| 5 | 32 | $\approx 4.29\times 10^{9}$ |

The double exponential explodes at once, which is precisely why we do not enumerate functions but reason about them symbolically. For $n=2$ the number is small enough to list in full, and the list is worth memorising because it names every operation we use.

### The sixteen functions of two variables

![Truth-table columns for eight of the sixteen two-variable Boolean functions](img/l05_sixteen.png)

A function of two variables assigns an output to each of the four rows $(A,B)\in\{00,01,10,11\}$; there are $2^4 = 16$ ways to fill the column, hence **16 distinct two-variable Boolean functions**. Reading the output column top-to-bottom for the input order $(A,B)=00,01,10,11$:

| Output $00\,01\,10\,11$ | Expression | Name |
|---|---|---|
| 0 0 0 0 | $0$ | constant **false** |
| 0 0 0 1 | $A\wedge B$ | **AND** (conjunction) |
| 0 0 1 0 | $A\wedge \overline{B}$ | inhibition ($A$ but not $B$) |
| 0 0 1 1 | $A$ | projection / left argument |
| 0 1 0 0 | $\overline{A}\wedge B$ | inhibition ($B$ but not $A$) |
| 0 1 0 1 | $B$ | projection / right argument |
| 0 1 1 0 | $A\overline{B}\vee \overline{A}B$ | **XOR** $A\oplus B$ (exclusive OR) |
| 0 1 1 1 | $A\vee B$ | **OR** (disjunction) |
| 1 0 0 0 | $\overline{A}\wedge \overline{B}$ | **NOR** $A\downarrow B$ |
| 1 0 0 1 | $A B\vee \overline{A}\,\overline{B}$ | **XNOR** / equivalence $A\odot B$ |
| 1 0 1 0 | $\overline{B}$ | NOT $B$ |
| 1 0 1 1 | $A\vee \overline{B}$ | converse implication $B\to A$ |
| 1 1 0 0 | $\overline{A}$ | NOT $A$ |
| 1 1 0 1 | $\overline{A}\vee B$ | implication $A\to B$ |
| 1 1 1 0 | $\overline{A}\vee \overline{B}$ | **NAND** $A\uparrow B$ |
| 1 1 1 1 | $1$ | constant **true** |

Notice two distinct symmetries. **Complementing every output bit** is negation ($f\mapsto\overline f$): it pairs AND $\leftrightarrow$ NAND, OR $\leftrightarrow$ NOR, XOR $\leftrightarrow$ XNOR, $A\leftrightarrow\overline A$, and $0\leftrightarrow 1$. **Dualization** is the *separate* operation $f^{d}(A,B)=\overline{f(\overline A,\overline B)}$ that swaps $\wedge\leftrightarrow\vee$ and $0\leftrightarrow1$ (the operational form of the principle of duality from Lecture 4); it pairs AND $\leftrightarrow$ OR, NAND $\leftrightarrow$ NOR, and XOR $\leftrightarrow$ XNOR. Every one of the sixteen can be written with $\wedge,\vee,\neg$ only — which raises the question of how small a set of operators still suffices.

---

## 5.3 Functional completeness

**Functionally complete set (basis).** A set $\mathcal{B}$ of Boolean operations is **functionally complete** if *every* Boolean function, of *any* number of variables, can be expressed by a formula that uses only operations from $\mathcal{B}$ (and the input variables).

This is a strong claim — it quantifies over all functions of all arities — so it needs a proof, not a plausibility argument. The cleanest tool is **Shannon's expansion**, which peels off one variable at a time.

> **Theorem 5.2 (Shannon expansion).** For any Boolean function $f(x_1,\dots,x_n)$ and any variable $x_i$,
>

$$
f = \bigl(x_i \wedge f|_{x_i=1}\bigr)\ \vee\ \bigl(\overline{x_i}\wedge f|_{x_i=0}\bigr),
$$

> where $f|_{x_i=c}$ (the *cofactor*) is $f$ with $x_i$ replaced by the constant $c$.
>
> *Proof.* Two functions are equal iff they agree on every input, so fix an input and split on the value of $x_i$.
> If $x_i=1$: the right-hand side is $(1\wedge f|_{x_i=1})\vee(0\wedge f|_{x_i=0}) = f|_{x_i=1}$, which is exactly $f$ evaluated with $x_i=1$.
> If $x_i=0$: it is $(0\wedge f|_{x_i=1})\vee(1\wedge f|_{x_i=0}) = f|_{x_i=0}$, exactly $f$ with $x_i=0$.
> In both cases the two sides agree, so they are equal as functions. $\blacksquare$

> **Theorem 5.3 ($\{\wedge,\vee,\neg\}$ is functionally complete).**
>
> *Proof.* Induction on the number of variables $n$.
>
> *Base $n=1$.* The four one-variable functions are $0,\,1,\,x,\,\overline{x}$, expressible as $x\wedge\overline{x}$, $x\vee\overline{x}$, $x$, and $\overline{x}$ respectively — all in the basis.
>
> *Inductive step.* Assume every function of $n-1$ variables is expressible. Let $f$ have $n$ variables. By Shannon expansion on $x_n$,
>

$$
f = \bigl(x_n\wedge g\bigr)\vee\bigl(\overline{x_n}\wedge h\bigr),\qquad g=f|_{x_n=1},\ \ h=f|_{x_n=0}.
$$

> Both $g$ and $h$ have only $n-1$ variables, so by the induction hypothesis each is expressible with $\{\wedge,\vee,\neg\}$. The displayed formula combines them using only $\wedge,\vee,\neg$, so $f$ is expressible too. By induction the claim holds for all $n$. $\blacksquare$

Iterating the expansion on *every* variable, and dropping the branches whose cofactor is the constant $0$, produces exactly the **sum of minterms** (the CDNF of §5.5); Theorem 5.3 is the reason a truth table can always be turned into a formula. From this one result, the smaller bases follow immediately.

> **Theorem 5.4 ($\{\wedge,\neg\}$ and $\{\vee,\neg\}$ are complete).**
>
> *Proof.* By Theorem 5.3 it suffices to rebuild the missing operator. De Morgan gives
>

$$
A\vee B=\overline{\overline{A}\wedge\overline{B}},
$$

> so every $\vee$ in a $\{\wedge,\vee,\neg\}$-formula can be rewritten with $\wedge,\neg$; hence $\{\wedge,\neg\}$ is complete. Dually,
>

$$
A\wedge B=\overline{\overline{A}\vee\overline{B}}
$$

> shows $\{\vee,\neg\}$ is complete. $\blacksquare$

Negation is doing essential work in every one of these bases. Remove it and completeness collapses.

> **Theorem 5.5 ($\{\wedge,\vee\}$ is *not* complete).**
>
> *Proof.* Order the inputs pointwise: for $a,b\in\{0,1\}^n$ write $a\le b$ iff $a_i\le b_i$ for every $i$. Call $f$ **monotone** if $a\le b\Rightarrow f(a)\le f(b)$. We show every formula built from $\wedge,\vee$ (and variables) is monotone, by structural induction:
> - a single variable $x_i$ is monotone, since $a\le b\Rightarrow a_i\le b_i$;
> - if $g,h$ are monotone and $a\le b$, then $g(a)\le g(b)$ and $h(a)\le h(b)$; because $\wedge$ and $\vee$ are nondecreasing in each argument, $g(a)\wedge h(a)\le g(b)\wedge h(b)$ and likewise for $\vee$. So $g\wedge h$ and $g\vee h$ are monotone.
>
> But negation is **not** monotone: $0\le 1$ yet $\overline{0}=1 > 0=\overline{1}$. A non-monotone function therefore cannot equal any $\{\wedge,\vee\}$-formula, so the set is incomplete. $\blacksquare$

> **Common pitfall.** Adding the constants does *not* rescue $\{\wedge,\vee\}$: the functions $0$ and $1$ are themselves monotone, and monotone functions are closed under $\wedge,\vee$, so $\{\wedge,\vee,0,1\}$ still produces only monotone functions and remains incomplete. It is specifically the ability to *invert* that is missing.

### The single-operator bases

Remarkably, one operator can be enough. This is the theoretical justification for building entire chips from a single gate type.

> **Theorem 5.6 (NAND is complete).** The Sheffer stroke $A\uparrow B=\overline{A\wedge B}$ alone is functionally complete, via
>

$$
\boxed{\ \overline{A}=A\uparrow A,\qquad A\wedge B=(A\uparrow B)\uparrow(A\uparrow B),\qquad A\vee B=(A\uparrow A)\uparrow(B\uparrow B).\ }
$$

>
> *Proof.* We verify each identity, then invoke Theorem 5.3.
> - $A\uparrow A=\overline{A\wedge A}=\overline{A}$ (idempotence $A\wedge A=A$).
> - $(A\uparrow B)\uparrow(A\uparrow B)=\overline{(A\uparrow B)\wedge(A\uparrow B)}=\overline{A\uparrow B}=\overline{\overline{A\wedge B}}=A\wedge B$ (double negation).
> - Using $A\uparrow A=\overline A$ and $B\uparrow B=\overline B$: $(A\uparrow A)\uparrow(B\uparrow B)=\overline A\uparrow\overline B=\overline{\overline A\wedge\overline B}=A\vee B$ (De Morgan).
>
> Thus $\neg,\wedge,\vee$ are each expressible with $\uparrow$ alone. Since $\{\wedge,\vee,\neg\}$ is complete (Theorem 5.3), so is $\{\uparrow\}$. $\blacksquare$

> **Theorem 5.7 (NOR is complete).** The Peirce arrow $A\downarrow B=\overline{A\vee B}$ alone is functionally complete, via
>

$$
\boxed{\ \overline{A}=A\downarrow A,\qquad A\vee B=(A\downarrow B)\downarrow(A\downarrow B),\qquad A\wedge B=(A\downarrow A)\downarrow(B\downarrow B).\ }
$$

>
> *Proof.* Dual to Theorem 5.6. $A\downarrow A=\overline{A\vee A}=\overline{A}$; $(A\downarrow B)\downarrow(A\downarrow B)=\overline{A\downarrow B}=A\vee B$; and $(A\downarrow A)\downarrow(B\downarrow B)=\overline A\downarrow\overline B=\overline{\overline A\vee\overline B}=A\wedge B$. Each of $\neg,\vee,\wedge$ reduces to $\downarrow$, so $\{\downarrow\}$ is complete. $\blacksquare$

> **Common pitfall.** NAND and NOR are **not associative**. For instance $(A\uparrow B)\uparrow C \ne A\uparrow(B\uparrow C)$: taking $A=1,B=0,C=0$ gives $(1\uparrow0)\uparrow0=1\uparrow0=1$ on the left but $1\uparrow(0\uparrow0)=1\uparrow1=0$ on the right. So a chain like $A\uparrow B\uparrow C$ is *ambiguous*; always parenthesise, and never assume $A\uparrow B\uparrow C$ means $\overline{ABC}$ (it does not — a $3$-input NAND is a different gate).

> **Remark (Post's theorem — the complete picture).** Emil Post (1941) classified *all* complete sets. A set of Boolean functions is complete **iff** it is not entirely contained in any of the five maximal "clones":
> $T_0$ (functions with $f(0,\dots,0)=0$), $T_1$ ($f(1,\dots,1)=1$), $M$ (monotone), $S$ (self-dual: $f(\overline{x_1},\dots)=\overline{f(x_1,\dots)}$), and $L$ (affine/linear: $f = x_{i_1}\oplus\cdots\oplus x_{i_k}\oplus c$).
> This gives a slick alternative completeness check for NAND: $A\uparrow B$ has $\uparrow(0,0)=1\ (\notin T_0)$, $\uparrow(1,1)=0\ (\notin T_1)$, is non-monotone ($\notin M$), is not self-dual (e.g. $\uparrow(1,0)=1\ne\overline{\uparrow(0,1)}=\overline1=0$), and equals $1\oplus xy$ which is nonlinear ($\notin L$). Lying outside all five classes, $\{\uparrow\}$ is complete — matching Theorem 5.6. NOR fails all five identically.

---

## 5.4 Logic gates and circuits

A **logic gate** is a physical device — today a transistor circuit inside an integrated circuit (IC) — that computes one Boolean operation on its input voltages, interpreting "high" as $1$ and "low" as $0$. Gates are the atoms of digital hardware; the abstract algebra of §§5.1–5.3 is exactly the mathematics of what these devices compute. The standard gates, with representative single-gate IC part numbers, are:

| Gate | Function | Symbol shape | Example IC |
|---|---|---|---|
| AND | $A\wedge B$ | flat back, round front | SN74LVC1G08-Q1 |
| OR | $A\vee B$ | curved back, pointed front | SN74LVC1G32-Q1 |
| NOT (inverter) | $\overline{A}$ | triangle + bubble | 7404 |
| NAND | $\overline{A\wedge B}$ | AND + bubble | SN74AHC1G00 |
| NOR | $\overline{A\vee B}$ | OR + bubble | SN74AHC1G02 |
| XOR | $A\oplus B$ | OR + extra back curve | SN74LVC1G86 |

The **bubble** on a gate symbol always denotes negation, which is why NAND is drawn as AND-with-a-bubble and NOR as OR-with-a-bubble — the pictures encode Theorems 5.6–5.7 visually. Real parts implement these operations directly; larger devices pack many gates to realise a whole function. For example the **CY54FCT480T** is a dual $8$-bit parity generator/checker — internally a tree of XOR gates, because the parity of a bit-vector is exactly the XOR of all its bits (XOR is associative, so the tree is well defined).

![Standard logic-gate symbols: NOT, AND, NAND, OR, and XOR](img/l05_gates.png)

### Building a circuit from a Boolean expression

A formula translates mechanically into a gate network: each operator becomes a gate, each variable becomes an input wire, and the wiring follows the nesting of the expression. Complemented inputs are produced by inverters. A **sum-of-products** (SOP / DNF) formula reads left-to-right as a *two-level* circuit — a layer of AND gates whose outputs feed a single OR gate — with inverters supplying any complemented literals. Dually, a **product-of-sums** (POS / CNF) is a layer of ORs feeding one AND.

Take the minimized function $F=\overline{B}\vee(A\wedge C)$ (derived in §5.7):

- an inverter produces $\overline{B}$ from $B$;
- a $2$-input AND gate produces $A\wedge C$ from $A,C$;
- a $2$-input OR gate combines $\overline{B}$ and $A\wedge C$ into $F$.

Gate count: $1$ NOT $+\ 1$ AND $+\ 1$ OR $=\ 3$ gates.

### Everything as NAND (or as NOR)

Because $\{\uparrow\}$ is complete, any two-level AND–OR circuit can be redrawn as an all-NAND network with the *same shape*. The trick: insert two bubbles (a double negation, hence no change in value) on each wire between the AND layer and the OR layer. The AND gates gain an output bubble and become NANDs; the OR gate gains input bubbles and, by De Morgan ($\overline{X}\vee\overline{Y}=\overline{X\wedge Y}$... read the other way, an OR with inverted inputs *is* a NAND), also becomes a NAND. So:

$$
F=\overline{B}\vee AC \;=\; \overline{\,\overline{\overline B}\wedge \overline{AC}\,}\;=\; \bigl(\,\underbrace{B\uparrow B}_{\overline B}\,\bigr)\uparrow\bigl(\,\underbrace{A\uparrow_{\!*} C}_{\text{AND via NAND}}\,\bigr)\ \text{-style network,}
$$

i.e. **AND-then-OR becomes NAND-then-NAND**. This is convenient because a board may already carry a NAND package, and because in CMOS a NAND is cheaper than an AND (see §5.9). The takeaway for the rest of the lecture: *minimize the algebra first*, because every literal and every term you eliminate is gates, transistors, area, delay, and power you never build.

---

## 5.5 Canonical normal forms

Minimization needs a well-defined starting point and a way to compare functions. Both are provided by the **canonical normal forms**: standard expressions built directly from the truth table, one for each function, *unique*. They are the rigorous bridge between a table and a formula. The two forms below — **CDNF** and **CCNF** — are also called the **canonical DNF** and **canonical CNF** (the names used in Lecture 6 and Practical 4), or the *perfect/complete* DNF/CNF; all these names denote the same sum-of-minterms / product-of-maxterms.

- A **literal** is a variable or its complement ($A$ or $\overline{A}$).
- A **minterm** in variables $x_1,\dots,x_n$ is a product (AND) of $n$ literals, one per variable. Given a point $a=(a_1,\dots,a_n)\in\{0,1\}^n$, its minterm is $m_a=\bigwedge_{i} x_i^{a_i}$, where $x_i^{1}=x_i$ and $x_i^{0}=\overline{x_i}$.
- A **maxterm** is a sum (OR) of $n$ literals, one per variable. The maxterm of $a$ is $M_a=\bigvee_i x_i^{\,1-a_i}$ (a variable appears *complemented* where $a_i=1$ and *direct* where $a_i=0$ — the mirror of the minterm rule).

The whole theory rests on one lemma: each minterm switches on exactly one row, each maxterm switches off exactly one row.

> **Lemma 5.8 (Indicator property).** For all $a,b\in\{0,1\}^n$: $\ m_a(b)=1\iff b=a$, and $\ M_a(b)=0\iff b=a$.
>
> *Proof.* Evaluate the literal $x_i^{a_i}$ at $b$: if $a_i=1$ it is $b_i$; if $a_i=0$ it is $\overline{b_i}$. Either way the literal equals $1$ **iff** $b_i=a_i$. The minterm $m_a(b)$ is the AND of all $n$ literals, so it is $1$ iff *every* literal is $1$, i.e. iff $b_i=a_i$ for all $i$, i.e. iff $b=a$.
> Dually, in $M_a$ the literal $x_i^{\,1-a_i}$ evaluated at $b$ equals $1$ iff $b_i\ne a_i$; the maxterm is the OR of these, so $M_a(b)=0$ iff *every* literal is $0$, i.e. iff $b_i=a_i$ for all $i$, i.e. iff $b=a$. $\blacksquare$

> **Corollary 5.9 (Minterms partition the cube).** There are exactly $2^n$ minterms, and every input $b\in\{0,1\}^n$ satisfies exactly one of them (namely $m_b$). The minterms are the "indicator functions" of the single points.

We use one running example, $F(A,B,C)$:

| $A$ | $B$ | $C$ | $F$ | row \# |
|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 0 |
| 0 | 0 | 1 | 1 | 1 |
| 0 | 1 | 0 | 0 | 2 |
| 0 | 1 | 1 | 0 | 3 |
| 1 | 0 | 0 | 1 | 4 |
| 1 | 0 | 1 | 1 | 5 |
| 1 | 1 | 0 | 0 | 6 |
| 1 | 1 | 1 | 1 | 7 |

### Canonical disjunctive normal form (CDNF)

**CDNF (perfect DNF, sum of minterms).** The OR of one minterm for every row where $F=1$.

> **Theorem 5.10 (Existence and uniqueness of the CDNF).** Every Boolean function $f\not\equiv 0$ equals the disjunction of the minterms of its $1$-rows,
>

$$
f=\bigvee_{a:\,f(a)=1} m_a,
$$

> and this is the *only* way to write $f$ as a disjunction of distinct minterms.
>
> *Proof.* **Existence.** Let $g=\bigvee_{a:\,f(a)=1} m_a$ (a nonempty OR since $f\not\equiv0$). For any $b$, by Lemma 5.8 the term $m_b$ contributes iff $f(b)=1$, and every other minterm is $0$ at $b$. Hence $g(b)=1\iff f(b)=1$, so $g=f$.
> **Uniqueness.** Suppose $f=\bigvee_{a\in S}m_a$ for some set $S$ of minterms. Evaluate at any $b$: by Lemma 5.8 the only term that can be nonzero at $b$ is $m_b$, and it appears iff $b\in S$. So $f(b)=1\iff b\in S$. Therefore $S=\{b:f(b)=1\}$ is forced — the set of minterms is uniquely determined by $f$. $\blacksquare$

For our $F$ the $1$-rows are $000,001,100,101,111$ (rows $0,1,4,5,7$), giving

$$
F=\overline{A}\,\overline{B}\,\overline{C}\ \vee\ \overline{A}\,\overline{B}C\ \vee\ A\overline{B}\,\overline{C}\ \vee\ A\overline{B}C\ \vee\ ABC.
$$

Indexing minterms by the decimal value of their row, this is written compactly as $F=\textstyle\sum m(0,1,4,5,7)$.

### Canonical conjunctive normal form (CCNF)

**CCNF (perfect CNF, product of maxterms).** The AND of one maxterm for every row where $F=0$.

> **Theorem 5.11 (Existence and uniqueness of the CCNF).** Every Boolean function $f\not\equiv 1$ equals
>

$$
f=\bigwedge_{a:\,f(a)=0} M_a,
$$

> and this is the only representation of $f$ as a product of distinct maxterms.
>
> *Proof.* **Existence.** Let $h=\bigwedge_{a:\,f(a)=0}M_a$. By Lemma 5.8, $M_a(b)=0$ exactly when $b=a$; so $h(b)=0$ iff some maxterm with $f(a)=0$ has $b=a$, i.e. iff $f(b)=0$. Hence $h=f$.
> **Uniqueness.** If $f=\bigwedge_{a\in T}M_a$, then evaluating at $b$ the only factor that can be $0$ is $M_b$, present iff $b\in T$; so $f(b)=0\iff b\in T$, forcing $T=\{b:f(b)=0\}$. $\blacksquare$
>
> *(Equivalently, the CCNF of $f$ is obtained from the CDNF of $\overline f$ by De Morgan — a one-line derivation once Theorem 5.10 is in hand.)*

For our $F$ the $0$-rows are $010,011,110$ (rows $2,3,6$), giving maxterms $(A\vee\overline{B}\vee C)$, $(A\vee\overline{B}\vee\overline{C})$, $(\overline{A}\vee\overline{B}\vee C)$, so

$$
F=(A\vee\overline{B}\vee C)(A\vee\overline{B}\vee\overline{C})(\overline{A}\vee\overline{B}\vee C)=\textstyle\prod M(2,3,6).
$$

> **Remark (which form is cheaper).** The rows split cleanly: the CDNF uses the $1$-rows, the CCNF uses the $0$-rows, and $\{1\text{-rows}\}\cup\{0\text{-rows}\}$ is all $2^n$ rows. So $\#(\text{minterms})+\#(\text{maxterms})=2^n$. A function that is mostly $1$ has a long CDNF and a short CCNF, and vice versa — expand around whichever output value is rarer. For our $F$: $5$ minterms vs $3$ maxterms, so the CCNF is the smaller canonical form.

> **Common pitfall.** The minterm and maxterm polarities are *opposite*. For a $1$-row, a variable equal to $1$ appears **uncomplemented** in the minterm; for a $0$-row, a variable equal to $1$ appears **complemented** in the maxterm. Getting this backwards is the single most common error in building canonical forms — re-derive it from Lemma 5.8 if in doubt, rather than memorising.

### Algebraic normal form (Zhegalkin polynomial)

A third canonical form uses **XOR** instead of OR. Since $\{\wedge,\oplus,1\}$ is
functionally complete, every Boolean function has a **unique algebraic normal form
(ANF)** — a XOR of distinct AND-terms, possibly including the constant $1$:
$$f=c_0\ \oplus\ c_1x_1\oplus\cdots\oplus c_nx_n\ \oplus\ c_{12}x_1x_2\oplus\cdots\ \oplus\ c_{1\ldots n}x_1\cdots x_n,\qquad c_i\in\{0,1\}.$$
There are $2^{2^n}$ Boolean functions of $n$ variables and exactly $2^{2^n}$ coefficient
vectors — one bit per subset of the variables — and distinct vectors compute distinct
functions, so the correspondence is a **bijection**: every function has exactly one ANF.
Equivalently $f$ is a polynomial over the two-element field $\mathbb F_2$ — the
**Zhegalkin polynomial**. Convert any formula to ANF by substituting
$\overline a=a\oplus 1$ and $a\vee b=a\oplus b\oplus ab$, then simplifying with
$a\oplus a=0$ and $aa=a$. The ANF is the natural form for parity and checksums, and a
function is **affine** (linear) exactly when its ANF has degree $\le 1$ — the class $L$
of Post's theorem (§5.3).

*(De Morgan generalises to any arity, used implicitly when reading a CCNF:
$\overline{x_1\wedge\cdots\wedge x_n}=\overline{x_1}\vee\cdots\vee\overline{x_n}$ and,
dually, $\overline{x_1\vee\cdots\vee x_n}=\overline{x_1}\wedge\cdots\wedge\overline{x_n}$.)*

## 5.6 Algebraic minimization

The canonical forms are unique but usually far from minimal. **Algebraic minimization** applies the identities of Lecture 4 to shrink a formula while preserving its truth table. The workhorses are:

| Law | Statement |
|---|---|
| Idempotence | $A\vee A=A$, $\ A\wedge A=A$ |
| Complement | $A\vee\overline A=1$, $\ A\wedge\overline A=0$ |
| Absorption | $A\vee AB=A$, $\ A(A\vee B)=A$ |
| Absorption (2nd form) | $\overline{A}\vee AB=\overline{A}\vee B$ |
| Combining / "expand by $1$" | $AB\vee A\overline B=A$; and $P=P\wedge(A\vee\overline A)$ |
| De Morgan | $\overline{A\vee B}=\overline A\,\overline B$, $\ \overline{A\wedge B}=\overline A\vee\overline B$ |
| Consensus | $AB\vee\overline A C\vee BC=AB\vee\overline A C$ |

The **combining law** $AB\vee A\overline B=A$ is the algebraic heart of every method in this lecture: two product terms that agree everywhere except in one variable, where they disagree, merge into one shorter term. Karnaugh maps and Quine–McCluskey are just disciplined, exhaustive ways of finding every legal application of this one law.

**Quick example (combining + absorption).**

$$
XY\vee X\overline Y\vee \overline X Y \;=\; X(Y\vee\overline Y)\vee\overline X Y \;=\; X\vee\overline X Y \;=\; X\vee Y.
$$

The last step is the second absorption form $\overline X\vee XY$... read as $X\vee\overline X Y=X\vee Y$. Three product terms collapse to a single OR.

**Consensus example.** In $XY\vee\overline X Z\vee YZ$, the term $YZ$ is the *consensus* of $XY$ and $\overline X Z$ (formed by cancelling the opposed variable $X$). It is redundant:

$$
YZ=YZ(X\vee\overline X)=XYZ\vee\overline X YZ,\quad XYZ\le XY,\ \ \overline X YZ\le\overline X Z,
$$

so $YZ\le XY\vee\overline X Z$ and $XY\vee\overline X Z\vee YZ=XY\vee\overline X Z$. Spotting redundant consensus terms is exactly what "don't add a group you don't need" means on a Karnaugh map.

**Worked example (full derivation).** Simplify

$$
F=\overline{(x\vee\overline{y})}\ \vee\ \bigl((\overline{y}\vee\overline{z})\vee \overline{x}\,z\bigr).
$$

| Step | Expression | Justification |
|---|---|---|
| 1 | $\overline{(x\vee\overline{y})}\vee\bigl((\overline{y}\vee\overline{z})\vee\overline{x}z\bigr)$ | given |
| 2 | $(\overline{x}\wedge\overline{\overline{y}})\vee(\overline{y}\vee\overline{z}\vee\overline{x}z)$ | De Morgan on first term; drop inner parentheses |
| 3 | $\overline{x}y\vee\overline{y}\vee\overline{z}\vee\overline{x}z$ | double negation $\overline{\overline{y}}=y$ |
| 4 | $\overline{x}y\vee\overline{x}z\vee\overline{y}(x\vee\overline{x})\vee\overline{z}(x\vee\overline{x})$ | reorder; multiply $\overline{y},\overline{z}$ by $(x\vee\overline{x})=1$ |
| 5 | $\overline{x}y\vee\overline{x}z\vee x\overline{y}\vee\overline{x}\,\overline{y}\vee x\overline{z}\vee\overline{x}\,\overline{z}$ | distribute |
| 6 | $\overline{x}(y\vee\overline{y})\vee\overline{x}(z\vee\overline{z})\vee x\overline{y}\vee x\overline{z}$ | group $\overline{x}y$ with $\overline{x}\,\overline{y}$, and $\overline{x}z$ with $\overline{x}\,\overline{z}$ |
| 7 | $\overline{x}\vee\overline{x}\vee x\overline{y}\vee x\overline{z}$ | complement law $y\vee\overline{y}=1$ |
| 8 | $\overline{x}\vee x(\overline{y}\vee\overline{z})$ | idempotence $\overline{x}\vee\overline{x}=\overline{x}$; factor $x$ |
| 9 | $\overline{x}\vee(\overline{y}\vee\overline{z})$ | absorption (2nd form) $\overline{x}\vee x W=\overline{x}\vee W$ with $W=\overline y\vee\overline z$ |
| 10 | $\overline{x}\vee\overline{y}\vee\overline{z}$ | drop parentheses |

So $F=\overline{x}\vee\overline{y}\vee\overline{z}=\overline{xyz}$.

> **Remark (the deck's longer route).** The original lecture reached the same answer from step 8 via a chain of De Morgan rewrites: $\overline x\vee x(\overline y\vee\overline z)=\overline{\,x\wedge\overline{x(\overline y\vee\overline z)}\,}=\overline{\,x\wedge(\overline x\vee yz)\,}=\overline{\,x\overline x\vee xyz\,}=\overline{xyz}=\overline x\vee\overline y\vee\overline z$. It is correct but longer; recognising the absorption law (step 9 above) collapses six lines into one. This is exactly why we want *systematic* methods — algebraic skill varies, and there is no guarantee you spotted the shortest path.

**Truth-table check.** Building both sides column by column confirms equality (they differ from $1$ only where every variable is $1$):

| $x$ | $y$ | $z$ | $\overline{(x\vee\overline{y})}$ | $\overline{y}\vee\overline{z}$ | $\overline{x}z$ | $F$ (original) | $\overline{xyz}$ |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 | 0 | 1 | 1 |
| 0 | 0 | 1 | 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 | 0 | 1 | 1 |
| 0 | 1 | 1 | 1 | 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 1 | 0 | 1 | 1 |
| 1 | 0 | 1 | 0 | 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 | 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 |

Algebraic minimization always works, but it gives no guarantee of reaching the smallest form and offers no stopping rule — you can never be sure you are done. This motivates the systematic methods that follow, which *do* find provably minimal two-level forms.

---

## 5.7 Karnaugh maps

A **Karnaugh map (K-map)** is a truth table redrawn as a grid whose rows and columns are labelled in **Gray-code** order $00,01,11,10$ — successive labels (including the wrap from the last back to the first) differ in exactly one bit. This labelling is the whole point of the map.

> **Proposition 5.12 (Adjacency = one-variable change).** With Gray-code labels, two cells sharing an edge — or lying at opposite ends of the same row or column (wrap-around) — represent inputs that differ in exactly one variable.
>
> *Proof sketch.* A horizontal move changes only the column label by one Gray-code step, which flips exactly one of the column variables and leaves the row variables (and all other column variables) fixed; a vertical move does the same for the row variables. Gray code is *cyclic* — for two bits, $10\to00$ also differs in one bit — so the first and last positions are one step apart too, justifying wrap-around. $\blacksquare$

By the combining law, two adjacent $1$-cells differing in variable $v$ merge: $(\text{rest})\,v\ \vee\ (\text{rest})\,\overline v=(\text{rest})$. Iterating, a block of $2^k$ cells that forms a *subcube* — $k$ chosen variables run through all their combinations while the remaining $n-k$ stay constant — collapses to the single product term of those $n-k$ constant literals.

![Grouping adjacent 1-cells of a three-variable Karnaugh map into subcubes](img/l05_kmap3.png)

> **Theorem 5.13 (K-map grouping).** A group of $2^k$ cells forming a subcube corresponds to the product term $p$ of its $n-k$ constant literals (each constant-$1$ variable direct, each constant-$0$ variable complemented). This $p$ is an **implicant** of $f$ (i.e. $p\le f$, meaning $p=1\Rightarrow f=1$) **iff** all $2^k$ cells hold $1$.
>
> *Proof.* By construction $p=1$ exactly on the $2^k$ cells of the subcube (the free variables are unconstrained, the constant literals pin the rest). Then $p\le f$ iff $f=1$ at every point where $p=1$, i.e. iff all those cells are $1$. The size is a power of two because $k$ binary variables range over $2^k$ combinations. $\blacksquare$

So *grouping $1$s into the largest legal subcubes* directly reads off short product terms. We formalise the vocabulary:

- An **implicant** is a product term $p$ with $p\le f$.
- A **prime implicant (PI)** is an implicant from which no literal can be deleted while remaining an implicant — on the map, a group that cannot be enlarged (doubled) and stay all-$1$.
- An **essential prime implicant** is a PI that covers at least one $1$-cell covered by no other PI.

A minimal SOP is a smallest set of prime implicants that covers every $1$; it must contain every essential PI, and then a cheapest choice of remaining PIs to cover what is left.

Template layouts (cells left blank):

Two variables — rows $x$, columns $y$:

| $x\backslash y$ | 0 | 1 |
|---|---|---|
| **0** |  |  |
| **1** |  |  |

Three variables — rows $x$, columns $yz$ in Gray order:

| $x\backslash yz$ | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| **0** |  |  |  |  |
| **1** |  |  |  |  |

Four variables — rows $xy$, columns $zt$, both in Gray order:

| $xy\backslash zt$ | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| **00** |  |  |  |  |
| **01** |  |  |  |  |
| **11** |  |  |  |  |
| **10** |  |  |  |  |

> **Common pitfall.** Do **not** label the axes $00,01,10,11$ (plain binary). Between $01$ and $10$ *two* bits change, so plain-binary neighbours are not logically adjacent and the combining law fails. The Gray order $00,01,11,10$ is mandatory. Likewise, groups must be rectangles of size a power of two ($1,2,4,8,\dots$); an "L-shape" or a $3$-cell group is illegal.

![A four-variable Karnaugh map with two valid 2×2 groups of 1-cells](img/l05_kmap4.png)

### Worked example 1 — a three-variable minimal DNF

Take the running $F(A,B,C)=\sum m(0,1,4,5,7)$. Rows $A$, columns $BC$:

| $A\backslash BC$ | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| **0** | 1 | 1 | 0 | 0 |
| **1** | 1 | 1 | 1 | 0 |

- The left half (columns $BC=00,01$, both rows) is four adjacent $1$s where only $B=0$ is constant $\Rightarrow \overline{B}$. This is a prime implicant, and it is **essential** (it is the only cover of the cells at $BC=00$).
- The two $1$s at $(A{=}1,BC{=}01)$ and $(A{=}1,BC{=}11)$ share $A=1,C=1$ $\Rightarrow AC$. Essential, because the cell $(A{=}1,BC{=}11)$ (minterm $7$) lies in no other group.

Together they cover every $1$ (the cell $A{=}1,BC{=}01$ is shared, which is allowed), giving the **minimal DNF**

$$
F=\overline{B}\vee AC.
$$

This is dramatically smaller than the five-minterm CDNF and is exactly the expression whose $3$-gate circuit was drawn in §5.4.

### Worked example 2 — wrap-around

Let $F(A,B,C)=\sum m(0,2,4,6)$ (all even rows). Rows $A$, columns $BC$:

| $A\backslash BC$ | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| **0** | 1 | 0 | 0 | 1 |
| **1** | 1 | 0 | 0 | 1 |

The four $1$s sit in columns $BC=00$ and $BC=10$ — the **first and last columns**, which are wrap-around adjacent. All four share $C=0$, so they form one legal group of size $4$:

$$
F=\overline{C}.
$$

Without wrap-around one would wrongly split this into two size-$2$ groups $\overline A\,\overline C+A\overline C$ and then have to combine them algebraically. Wrap-around lets the map find the largest group directly.

### Worked example 3 — a four-variable minimal DNF

Consider $F(x,y,z,t)$ given by the eight minterms

$$
xyz\overline{t}\vee x\overline{y}zt\vee\overline{x}yzt\vee\overline{x}\,\overline{y}zt\vee x\overline{y}\,\overline{z}t\vee\overline{x}\,\overline{y}\,\overline{z}t\vee x\overline{y}\,\overline{z}\,\overline{t}\vee\overline{x}\,\overline{y}\,\overline{z}\,\overline{t}.
$$

Plotting each minterm (rows $xy$, columns $zt$):

| $xy\backslash zt$ | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| **00** | 1 | 1 | 1 | 0 |
| **01** | 0 | 0 | 1 | 0 |
| **11** | 0 | 0 | 0 | 1 |
| **10** | 1 | 1 | 1 | 0 |

Grouping the $1$s into largest subcubes:

- Rows $xy=00$ and $xy=10$ (wrap-adjacent, both have $y=0$) $\times$ columns $zt=00,01$ ($z=0$): a $2\times2$ block $\Rightarrow \overline{y}\,\overline{z}$.
- The same two rows ($y=0$) $\times$ columns $zt=01,11$ ($t=1$): a $2\times2$ block $\Rightarrow \overline{y}t$.
- Column $zt=11$, rows $xy=00,01$ ($x=0$): a vertical pair $\Rightarrow \overline{x}zt$. (Essential — it is the only cover of the cell $(xy{=}01,zt{=}11)$.)
- The isolated cell $xy=11,zt=10$ cannot be enlarged (all four neighbours are $0$), so it stays a full minterm $\Rightarrow xyz\overline{t}$ (essential).

$$
F_{\min}=\overline{y}\,\overline{z}\ \vee\ \overline{y}t\ \vee\ \overline{x}zt\ \vee\ xyz\overline{t}.
$$

### Reading a minimal CNF (group the 0s)

For a minimal CNF, group the **zeros** and read each block as a maxterm — keep the variables constant over the block, complemented where the variable is $1$ and direct where it is $0$ (Theorem 5.13 with the polarity flipped, because a group of $0$s is a prime implicant of $\overline F$). The zeros of the same four-variable map:

| $xy\backslash zt$ | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| **00** | . | . | . | 0 |
| **01** | 0 | 0 | . | 0 |
| **11** | 0 | 0 | 0 | . |
| **10** | . | . | . | 0 |

Grouping the $0$s:

- Rows $xy=01,11$ ($y=1$) $\times$ columns $zt=00,01$ ($z=0$): $2\times2$ block, constants $y=1,z=0 \Rightarrow (\overline{y}\vee z)$.
- Row $xy=11$ ($x=1,y=1$) $\times$ columns $zt=01,11$ ($t=1$): pair $\Rightarrow (\overline{x}\vee\overline{y}\vee\overline{t})$.
- Column $zt=10$ ($z=1,t=0$), rows $xy=00,01$ ($x=0$): pair $\Rightarrow (x\vee\overline{z}\vee t)$.
- Column $zt=10$ ($z=1,t=0$), rows $xy=00,10$ ($y=0$): pair $\Rightarrow (y\vee\overline{z}\vee t)$.

$$
F_{\min}=(\overline{y}\vee z)(\overline{x}\vee\overline{y}\vee\overline{t})(x\vee\overline{z}\vee t)(y\vee\overline{z}\vee t).
$$

Both readings describe the same function; the DNF form is cheaper when $1$s cluster, the CNF form when $0$s cluster.

### Don't-care conditions

Often some input combinations *cannot occur* (e.g. the six bit-patterns $1010$–$1111$ that are not valid BCD digits) or their output is simply irrelevant. Such rows are **don't-cares**, written $\times$ (or $d$). A don't-care may be treated as $1$ **or** $0$, chosen independently for each group, whichever makes the groups larger. You must still *cover every real $1$*, but you never have to cover a $\times$.

![A Karnaugh map with a don't-care cell (×) absorbed into a group to enlarge it](img/l05_kmap_dc.png)

**Worked example 4 — BCD "digit $\ge 5$" with don't-cares.** Inputs $A,B,C,D$ encode a decimal digit $8A+4B+2C+D$; patterns $10$–$15$ are invalid, hence don't-cares. $F=1$ iff the digit is $\ge5$, i.e. minterms $\{5,6,7,8,9\}$, with $d\{10,11,12,13,14,15\}$.

| $AB\backslash CD$ | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| **00** | 0 | 0 | 0 | 0 |
| **01** | 0 | 1 | 1 | 1 |
| **11** | $\times$ | $\times$ | $\times$ | $\times$ |
| **10** | 1 | 1 | $\times$ | $\times$ |

Using don't-cares as $1$ where helpful:

- The whole bottom half $A=1$ (rows $11,10$) can all be $1$ (real $1$s at $8,9$; the rest are $\times$): a group of $8$ $\Rightarrow A$.
- Rows $01,11$ ($B=1$) $\times$ columns $01,11$ ($D=1$): $2\times2$ $\Rightarrow BD$ (covers $5,7$; uses $\times$ at $13,15$).
- Rows $01,11$ ($B=1$) $\times$ columns $11,10$ ($C=1$): $2\times2$ $\Rightarrow BC$ (covers $6,7$; uses $\times$ at $14,15$).

$$
F_{\min}=A\vee BC\vee BD\qquad(3\text{ terms},\ 5\text{ literals}).
$$

Had we forced every don't-care to $0$, the same function would minimize to

$$
F=\overline A B C\vee\overline A B D\vee A\overline B\,\overline C\qquad(3\text{ terms},\ 9\text{ literals}),
$$

noticeably more expensive. Exploiting don't-cares is one of the biggest practical wins in logic synthesis.

> **Remark.** A don't-care is included in a group only if doing so *helps*; it is never obligatory. Different groups may make opposite assumptions about the same $\times$ cell — that is fine, because each group is an independent implicant and we only require that the real $1$s are covered and no real $0$ is.

**Practical rules for K-maps.**

- Groups must be rectangular and of size a power of two; wrap-around across all four edges (and the four corners) is allowed.
- Use the *largest* legal groups (bigger group $=$ fewer literals) and the *fewest* groups that still cover every target cell.
- Identify **essential** prime implicants first (a $1$ that only one group can cover forces that group in), then cover the rest as cheaply as possible.
- Groups may overlap; every $1$ (for DNF) or every $0$ (for CNF) must lie in at least one group. Don't-cares may be covered or not, freely.
- K-maps stay readable up to about $4$–$5$ variables; beyond that, use the tabular Quine–McCluskey method.

> **Common pitfall.** "Take the largest group first, greedily" does *not* always give a minimal cover. When no prime implicant is essential (a *cyclic* chart, see Exercise C3) you must compare competing covers. The map is a visual aid for the *reasoning*, not a substitute for it.

---

## 5.8 The Quine–McCluskey algorithm

Karnaugh maps rely on human pattern-recognition and break down past five variables. The **Quine–McCluskey (QM) algorithm** (Willard Quine 1952–55, Edward McCluskey 1956) is a fully mechanical procedure that finds *all* prime implicants and then a minimal cover — it is essentially "the K-map as a table," suitable for a computer. It has two phases.

**Phase 1 — find all prime implicants by repeated combining.**

1. List all minterms (and don't-cares) as binary strings; group them by their number of $1$s.
2. Compare every string in each group with every string in the next group. If two differ in exactly one bit position, they combine: write a new term with a dash `–` in that position, and tick $(\checkmark)$ both parents as "used."
3. Repeat on the newly formed terms (matching requires the *same* dash positions and a one-bit difference elsewhere), producing size-$4$, then size-$8$ terms, etc., until no more combining is possible.
4. Every term never ticked (never absorbed into a larger one) is a **prime implicant**.

![Quine–McCluskey Phase 1: minterms grouped by their number of 1-bits](img/l05_quine.png)

**Phase 2 — choose a minimal cover with a prime-implicant chart.**

5. Build a chart: rows = prime implicants, columns = the original minterms (don't-cares are *not* required to be covered, so they get no column). Mark which PI covers which minterm.
6. A column with a single mark forces its PI: that PI is **essential**. Select all essential PIs.
7. Delete covered columns; from the remaining PIs choose a minimum-cost subset covering the leftover minterms (by inspection, or Petrick's method for cyclic charts).

**Fully worked example.** Minimize $F(w,x,y,z)=\sum m(0,1,2,8,10,11,14,15)$.

*Phase 1, round 0* — group by number of $1$s:

| Group ($\#1$s) | Minterm | $wxyz$ |
|---|---|---|
| 0 | 0 | 0000 |
| 1 | 1, 2, 8 | 0001, 0010, 1000 |
| 2 | 10 | 1010 |
| 3 | 11, 14 | 1011, 1110 |
| 4 | 15 | 1111 |

*Round 1* — combine adjacent groups differing in one bit (dash the differing position):

| Term | Pattern | from |
|---|---|---|
| $0,1$ | $000\text{–}$ | $0,1$ |
| $0,2$ | $00\text{–}0$ | $0,2$ |
| $0,8$ | $\text{–}000$ | $0,8$ |
| $2,10$ | $\text{–}010$ | $2,10$ |
| $8,10$ | $10\text{–}0$ | $8,10$ |
| $10,11$ | $101\text{–}$ | $10,11$ |
| $10,14$ | $1\text{–}10$ | $10,14$ |
| $11,15$ | $1\text{–}11$ | $11,15$ |
| $14,15$ | $111\text{–}$ | $14,15$ |

Every original minterm was used at least once (all ticked).

*Round 2* — combine size-$2$ terms sharing a dash position and differing in one bit:

| Term | Pattern | from |
|---|---|---|
| $0,2,8,10$ | $\text{–}0\text{–}0$ | $(0,2)\!+\!(8,10)$ and $(0,8)\!+\!(2,10)$ |
| $10,11,14,15$ | $1\text{–}1\text{–}$ | $(10,11)\!+\!(14,15)$ and $(10,14)\!+\!(11,15)$ |

The term $000\text{–}$ ($=\{0,1\}$) never combines further and remains as is; the size-$4$ terms cannot combine (different dash patterns). **Prime implicants:**

| PI | Pattern | Covers | Product term |
|---|---|---|---|
| $P_1$ | $000\text{–}$ | $0,1$ | $\overline{w}\,\overline{x}\,\overline{y}$ |
| $P_2$ | $1\text{–}1\text{–}$ | $10,11,14,15$ | $wy$ |
| $P_3$ | $\text{–}0\text{–}0$ | $0,2,8,10$ | $\overline{x}\,\overline{z}$ |

*Phase 2* — prime-implicant chart:

| PI \ minterm | 0 | 1 | 2 | 8 | 10 | 11 | 14 | 15 |
|---|---|---|---|---|---|---|---|---|
| $P_1=\overline w\,\overline x\,\overline y$ | $\times$ | $\times$ |  |  |  |  |  |  |
| $P_2=wy$ |  |  |  |  | $\times$ | $\times$ | $\times$ | $\times$ |
| $P_3=\overline x\,\overline z$ | $\times$ |  | $\times$ | $\times$ | $\times$ |  |  |  |

Reading the single-mark columns: minterm $1$ forces $P_1$; minterms $2,8$ force $P_3$; minterms $11,14,15$ force $P_2$. All three PIs are **essential**, and together they cover $\{0,1,2,8,10,11,14,15\}$ — the whole function. Hence

$$
\boxed{\,F=\overline{w}\,\overline{x}\,\overline{y}\ \vee\ wy\ \vee\ \overline{x}\,\overline{z}\,}\qquad(3\text{ terms},\ 7\text{ literals}).
$$

Cross-check on the K-map (rows $wx$, cols $yz$):

| $wx\backslash yz$ | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| **00** | 1 | 1 | 0 | 1 |
| **01** | 0 | 0 | 0 | 0 |
| **11** | 0 | 0 | 1 | 1 |
| **10** | 1 | 0 | 1 | 1 |

$P_3=\overline x\,\overline z$ is the **four corners** ($x=0,z=0$); $P_2=wy$ is the lower-right $2\times2$ ($w=1,y=1$); $P_1=\overline w\,\overline x\,\overline y$ is the pair at the top-left. The tabular method and the map agree, as they must.

> **Remark (cyclic charts and Petrick's method).** Sometimes *no* column has a single mark, so there are no essential PIs and the chart is **cyclic** (see Exercise C3, $F=\sum m(0,1,2,5,6,7)$, where every minterm is covered by exactly two PIs). Then form Petrick's product $P=\prod_{\text{minterm }m}\bigl(\textstyle\sum_{\text{PIs covering }m}\bigr)$, multiply out to SOP using $X+X=X$ and $X+XY=X$, and pick the product term with the fewest (cheapest) PIs. This turns "cover the chart" into a Boolean problem itself.

> **Remark (why QM is not the end of the story).** QM finds a minimal *two-level* SOP, but Phase 2 (the covering problem) is NP-hard in general, so exact QM does not scale to functions with hundreds of variables. Industrial logic synthesis uses the heuristic minimizer **Espresso**, and moves beyond two-level to **multi-level** minimization (factoring common subexpressions across many outputs), which is what actually reduces area in a real chip. QM remains the conceptual foundation and the definition of "minimal SOP."

---

## 5.9 Cost: before vs after minimization

Minimization pays off in three currencies: **gate count**, **transistor count** (area/power), and **delay**. Consider again $F(A,B,C)=\sum m(0,1,4,5,7)$, comparing the raw CDNF against the minimized $\overline B\vee AC$.

A useful reference for static CMOS (the dominant chip technology): an inverter is $2$ transistors; a $k$-input NAND or NOR is $2k$ transistors; a $k$-input AND is a NAND followed by an inverter, $2k+2$ transistors; a $k$-input OR is a NOR plus an inverter, likewise $2k+2$. These figures are approximate but standard, and they explain why NAND/NOR are the "native" gates and AND/OR cost extra.

| Metric | CDNF $\sum m(0,1,4,5,7)$ | Minimized $\overline B\vee AC$ |
|---|---|---|
| Product terms | 5 | 2 |
| Literals | 15 | 3 |
| Inverters (NOT) | 3 (for $\overline A,\overline B,\overline C$) | 1 (for $\overline B$) |
| AND gates | 5 (three-input) | 1 (two-input) |
| OR gates | 1 (five-input) | 1 (two-input) |
| Gate total | 9 | 3 |
| CMOS transistors (approx.) | $3(2)+5(8)+1(12)=58$ | $2+6+6=14$ |
| Logic depth (levels) | 2 (+ inverters) | 2 (+ inverter) |

Minimization cuts the gate count by two thirds and the transistor count roughly fourfold, with no loss of speed (both are two-level). Redrawn as NAND-only (§5.4), the minimized circuit is a handful of NAND gates. Multiply such savings across the millions of instances of a standard cell in a modern design and the motivation for §§5.6–5.8 is clear: **the algebra is the design**, and smaller algebra is a smaller, faster, cooler chip.

> **Remark (delay).** Two-level SOP minimizes logic *depth* (hence delay) at some cost in *width* (many wide gates in parallel). Real gates have limited fan-in, so a $5$-input OR is often built from a tree of $2$-input gates, adding depth. Multi-level synthesis trades depth against area to hit a timing target; two-level minimization is the baseline it starts from.

---

## 5.10 Historical note and connections

**A short history.** The algebra of logic is due to **George Boole** (*The Mathematical Analysis of Logic*, 1847; *An Investigation of the Laws of Thought*, 1854), who treated logical reasoning as symbolic calculation. Its application to circuits is due to **Claude Shannon**, whose 1937 MIT master's thesis *A Symbolic Analysis of Relay and Switching Circuits* showed that Boolean algebra exactly describes — and, crucially, *simplifies* — networks of relays and switches. That single insight founded digital design; the expansion theorem of §5.3 bears his name. The single-operator results are older than the transistor: **Charles Sanders Peirce** noted around 1880 (unpublished) that one connective suffices, and **Henry Sheffer** proved it in print in 1913 for the stroke $\uparrow$. **Emil Post** (1941) then classified *all* complete sets via his lattice of clones. On the minimization side, **Edward Veitch** proposed a chart in 1952 which **Maurice Karnaugh** refined into today's map in 1953 (both at Bell Labs), while **Willard Quine** (1952, 1955) and **McCluskey** (1956) gave the tabular algorithm.

**Connections to computer science.**

- **Programmable logic (PLA, PAL):** a two-level SOP maps directly onto a programmable AND-plane feeding an OR-plane — minimization literally sets which fuses to blow.
- **FPGAs and LUTs:** a $k$-input lookup table *is* a stored truth table, so any $k$-variable function is realised without gate-level minimization at all — a modern echo of Theorem 5.1.
- **BDDs:** iterating Shannon expansion (Theorem 5.2) with a fixed variable order and sharing identical subfunctions yields the *ordered binary decision diagram*, the standard data structure for representing and comparing huge Boolean functions in verification.
- **SAT and verification:** the CNF of §5.5 is the input format for SAT solvers; equivalence checking two circuits reduces to a satisfiability question about their XOR.
- **Compilers:** short-circuit evaluation, branch simplification, and dead-code elimination apply exactly the identities of §5.6 to program conditions.
- **Automata theory (Lecture 14):** everything here is *combinational* (output $=$ function of current input). A flip-flop adds state; the machine's next-state and output logic are combinational blocks minimized by precisely these methods, so this lecture is the foundation of the sequential machines (Mealy/Moore) studied there.

---

## Chapter summary

- A Boolean function is a map $\{0,1\}^n\to\{0,1\}$; there are $2^{2^n}$ of them, and exactly **16** of two variables (AND, OR, NOT, NAND, NOR, XOR, XNOR, the two implications and inhibitions, the projections, and the two constants).
- **Shannon expansion** $f=(x_i\wedge f|_{x_i=1})\vee(\overline{x_i}\wedge f|_{x_i=0})$ proves $\{\wedge,\vee,\neg\}$ is **functionally complete** by induction; De Morgan then gives completeness of $\{\wedge,\neg\}$ and $\{\vee,\neg\}$.
- $\{\wedge,\vee\}$ is **not** complete — it produces only monotone functions, and $\neg$ is non-monotone. Negation is indispensable.
- **NAND** ($\uparrow$) and **NOR** ($\downarrow$) are each complete alone: $\overline A=A\uparrow A=A\downarrow A$, with two-step rebuilds of $\wedge$ and $\vee$. Post's theorem characterises *all* complete sets via five maximal classes.
- **Logic gates** realise these operations; a formula maps directly onto a gate network, and any two-level AND–OR circuit becomes an all-NAND (or all-NOR) circuit of the same shape.
- **CDNF** $=\sum$ minterms over the $1$-rows and **CCNF** $=\prod$ maxterms over the $0$-rows; both **exist and are unique** (Theorems 5.10–5.11), read straight from the truth table.
- **Algebraic minimization** applies the identities (combining, absorption, consensus) — powerful but with no stopping rule.
- A **Karnaugh map** uses Gray-code labelling so that adjacency $=$ one-variable change; grouping $1$s (into power-of-two subcubes, wrap-around allowed, don't-cares exploited) gives a minimal SOP, grouping $0$s gives a minimal POS. Cover essential prime implicants first.
- **Quine–McCluskey** mechanises this: combine to find all prime implicants, then use a PI chart (with Petrick's method for cyclic charts) to pick a minimal cover — scalable past the reach of K-maps.
- **Minimization saves gates, transistors, area, power, and delay**, which is why it sits at the heart of digital design.

---

## Exercises

### Warm-up

**W1.** How many Boolean functions are there of $3$ variables? Of $n$ variables? How many of the $16$ two-variable functions are monotone?

**W2.** For the input row $(A,B,C,D)=(1,0,1,1)$, write (a) its minterm and (b) its maxterm.

**W3.** For $F(A,B,C)=\sum m(0,2,5,7)$, write the CDNF as an expression and the CCNF as a $\prod M(\dots)$ list of maxterms.

**W4.** Using only NAND gates, build (a) an inverter and (b) a $2$-input AND. Count the gates in each.

**W5.** Simplify with a single law each: (a) $A\vee AB$; (b) $A(A\vee B)$; (c) $\overline A\vee AB$.

**W6.** Why must K-map columns be labelled $00,01,11,10$ rather than $00,01,10,11$? Give the two-bit patterns that would become "adjacent" incorrectly.

### Standard

**S1.** Prove that $\{\vee,\neg\}$ is functionally complete by expressing $A\wedge B$ using only $\vee$ and $\neg$, and justify each step.

**S2.** Show that XOR ($A\oplus B$) is *not* expressible using only $\{\wedge,\vee\}$. (Hint: monotonicity, or $0$/$1$-preservation.)

**S3.** Minimize $F(A,B,C)=\sum m(0,1,2,3,4,5)$ with a K-map. Express the result with a named two-variable operation.

**S4.** Minimize $F(A,B,C,D)=\sum m(1,3,5,7,9,11,13,15)$. (Look before you compute.)

**S5.** Express $A\oplus B$ using only NOR gates, and count the gates. (Hint: $A\oplus B=A\overline B\vee\overline A B$; or first get $\wedge,\vee,\neg$ from $\downarrow$.)

**S6.** From the truth table of $F(A,B,C)=\sum m(0,1,4,5,7)$, write both the CDNF and the CCNF, and verify that the index sets $\{0,1,4,5,7\}$ and $\{2,3,6\}$ partition $\{0,\dots,7\}$.

**S7.** For the minimized $F=\overline B\vee AC$: draw the gate circuit, count gates and (using the §5.9 CMOS figures) transistors, then repeat for a circuit built directly from the five-minterm CDNF. State the ratio.

**S8.** A four-variable function is $1$ on $\{2,3,7,9,11,13\}$ and don't-care on $\{1,10,15\}$; it is $0$ elsewhere. Minimize it as an SOP using a K-map, exploiting the don't-cares.

### Challenge

**C1.** Run Quine–McCluskey on $F(A,B,C,D)=\sum m(0,2,3,5,7,8,10,11,12,13,15)$: list all prime implicants, build the PI chart, identify the essential PIs, and give a minimal SOP.

**C2.** Prove that the $2^n$ minterms of $n$ variables partition $\{0,1\}^n$ — i.e. every input satisfies exactly one minterm — and deduce that $\sum_a m_a\equiv 1$.

**C3.** The chart for $F(A,B,C)=\sum m(0,1,2,5,6,7)$ is *cyclic*: find all six prime implicants, show the chart has no essential PI, and use Petrick's method to obtain the (two) minimal SOPs.

**C4.** Prove that NOR is functionally complete using **Post's criterion** — show $A\downarrow B$ lies outside each of the five maximal classes $T_0,T_1,M,S,L$.

**C5.** A function is **self-dual** if $f(\overline{x_1},\dots,\overline{x_n})=\overline{f(x_1,\dots,x_n)}$. Prove that a self-dual function of $n$ variables has exactly $2^{n-1}$ minterms, and that its CDNF and CCNF index sets are complementary "under bit-flip."

**C6.** Prove the **consensus theorem** $AB\vee\overline A C\vee BC=AB\vee\overline A C$ from the basic identities, and explain what it corresponds to on a Karnaugh map (why the $BC$ group is redundant).

---

## Selected answers & hints

**W1.** $2^{2^3}=2^8=256$; in general $2^{2^n}$. Monotone two-variable functions: $0,1,A,B,A\wedge B,A\vee B$ — six of them (all the others need negation or are XOR/XNOR).

**W2.** (a) minterm $A\overline B C D$; (b) maxterm $\overline A\vee B\vee\overline C\vee\overline D$. Note the opposite polarities.

**W3.** CDNF $=\overline A\,\overline B\,\overline C\vee\overline A B\overline C\vee A\overline B C\vee ABC$. The $0$-rows are $\{1,3,4,6\}$, so CCNF $=\prod M(1,3,4,6)=(A\vee B\vee\overline C)(A\vee\overline B\vee\overline C)(\overline A\vee B\vee C)(\overline A\vee\overline B\vee C)$.

**W4.** (a) $\overline A=A\uparrow A$ — one gate. (b) $A\wedge B=(A\uparrow B)\uparrow(A\uparrow B)$ — one NAND for $A\uparrow B$, a second NAND wired as an inverter, so **two** gates.

**W5.** (a) $A$; (b) $A$; (c) $\overline A\vee B$.

**S1.** $A\wedge B=\overline{\overline A\vee\overline B}$: negate each input, OR them, negate the result — De Morgan. Since $\{\wedge,\vee,\neg\}$ is complete and $\wedge$ is now built from $\{\vee,\neg\}$, the smaller set is complete.

**S2.** $\oplus$ is not monotone: $(0,0)\le(0,1)$ but $0\oplus0=0$ and $0\oplus1=1$ (fine), yet $(0,1)\le(1,1)$ with $0\oplus1=1>1\oplus1=0$. A $\{\wedge,\vee\}$-formula is monotone (Theorem 5.5), so it cannot be $\oplus$. (Alternatively: every $\{\wedge,\vee\}$-formula preserves both $0$ and $1$, but $\oplus$ preserves $0$ and *not* $1$ since $1\oplus1=0$.)

**S3.** Group: row $A=0$ (all four $1$s) $\Rightarrow\overline A$; columns $BC=00,01$ (both rows) $\Rightarrow\overline B$. So $F=\overline A\vee\overline B=\overline{AB}=A\uparrow B$ (NAND).

**S4.** These are exactly the odd rows (LSB $D=1$), so $F=D$. One group of eight; no other literal survives.

**S5.** Build $\neg,\wedge,\vee$ from $\downarrow$ (Theorem 5.7) and substitute into $A\overline B\vee\overline A B$; a compact standard NOR realization of XOR uses **five** NOR gates. (Any correct all-NOR network is acceptable; count your gates.)

**S6.** CDNF $=\overline A\,\overline B\,\overline C\vee\overline A\,\overline B C\vee A\overline B\,\overline C\vee A\overline B C\vee ABC$; CCNF $=(A\vee\overline B\vee C)(A\vee\overline B\vee\overline C)(\overline A\vee\overline B\vee C)$. The sets $\{0,1,4,5,7\}$ and $\{2,3,6\}$ are disjoint and their union is $\{0,\dots,7\}$ — a partition, as Theorem 5.10/5.11 guarantee.

**S7.** Minimized: $1$ NOT, $1$ AND$_2$, $1$ OR$_2$ $=3$ gates, $\approx 2+6+6=14$ transistors. CDNF: $3$ NOT, $5$ AND$_3$, $1$ OR$_5$ $=9$ gates, $\approx 3(2)+5(8)+1(12)=58$ transistors. Ratio about $3\times$ in gates, $4\times$ in transistors.

**S8.** With the map (rows $AB$, cols $CD$) and the don't-cares at $1,10,15$ set as convenient, a minimal cover is $F=\overline A C\vee A D\vee \overline A\overline C\!\dots$ — set up the map, mark $1$s at $\{2,3,7,9,11,13\}$ and $\times$ at $\{1,10,15\}$, and confirm your groups cover all real $1$s while never being forced to cover a $\times$. (Multiple minimal answers exist; verify by truth table.)

**C1.** Essential prime implicants come out to (one correct minimal form) $F=\overline A\,\overline B\,\overline C\vee \dots$; build the chart, take every single-mark column's PI, then cover the rest. Verify your SOP against the minterm list by evaluating all $16$ rows.

**C2.** By Lemma 5.8, $m_a(b)=1\iff a=b$; so for a fixed input $b$, exactly one minterm ($m_b$) is $1$ and the other $2^n-1$ are $0$ — the minterms' $1$-sets are the singletons $\{a\}$, which partition $\{0,1\}^n$. Their OR is therefore $1$ on every input: $\bigvee_a m_a\equiv 1$.

**C3.** Prime implicants: $\overline A\,\overline B\ (0,1)$, $\overline A\,\overline C\ (0,2)$, $\overline B C\ (1,5)$, $B\overline C\ (2,6)$, $AC\ (5,7)$, $AB\ (6,7)$. Every minterm is covered by exactly two PIs and every PI covers two minterms — no column has a single mark, so no PI is essential (cyclic). Petrick's product multiplies out to reveal minimal covers of three PIs each, e.g.

$$
F=\overline A\,\overline B\vee B\overline C\vee AC\qquad\text{or}\qquad F=\overline A\,\overline C\vee\overline B C\vee AB.
$$

Both use $3$ terms / $6$ literals.

**C4.** $A\downarrow B=\overline{A\vee B}$: $\downarrow(0,0)=1\ (\notin T_0)$; $\downarrow(1,1)=0\ (\notin T_1)$; non-monotone since $(0,0)\le(1,1)$ but $1>0$ ($\notin M$); not self-dual, e.g. $\downarrow(1,0)=0\ne\overline{\downarrow(0,1)}=\overline 0=1$ ($\notin S$); nonlinear, $\downarrow=1\oplus A\oplus B\oplus AB$ has the degree-$2$ term $AB$ ($\notin L$). Outside all five classes $\Rightarrow$ complete by Post.

**C5.** Pair each input $a$ with its bit-complement $\overline a$. Self-duality $f(\overline a)=\overline{f(a)}$ makes exactly one of each pair $\{a,\overline a\}$ a $1$-row, and the $2^n$ inputs split into $2^{n-1}$ such pairs, so $f$ has exactly $2^{n-1}$ minterms. Moreover $a$ indexes a minterm (a $1$-row) iff $\overline a$ indexes a maxterm (a $0$-row), so the CDNF and CCNF index sets are exact bit-flips of one another.

**C6.** $AB\vee\overline A C\vee BC$; expand $BC=BC(A\vee\overline A)=ABC\vee\overline A BC$; then $ABC\le AB$ and $\overline A BC\le\overline A C$, so $BC$ is absorbed and drops out, leaving $AB\vee\overline A C$. On a K-map, $AB$ and $\overline A C$ are two groups whose union already includes the cells of the $BC$ group; the $BC$ group covers nothing new, so adding it only wastes a gate.

---

## Further reading

- K. H. Rosen, *Discrete Mathematics and Its Applications* — chapter on Boolean algebra (Boolean functions, representing functions, logic gates, minimization, Karnaugh maps).
- Z. Kohavi and N. K. Jha, *Switching and Finite Automata Theory* — thorough treatment of canonical forms, the Quine–McCluskey algorithm, and multi-output/multi-level minimization.
- C. E. Shannon, "A Symbolic Analysis of Relay and Switching Circuits," *Trans. AIEE* 57 (1938) — the founding paper, for historical interest.