Karnaugh Maps

Karnaugh maps (K-maps) are a visual tool for simplifying Boolean expressions. Instead of applying algebraic rules mechanically, you draw a grid, fill in the truth table values, and group adjacent 1s. Each group corresponds to a simplified product term. For expressions with 2 to 4 variables, K-maps are faster and more intuitive than algebraic simplification.

Objectives

• Construct 2, 3, and 4-variable Karnaugh maps from truth tables
• Identify valid groups: sizes must be powers of 2 (1, 2, 4, 8, 16)
• Apply wrap-around grouping on edges and corners
• Extract minimized SOP expressions from K-map groupings
• Use don't care conditions (X) for additional simplification
• Extract POS expressions by grouping the 0s

Key Takeaways

• K-maps are a visual tool for minimizing Boolean expressions with 2-4 variables
• Gray code ordering ensures adjacent cells differ by exactly one variable
• Groups must be rectangular, contain only 1s, and have power-of-2 size
• Larger groups = simpler terms. Fewer groups = fewer product terms.
• Don't cares can be treated as 1 or 0 - choose what gives the best grouping
• Edges and corners wrap around - don't forget these adjacencies
• For POS, group the 0s instead of the 1s

Applications

• Circuit Design: Minimizing gate count in combinational logic.
• PLD Programming: Optimizing expressions for PAL/GAL/CPLD devices.
• State Machine Design: Minimizing next-state and output logic.
• Quick Verification: Visually confirming Boolean simplifications.

Practice Problems

Problem 1: Minimize f(A,B,C) = Σm(0,2,4,5,6) using a 3-variable K-map.

Problem 2: Minimize f(A,B,C,D) = Σm(0,1,2,5,8,9,10) using a 4-variable K-map.

Problem 3: A BCD-to-something converter has don't cares for inputs 10-15. f(A,B,C,D) = Σm(1,3,5) + Σd(10,11,12,13,14,15). Minimize.

Problem 4: Why are K-map columns ordered 00, 01, 11, 10 instead of 00, 01, 10, 11?

Problem 5: In a 4-variable K-map, which cells form a valid group: {0, 2, 8, 10}?