L10: Minimization

Let’s practice Boolean algebra!

Objective
Practice usage of theorems 5-17 of Boolean algebra.

Additional Materials & Formats
Check Box for the most up-to-date versions of this lecture’s materials.

Before the Lecture

Required Textbook Reading:

• 2.11 (Minimization and Karnaugh Maps)
• 2.12 (Strategy for Minimization)
• 2.13 (Minimization of Product-of-Sums Forms)
• 2.14 (Incompletely Specified Functions)

Optional Supplemental Instruction:

• Introduction to Karnaugh Maps – The Organic Chemistry Tutor on YouTube
• Karnaugh map – Wikipedia (for a deep dive)

Quick overview

Minimization reduces a Boolean function to an equivalent form with fewer terms or literals. We could use our theorems of Boolean algebra to do this from start to finish, but that’s a major pain. Karnaugh maps (K-maps) give us a visual method for minimizing small functions by grouping adjacent minterms.

Goals:

• Find large groups of 1s (or 0s for POS) that are powers of two: 1, 2, 4, 8, …
• Extract product terms (SOP) that correspond to variables that are constant across a group.
• Prefer larger groups to reduce literal count.
• Use don’t-care entries to enlarge groups.

K-map Quick Review

• A K-map has $2^n$ cells for n variables. Each cell corresponds to one minterm.
• Rows and columns are labeled in Gray code order so adjacent cells differ by one variable.
• Cells at edges are adjacent (wrap-around), so the map is topologically a torus.

Grouping

• Grouping rules:
  • Groups must contain $2^k$ cells ($k \geq 0$).
  • Groups should be as large as possible and may overlap.
  • Every 1 must be covered by at least one group.
  • Groups may wrap around edges.
  • Do not split groups into smaller ones if they can be combined.
• Terminology:
  • Literal: a single appearance of a variable (complemented or uncomplemented).
  • Implicant: a product term that covers some 1s.
  • Prime implicant: an implicant not contained in a larger implicant.
  • Essential prime implicant: a prime implicant that covers at least one minterm not covered by any other prime implicant.
  • Cover: a collection of implicants that account for all valuations for which as function is equal to 1.

How to read a group into a product term

Within a group, any variable that changes (both 0 and 1 appear) is eliminated. Variables that remain constant form the product term:

• If a variable is 1 in all grouped cells, include it as the uncomplemented literal.
• If a variable is 0 in all grouped cells, include it as the complemented literal.
• Example: In a 4-variable map with group covering cells where A=0, B varies, C=1, D=0, the term is A’ C D'.

Worked Example

Karnaugh maps simplify Boolean functions by grouping adjacent minterms. Consider the 4-variable function f(A,B,C,D) given by this truth table:

In minterm/maxterm notation:

• $f(A,B,C,D)=\displaystyle\sum m_i,~i\in{6,8,9,10,11,12,13,14}$.
• Equivalently, $f(A,B,C,D)=\displaystyle\prod M_i,; i\in{0,1,2,3,4,5,7,15}$.

K-map construction: arrange a 4×4 grid (16 cells) with row/column indices in Gray code so adjacent cells differ by one bit. Each cell holds the function output for that input combination; edges wrap around (toroidal adjacency).

Grouping: encircle rectangular groups of 1s whose sizes are powers of two (1,2,4,8…). Groups should be as large as possible and may overlap or wrap edges. In this example the optimal groups are:

• Red: a 2×2 square (covers cells where A=1 and C=0).
• Green: a 4×1 rectangle (covers cells where A=1 and B=0).
• Blue: a 2×2 (or 2×1 depending on layout) giving the term involving B, C and D.

Solution (extracting product terms): within each group, keep only variables that are constant.

Image: Cmglee, CC BY-SA 4.0, via Wikimedia Commons

• Red group:

  • A = 1 throughout → include $A$.
  • C = 0 throughout → include $\overline{C}$.
  • B and D vary → excluded.
  • Term: $A\overline{C}$.

• Green group:

  • A = 1 and B = 0 throughout → include $A\overline{B}$.
  • C and D vary → excluded.
  • Term: $A\overline{B}$.

• Blue group:

  • B = 1, C = 1 and D = 0 throughout → include $BC\overline{D}$.
  • Term: $BC\overline{D}$.

Combine groups to get the simplified SOP: $,f(A,B,C,D)=A\overline{C} + A\overline{B} + BC\overline{D}.$

This corresponds to a reduction from the full sum of eight minterms down to three product terms.

See the full worked example on Karnaugh map at Wikipedia.

Incompletely Specified Functions

Don’t-cares (often written X or d) are input combinations for which the output value is irrelevant or undefined in the intended application. Because their true output doesn’t matter, you may treat don’t-cares as either 0 or 1 when minimizing a function. In practice this lets you expand groups on a K-map (or combine terms algebraically) to form larger power-of-two groupings, yielding fewer literals or terms.

Key points:

• Use don’t-cares to enlarge groups of 1s when finding a minimal SOP, or to enlarge groups of 0s for POS minimization.
• A don’t-care can be assigned differently in different groups if that produces a simpler overall expression.
• Do not require that every don’t-care be covered; only use them where they help simplification.
• Always verify the final minimized expression matches the specified outputs for the non-don’t-care inputs.

Don’t-cares can improve minimization but must be applied carefully so the implementation still meets the real system constraints.

Recipe for solving a K-map problem

1. Draw the correct-size K-map (2^n cells).
2. Fill in 1s, 0s, and don’t-cares.
3. Group largest possible power-of-two rectangles (allow wrap-around).
4. Write each group’s product term (keep only constant variables).
5. Combine terms to form the simplified SOP (or POS) expression.
6. Verify by truth table or algebraic expansion if needed.

These steps will produce a minimal or near-minimal expression for small-variable functions and provide intuition for automated minimization on larger problems.

Visualizing a K-map as a Torus

Image: Cmglee, CC BY-SA 4.0, via Wikimedia Commons

Textbook Walkthrough

Because it is a massive pain to typeset K-maps (and you likely paid the textbook’s authors a hefty sum to do that work for us), let’s walk through some of the textbook examples as a class.

K-maps are something you learn best by practicing – let’s practice together!