Karnaugh Maps
A visual method for simplifying Boolean expressions by grouping adjacent cells.
Problem
A truth table with n inputs has 2n rows. Writing a sum-of-products (SOP) expression directly from the table gives one product term per 1-output row. For 4 inputs, that can be up to 16 terms. How do you find the simplest equivalent expression?
How it works
The K-map is a 2D grid where each cell is one row of the truth table, arranged so adjacent cells differ by exactly one variable (Gray code ordering). This means neighboring 1-cells can always be combined.
Grouping rules:
• Groups must be rectangular and contain 2k cells (1, 2, 4, 8, …).
• The grid wraps around: the leftmost column is adjacent to the rightmost, top row to bottom row.
• Every 1-cell must be covered by at least one group. Groups can overlap.
• Make groups as large as possible: each doubling eliminates one variable from that term.
Reading the result: For each group, identify which variables stay constant across all cells in the group. Variables that are 1 appear uncomplemented; variables that are 0 appear complemented. Variables that change within the group disappear. The final expression is the OR (sum) of all group terms.
Don't-cares (X): Inputs that can never occur (or whose output doesn't matter) can be treated as 0 or 1: whichever makes groups larger. This is free simplification that the truth table alone can't reveal.
POS minimization: To get a product-of-sums (POS) form, group the 0-cells instead of the 1-cells. Each group of 0s gives a sum (OR) term, and the final expression is the AND of those terms.
Grouping rules:
• Groups must be rectangular and contain 2k cells (1, 2, 4, 8, …).
• The grid wraps around: the leftmost column is adjacent to the rightmost, top row to bottom row.
• Every 1-cell must be covered by at least one group. Groups can overlap.
• Make groups as large as possible: each doubling eliminates one variable from that term.
Reading the result: For each group, identify which variables stay constant across all cells in the group. Variables that are 1 appear uncomplemented; variables that are 0 appear complemented. Variables that change within the group disappear. The final expression is the OR (sum) of all group terms.
Don't-cares (X): Inputs that can never occur (or whose output doesn't matter) can be treated as 0 or 1: whichever makes groups larger. This is free simplification that the truth table alone can't reveal.
POS minimization: To get a product-of-sums (POS) form, group the 0-cells instead of the 1-cells. Each group of 0s gives a sum (OR) term, and the final expression is the AND of those terms.
Key insightA group of 2k cells eliminates k variables. A single cell = 0 variables eliminated (full minterm). Two cells = 1 variable gone. Four cells = 2 variables gone. The K-map makes this visual: you literally see simplification as larger rectangles.