Karnaugh Maps

Find the minimal Sum-of-Products expression for a function given by its minterms.

Applying Boolean laws one at a time, like the previous topic, works but doesn't guarantee you land on the shortest possible expression — it's easy to stop simplifying one step too early without noticing. A Karnaugh map (K-map) is a way of laying out a truth table so that a genuinely minimal expression falls out visually, by grouping adjacent 1s.

Ready to put it into practice?

Start practicing

Note on this page specifically: there's no clickable grid here — you reason through the grouping yourself (on paper is normal) and type the resulting expression, which is checked for both correctness and minimality, not just correctness.

A cell's minterm number is just its row in the truth table, in binary:

m_i = (\text{the row where the inputs, read as a binary number, equal } i)

Minterm numbering

$m_i$ minterm i — the specific input combination whose binary value is i.

The whole trick of a K-map is arranging cells so that physically adjacent cells differ in exactly one variable — that's why the columns/rows go 00, 01, 11, 10 (Gray code), not 00, 01, 10, 11. Two adjacent 1s can always be combined into one term with one fewer variable, because whichever variable flips between them doesn't matter to the function's output there.

Group the 1s into the largest rectangles you can, where each rectangle's size is a power of two (1, 2, 4, 8 cells) and wraps around the edges of the map. Each group becomes one product term: a group of 2^k cells eliminates k variables from that term, keeping only the variables that stay constant across the whole group.

A 1 that's covered by only one possible group is an essential prime implicant — that group must be in your final answer, no choice about it. Once every essential group is included, cover whatever 1s are still left with as few additional groups as possible. The result is the minimal Sum-of-Products (SOP) form: an OR of the smallest possible number of AND terms, each with as few literals as possible.

Worked example

f(A,B,C) = 1 \text{ at minterms } \{2, 3, 4, 5\}

$\overline{A}B\overline{C} + \overline{A}BC + A\overline{B}\,\overline{C} + A\overline{B}C$
The canonical (unsimplified) SOP — one term per minterm, straight from the truth table.
$\{2,3\} \to \overline{A}B, \qquad \{4,5\} \to A\overline{B}$
Group adjacent 1s in pairs — each pair drops the one variable that differs between its two minterms (here, C). Both groups are essential: minterms 2 and 3 are only reachable via {2,3}, and minterms 4 and 5 only via {4,5} — there's no other prime implicant covering either pair.
$\overline{A}B + A\overline{B}$
The minimal cover: 2 terms, 4 literals total, and every minterm in {2,3,4,5} is covered — no equivalent expression uses fewer of either. Notice C dropped out completely: this function doesn't actually depend on C at all.

Answer:

\overline{A}B + A\overline{B}

How to solve one of these

1.
List the minterms. The input combinations where the function is 1.
2.
Find every prime implicant. Every maximal group of adjacent 1s (size a power of two) that can't be grown any larger.
3.
Pull out the essential prime implicants. Any 1 covered by only one possible group forces that group into the answer.
4.
Cover what's left with as few more groups as possible. Aim for the fewest additional terms, and among ties, the fewest total literals.
5.
Write the SOP expression. One product term per group you selected, OR'd together.

m_i, \quad \Sigma m(0, 1, 2, \ldots)

Minterm i, and the standard shorthand for "the function that's 1 at exactly these minterms."

Ready to put it into practice?

Start practicing

Want the rest of Calc III? Leave your email and I'll tell you the day the pack's live.