Karnaugh Map
Minimise a Boolean function of two to four variables, with the map and every prime implicant.
3 product terms
the usual measure of cost
this cover is the only minimal one
The map
| AB\CD | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 00 | 10 | 11 | 03 | 12 |
| 01 | 04 | 15 | 17 | 16 |
| 11 | 012 | 013 | 015 | 114 |
| 10 | 18 | 19 | 011 | 110 |
Columns and rows run in Gray-code order, so any two neighbouring cells differ in exactly one variable — which is what makes a rectangular group legal.
| Prime implicant | Pattern | Covers | Status |
|---|---|---|---|
| ĀC̄D | 0-01 | 1, 5 | Not needed |
| ĀBD | 01-1 | 5, 7 | Chosen to finish the cover |
| ĀBC | 011- | 6, 7 | Not needed |
| B̄C̄ | -00- | 0, 1, 8, 9 | Essential — nothing else covers one of its minterms |
| B̄D̄ | -0-0 | 0, 2, 8, 10 | Not needed |
| CD̄ | --10 | 2, 6, 10, 14 | Essential — nothing else covers one of its minterms |
The cover is found by exhaustive search over the prime implicants, so it is genuinely the cheapest — not merely a good one found by a greedy rule.
A Karnaugh map rearranges a truth table so that neighbouring cells differ in exactly one variable. Groups of adjacent 1s then correspond to terms with that variable cancelled out, which is why circling the largest legal groups gives the simplest expression.
Why the map is laid out so strangely
The columns do not run 00, 01, 10, 11 but 00, 01, 11, 10. That is Gray code, and it is the whole point: consecutive entries differ in one bit, so any two cells sharing an edge differ in exactly one variable. Two adjacent 1s therefore represent a pair like AB̄C and ABC, whose sum simplifies to AC — the B has cancelled, because the function is 1 whether B is true or false.
Everything else follows. A group of two removes one variable, a group of four removes two, a group of eight removes three. The groups must be rectangles of size a power of two, and they wrap around the edges, because the leftmost and rightmost columns also differ in only one bit. That wrap-around is the part most often missed by eye.
Prime implicants, and choosing between them
A group that cannot be made any larger is a prime implicant. Finding them all is mechanical — the Quine–McCluskey procedure repeatedly combines terms differing in one bit until nothing more combines — but finding the cheapest set that still covers every 1 is a separate problem. Some prime implicants are essential, being the only one covering a particular minterm; the rest are a choice, and this page searches every combination rather than taking whichever looks biggest first.
groups must be rectangles whose side lengths are powers of two, and they wrap round the edges
- 1 Fill the map from the truth table. Put a 1 in every cell whose index is a minterm, an x for a don’t-care, and 0 elsewhere.
- 2 Find the largest legal groups. Rectangles of 1, 2, 4, 8 or 16 cells. Don’t-cares may be included when it helps, and ignored when it does not.
- 3 Remember the edges wrap. The left and right columns are neighbours, and so are the top and bottom rows. The four corners of a four-variable map form a legal group of four.
- 4 Keep the essential groups. If a 1 is covered by only one group, that group must be in the answer.
- 5 Cover what is left as cheaply as possible. Choose among the remaining groups to cover the rest with the fewest literals — not simply the fewest groups.
What each group size buys
On a four-variable map. A larger group is always a simpler term.
| Cells in the group | Variables eliminated | Literals left | Example term |
|---|---|---|---|
| 1 | 0 | 4 | AB̄CD |
| 2 | 1 | 3 | AB̄C |
| 4 | 2 | 2 | AB̄ |
| 8 | 3 | 1 | A |
| 16 | 4 | 0 | 1 — the function is always true |
Don’t-cares, and what the method cannot do
A don’t-care marks an input combination that never occurs — a binary-coded decimal digit above 9, say, or a state the hardware cannot reach. Because the output for it is irrelevant, it can be treated as a 1 when that enlarges a group and as a 0 when it does not. Using them well often removes a whole term, which is why they are worth listing rather than leaving as zeros.
Two limits are worth naming. The map is a visual method and stops being usable past four variables — five needs two stacked maps and six is essentially unreadable, which is why real synthesis tools use Quine–McCluskey or Espresso rather than a drawing. And the result here is a minimal sum of products; a product of sums can sometimes be cheaper still, and is found by mapping the zeros instead.
One thing the page reports that a hand-drawn map hides: whether the minimal cover is unique. When several different sets of prime implicants share the lowest cost, any of them is equally correct, and a textbook answer key showing a different expression from yours may well be one of the alternatives rather than a mark against you.