Simplifying Boolean Expressions
Boolean Algebra & Digital Logic
Chapter 5 · Simplifying Boolean Expressions
Chapter 4 closed with an honest admission: the SOP form it built is always correct, but almost never the shortest way to say the same thing. This chapter delivers two genuinely different tools for shrinking an expression down — algebraic simplification using Chapter 3's own laws, and Karnaugh maps, a visual method that finds the same simplification by spotting patterns instead of manipulating symbols.
Algebraic Simplification: Shrinking Chapter 4's Own Majority Function
Chapter 4's SOP form for the majority function was x'yz + xy'z + xyz' + xyz — 4 terms, 12 literals total. Simplifying it directly:
A=A+A) allows duplicating the shared xyz term twice, giving x'yz + xy'z + xyz' + xyz + xyz + xyz — still exactly equal to the original, just written with two extra (redundant) copies. Regrouping: (x'yz+xyz) + (xy'z+xyz) + (xyz'+xyz). Factoring each pair (distributive law): yz(x'+x) + xz(y'+y) + xy(z'+z). Applying the complement law (x'+x=1) to each: yz(1) + xz(1) + xy(1). Applying the identity law (x·1=x): yz + xz + xy.
xy + xz + yz matches majority(x,y,z) exactly, for all 8 input combinations — down from 4 terms / 12 literals to 3 terms / 6 literals, exactly half the size, with zero loss of correctness.
Karnaugh Maps: The Same Simplification, Found Visually
A Karnaugh map (K-map) arranges a truth table in a grid where adjacent cells always differ in exactly one variable — achieved by ordering the column headers in Gray code (00, 01, 11, 10, not the "obvious" 00, 01, 10, 11) so a single-bit change always corresponds to a single step across the grid.
| x \ yz | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 1 | 1 |
1-cells eliminates whichever variable changes between them, leaving only the variables that stay fixed across the group. Groups may overlap freely.
(x=1,yz=01) and (x=1,yz=11) are adjacent (only y changes) → group gives xz. Cells (x=1,yz=11) and (x=1,yz=10) are adjacent (only z changes) → group gives xy. Cells (x=0,yz=11) and (x=1,yz=11) are adjacent (only x changes) → group gives yz. Together: xz + xy + yz — the exact same result the algebraic method reached, found by pattern-spotting instead of symbol manipulation.
A Second, Simpler Example
A 2-variable function: f(x,y) = xy + xy'.
xy + xy' = x(y+y') = x(1) = x — an entire variable, y, disappears completely. Checked for all 4 inputs: f(x,y) equals plain x in every case. On a K-map, this is exactly a group spanning an entire row — the widest possible group, eliminating the one variable that changes across the whole row.
Real Relevance
Chapter 4's requirements-table-to-SOP procedure is guaranteed correct but routinely produces expressions far longer than necessary — exactly what happened with the majority function's own 12-literal starting point. Whether reached algebraically or visually, a simplified expression means fewer conditions to read in code, and — critically for Chapter 6 onward — fewer physical logic gates to build the same circuit from.
Hands-On Exercises
Simplify f(x,y) = xy + x'y algebraically, using Chapter 3's own laws, showing each step. Verify your simplified result against the original for all 4 input combinations.
Draw the K-map for the function f(x,y) = xy + x'y from Exercise 1 (a 2×2 grid, rows x=0/1, columns y=0/1), identify the group of adjacent 1s, and confirm it produces the same simplified expression you found algebraically.
A colleague simplifies xy + xz + yz (this chapter's own majority-function result) down to just xy + xz, claiming the yz term is redundant. Determine whether they're correct by checking all 8 input combinations, and explain your conclusion.
Chapter 5 Quick Reference
- Algebraic simplification: apply Chapter 3's own laws (idempotent to duplicate a shared term, distributive to factor, complement + identity to collapse) directly to an SOP expression
- Chapter 4's majority function shrank from 4 terms/12 literals to 3 terms/6 literals — verified against the original for all 8 inputs
- Karnaugh map: a grid with Gray-code-ordered headers so adjacent cells differ in exactly one variable; group adjacent 1s to eliminate the variable that changes across the group
- Both methods, applied to the same function, land on the exact same simplified result — verified directly
- A group spanning an entire row/column eliminates a whole variable (Exercise-worthy 2-variable example:
xy+xy'=x) - Next chapter: Logic gates and combinational circuits