Chapter 2: Boolean Algebra and Logic Gates

Source files used: ELEC205 Week 2 slides (slides 23-56), Week 3 slides (slides 4-39); textbook Chapter 2 as support. No worked examples are included.

1. Big Picture

Chapter 2 is the algebra behind every combinational circuit.

Chapter 1 asked: how do we write numbers in bits? Chapter 2 asks: how do we build a circuit whose output is any function of those bits, using only basic gates?

$$\boxed{\text{Truth table}\ \to\ \text{Boolean expression (SOP/POS)}\ \to\ \text{gate circuit (incl. all-NAND / all-NOR)}}$$

New ideas in this chapter:

• logic gates as the “atoms” of digital systems,
• Boolean algebra theorems, DeMorgan, duality,
• minterms and maxterms,
• canonical SOP and POS forms and converting between them,
• two-level AND-OR / OR-AND circuits and the bubble trick (NAND-NAND, NOR-NOR).

Erzin’s analogy: learn how each gate “moves” first (like chess pieces), then the standard plays (adders, decoders, MUXes), then practice many designs.

---

2. Core Ideas

2.1 Combinational System

A combinational system has no memory: the current output depends only on the current input. It is completely described by a truth table.

With 2 inputs there are 4 input rows, so a 2-input function is just a choice of 4 output bits. The slides list the useful ones: constant 0, AND, OR, NAND, NOR, XOR, XNOR, constant 1. With one input: buffer ($f=x$), inverter ($f=x'$), and the two constants.

---

2.2 Basic Gates

Every gate is one row of the table in Section 6.1. Two notes from the slides:

• NAND and NOR are AND/OR followed by an inverter (the output bubble).
• By DeMorgan, NAND equals OR with inverted inputs, and NOR equals AND with inverted inputs. This is the basis of the bubble trick.

Any digital function can be built with AND, OR and NOT. Basic gates are the atoms of digital systems.

---

2.3 Boolean Algebra

Algebra on the set $\{0,1\}$ with three operations:

• $+$ : OR,
• $\cdot$ : AND,
• $'$ : complement (NOT).

Boole (1854) defined it; Shannon (1938) adapted it as switching algebra for circuits. It is used to (1) express any function in terms of basic gates and (2) simplify those implementations.

---

2.4 Duality

Every theorem has a dual. Erzin’s recipe: pick a theorem, then

• swap 1’s with 0’s,
• swap variables with their complements,
• swap ANDs with ORs,

and you obtain another theorem. The textbook’s duality principle swaps only AND/OR and 0/1 (variables unchanged); both recipes produce valid theorems. This is why the theorem list in Section 3 comes in pairs.

---

2.5 Minterms and Maxterms

• Minterm $m_k$: a product (AND) term in which every variable appears exactly once, complemented or not. It equals 1 on exactly one row (row $k$).
• Maxterm $M_k$: a sum (OR) term in which every variable appears exactly once. It equals 0 on exactly one row (row $k$).

There are $2^n$ of each for $n$ variables, one per binary number $0$ to $2^n-1$. In a minterm a 0 bit gives a complemented variable; in a maxterm a 0 bit gives an uncomplemented variable.

---

2.6 SOP and POS

• Sum of Products (SOP): OR of AND terms. Built from the rows where $f=1$. Two-level AND-OR circuit.
• Product of Sums (POS): AND of OR terms. Built from the rows where $f=0$. Two-level OR-AND circuit. POS is the dual of SOP.

A canonical form uses full minterms/maxterms. A standard (simplified) form uses shorter terms.

---

3. Main Governing Equations and Formulas

3.1 Single-Variable Theorems

$$X+0=X\qquad X\cdot1=X\qquad\text{(identity)}$$ $$X+1=1\qquad X\cdot0=0\qquad\text{(null element)}$$ $$X+X=X\qquad X\cdot X=X\qquad\text{(idempotency)}$$ $$X+X'=1\qquad X\cdot X'=0\qquad\text{(complements)}$$ $$(X')'=X\qquad\text{(involution)}$$

Each one can be proven by checking $X=0$ and $X=1$ (perfect induction).

---

3.2 Commutative and Associative

$$X+Y=Y+X\qquad X\cdot Y=Y\cdot X$$ $$X+(Y+Z)=(X+Y)+Z\qquad X\cdot(Y\cdot Z)=(X\cdot Y)\cdot Z$$

Meaning: input order on an AND or OR gate does not matter, and multi-input AND/OR gates are well defined.

---

3.3 Distributive

$$X\cdot(Y+Z)=X\cdot Y+X\cdot Z$$ $$X+Y\cdot Z=(X+Y)\cdot(X+Z)$$

The second form has no decimal counterpart. Use it to “sum out” an SOP into POS.

---

3.4 Absorption

$$X+X\cdot Y=X\qquad X\cdot(X+Y)=X$$

Use to delete redundant terms.

---

3.5 Combining (Adjacency)

$$X\cdot Y+X\cdot Y'=X\qquad (X+Y)\cdot(X+Y')=X$$

Erzin calls these the key theorems for circuit simplification. They are exactly what a K-map group does in Chapter 3.

---

3.6 DeMorgan’s Theorems

$$(X\cdot Y)'=X'+Y'\qquad (X+Y)'=X'\cdot Y'$$

$N$-variable form:

$$(X_1+X_2+\dots+X_N)'=X_1'\cdot X_2'\cdots X_N'$$ $$(X_1\cdot X_2\cdots X_N)'=X_1'+X_2'+\dots+X_N'$$

Generalized form (complement of any function):

$$F(X_1,\dots,X_N;\,+,\cdot)'=F(X_1',\dots,X_N';\,\cdot,+)$$

To complement an expression: swap $+$ and $\cdot$ and complement every literal. Keep the original grouping with parentheses.

---

3.7 Shannon Expansion

$$F(X_1,X_2,\dots,X_N)=X_1\cdot F(1,X_2,\dots,X_N)+X_1'\cdot F(0,X_2,\dots,X_N)$$

Use to split a function on one variable. This is the basis of 5-variable K-maps and MUX implementations (Chapters 3 and 4).

---

3.8 Minterm/Maxterm Relation

$$m_k=(M_k)'$$

Two-variable case:

$$m_0=x'y',\ m_1=x'y,\ m_2=xy',\ m_3=xy$$ $$M_0=x+y,\ M_1=x+y',\ M_2=x'+y,\ M_3=x'+y'$$

---

3.9 Canonical SOP and POS

$$F=\sum m(\text{rows where }F=1)$$ $$F=\prod M(\text{rows where }F=0)$$ $$F'=\sum m(\text{rows where }F=0)$$

Example from the slides: $F(X,Y,Z)=\sum m(0,2,5,7)$ gives $F'=\sum m(1,3,4,6)$ and $F=\prod M(1,3,4,6)$.

The POS index list is exactly the indices missing from the SOP list.

---

3.10 Getting POS from $F'$

$$F=(F')'=\big(\textstyle\sum m(\text{0-rows})\big)'=\prod M(\text{0-rows})$$

Write $F'$ as SOP, then apply DeMorgan. Example: XOR has $f'=x'y'+xy$, so $f=(x+y)(x'+y')$.

Use this whenever you need a POS (or a NOR circuit).

---

3.11 Two-Level Gate Equivalences

$$\text{AND-OR (SOP)}\ =\ \text{NAND-NAND}$$ $$\text{OR-AND (POS)}\ =\ \text{NOR-NOR}$$

Bubble trick: add a bubble at each first-level output and at each matching second-level input. Two bubbles on a wire cancel ($(X')'=X$). The OR with bubbled inputs is a NAND (DeMorgan), so the whole circuit becomes NAND gates. Same idea with OR-AND giving NOR-NOR.

A single literal feeding the second level directly has no first-level gate, so per the textbook it must be complemented when the output gate becomes NAND/NOR.

---

4. Problem-Solving Workflow

4.1 Truth Table to Circuit

1. List the rows where $f=1$.
2. Write one minterm per row (0 → complemented variable, 1 → plain variable).
3. OR them: canonical SOP.
4. Simplify with the theorems (Sections 3.4, 3.5) or a K-map (Chapter 3).
5. Draw AND-OR, then convert to NAND-NAND if asked.

4.2 Converting Between Forms

1. $\sum m$ list to $\prod M$ list: take the missing indices.
2. Expression to canonical form: build the truth table, or expand each term by multiplying in $(X+X')$ for missing variables.
3. Arbitrary circuit to SOP: “multiply out” with the first distributive law. Slide example: $F=(X+Y')Z+X'YZ'=XZ+Y'Z+X'YZ'$.
4. Arbitrary circuit to POS: “sum out” with $X+YZ=(X+Y)(X+Z)$, or go through $F'$ (Section 3.10).

4.3 Complementing an Expression

1. Swap every $+$ with $\cdot$ and every $\cdot$ with $+$.
2. Complement every literal.
3. Keep the original operator precedence by adding parentheses.

---

5. Decision Rules / Decision Trees

5.1 SOP or POS?

Fewer 1’s than 0’s in the truth table? → SOP from the 1-rows is usually shorter

Fewer 0’s than 1’s? → POS from the 0-rows is usually shorter

Asked for NAND-only? → start from SOP, use NAND-NAND

Asked for NOR-only? → start from POS, use NOR-NOR

5.2 Which Theorem?

Two terms differ in exactly one variable? → combining: $XY+XY'=X$

One term contains another term entirely? → absorption: $X+XY=X$

Complement over a product or sum? → DeMorgan

Need to split on one variable? → Shannon expansion

---

6. Important Tables / Correlations Needed

6.1 Gate Summary

Gate	Expression	Output is 1 when
AND	$xy$	all inputs are 1
OR	$x+y$	any input is 1
NOT	$x'$	input is 0
NAND	$(xy)'$	any input is 0
NOR	$(x+y)'$	all inputs are 0
XOR	$x\oplus y=x'y+xy'$	inputs differ
XNOR	$(x\oplus y)'$	inputs are equal

6.2 Three-Variable Minterms and Maxterms

$xyz$	Minterm	Maxterm
000	$m_0=x'y'z'$	$M_0=x+y+z$
001	$m_1=x'y'z$	$M_1=x+y+z'$
010	$m_2=x'yz'$	$M_2=x+y'+z$
011	$m_3=x'yz$	$M_3=x+y'+z'$
100	$m_4=xy'z'$	$M_4=x'+y+z$
101	$m_5=xy'z$	$M_5=x'+y+z'$
110	$m_6=xyz'$	$M_6=x'+y'+z$
111	$m_7=xyz$	$M_7=x'+y'+z'$

6.3 Properties of Minterms and Maxterms

Minterms	Maxterms
$2^n$ of them, one per number $0$ to $2^n-1$	$2^n$ of them, one per number $0$ to $2^n-1$
Every function is a sum of minterms	Every function is a product of maxterms
Absent minterms belong to $F'$	Absent maxterms belong to $F'$
Sum of all minterms $=1$	Product of all maxterms $=0$

---

7. Key Takeaways

• A combinational circuit is fully defined by its truth table; output depends only on current inputs.
• Boolean algebra: set $\{0,1\}$, operations OR, AND, NOT.
• Combining ($XY+XY'=X$) and absorption ($X+XY=X$) are the main simplification tools.
• DeMorgan: complement swaps AND/OR and complements each literal.
• $m_k$ is 1 only on row $k$; $M_k$ is 0 only on row $k$; $m_k=M_k'$.
• $\sum m(\dots)$ and $\prod M(\dots)$ use complementary index lists.
• POS shortcut: write $F'$ as SOP, then apply DeMorgan.
• AND-OR becomes NAND-NAND; OR-AND becomes NOR-NOR (bubble trick).
• Shannon expansion splits a function on one variable; it reappears in MUX design.
• Trap: in a maxterm, a 0 bit means the uncomplemented variable.