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$

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 #

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$:

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:

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

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)$:

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:

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

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$):

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.

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$:

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

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

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.

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$:

• 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$:

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$):

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:

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