Skip to content
Tutorials Center
My learning

Topics

Lesson 19 of 57 ยท Simplification

Karnaugh Maps

Learn Karnaugh maps step by step: Gray code order, grouping rules, wrap-around, prime implicants and simplification of 2 to 4 variable functions, with live Python.

Simplifying a Boolean expression with algebra works, but it needs insight: which law do you apply next, and have you found the shortest result? In 1953 Maurice Karnaugh proposed a drawing that turns the hunt into pattern matching. A Karnaugh map (K-map) is a truth table laid out in a grid so that cells next to each other differ in exactly one variable. Groups of adjacent 1s then correspond to terms that can lose a variable.

This lesson shows how to build 2, 3 and 4-variable maps, how to group cells correctly (including the wrap-around cases that trip up beginners), and how to read off a minimal sum of products. You will also draw a map with matplotlib and check results by brute force.

Why the grid works

The core algebra fact is XY + XYโ€ฒ = X(Y + Yโ€ฒ) = X. Two product terms that differ in only one variable merge into a shorter term. In a truth table those two rows are far apart, but in a K-map they sit side by side. Merging neighbours repeatedly gives you a term that is missing 1, 2 or 3 variables.

The trick that makes neighbours work is the Gray code order of the row and column labels. Instead of counting 00, 01, 10, 11, a K-map uses 00, 01, 11, 10, so that every step changes exactly one bit. The last label (10) also differs from the first (00) in one bit, so the left edge is a neighbour of the right edge, and the top edge is a neighbour of the bottom edge. The map is really a doughnut.

What a K-map is

A grid One cell for every row of the truth table.
Gray order Labels go 00, 01, 11, 10 so neighbours differ by one bit.
Wraps around Left meets right, top meets bottom.
1 / 2

Maps for 2, 3 and 4 variables

For two variables A and B, the map has four cells. For three variables, use two rows (A) and four Gray-ordered columns (BC). For four variables, use four rows (AB) and four columns (CD), both in Gray order. Cell positions correspond to minterm numbers. A 3-variable example for F = ฮฃm(1, 3, 5, 6, 7):

A \ BC 00 01 11 10
0 0 1 1 0
1 0 1 1 1

(The cell under A = 0, BC = 11 is minterm 3, and the one under A = 1, BC = 10 is minterm 6.)

The grouping rules

  1. A group must be a rectangle with 1, 2, 4, 8 or 16 cells (powers of two) and contains only 1s.
  2. Groups may overlap, and may wrap around the edges, including the four corners together.
  3. Make each group as large as possible. A bigger group means a shorter term.
  4. Cover every 1 with at least one group, using as few groups as possible.
  5. Diagonal cells are not neighbours. They differ in two bits.

To read a group, look at which variables stay constant across all its cells. A variable that is 1 throughout appears uncomplemented, one that is 0 throughout appears complemented, and one that changes within the group disappears.

For the table above, the two middle columns (BC = 01 and 11) form a group of four cells where C is always 1, while A and B both change. That group is simply C. The cells A = 1, BC = 11 and A = 1, BC = 10 form a group of two where A = 1 and B = 1 stay constant: AB. So F = C + AB. Notice that cell 7 is in both groups, which is allowed.

Drawing a 4-variable map

The map below shows F = ฮฃm(0, 2, 5, 7, 8, 10, 13, 15). This function is a classic because its groups touch the corners: the four corners (cells 0, 2, 8, 10) form a single group of four, where B = 0 and D = 0 stay constant, so it reads Bโ€ฒDโ€ฒ. The center block (5, 7, 13, 15) has B = 1 and D = 1: BD. The answer is F = Bโ€ฒDโ€ฒ + BD.

The program draws the grid with matplotlib, shades each group in its own color (so wrap-around groups are still easy to see) and then verifies the answer by comparing the simplified expression with the original list of minterms.

Python Draw and verify a 4-variable K-map

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The picture shows the corner group colored in all four corners. The final line confirms that Bโ€ฒDโ€ฒ + BD is 1 on exactly the eight chosen minterms. Without the map, that algebra would take several steps.

Prime implicants and essential groups

A product term that implies F (it is 1 only where F is 1) is an implicant. An implicant that cannot be made any larger is a prime implicant. In K-map language, the prime implicants are the largest possible groups. A prime implicant that is the only group covering some 1 is essential, and it must be in the answer.

Choosing groups by eye can go wrong when several prime implicants overlap. This program lists all of them mechanically. It represents each product term as a "cube" where 0 and 1 fix a variable and None means the variable is dropped. It keeps the cubes that cover only ones, discards cubes contained in a larger valid cube, marks essential primes, and then finds every minimal cover.

Python Find prime implicants and minimal covers

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The first function gives C + AB, matching the hand reduction. The second has six prime implicants and no essential ones; two different covers, each with three terms, are equally good. That is a warning that a K-map solution is a minimal form, not always the only one. The third reproduces the corner-group answer.

When you group by hand, start with the 1s that have only one possible largest group. Those groups are the essential prime implicants. Then cover the remaining 1s with as few extra groups as possible.

Common mistakes

  • Wrong label order. Writing the columns as 00, 01, 10, 11 breaks adjacency. Always use Gray order.
  • Groups of three or six. Group sizes are powers of two, because each merge removes one variable.
  • Missing the wrap-around. Cells in the first and last columns (or rows) are neighbours, and so are the four corners.
  • Reading the wrong variables. Write down which variable stays constant across the whole group, not just across a pair of cells.
  • Stopping too early. Always check that a group cannot be doubled by including a neighbouring 1.

K-maps are practical up to about 4 or 5 variables. Beyond that, the grid becomes unwieldy and you need an algorithm, which is the topic of The Quine-McCluskey Method. Before that, Don't-Cares and Hazards extends the K-map with cells whose value does not matter.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why are K-map columns labeled 00, 01, 11, 10 instead of 00, 01, 10, 11?

    Adjacent cells must differ in one bit so that grouping them removes exactly one variable.
  2. 2. A group of 4 ones in a 4-variable K-map yields a product term with how many literals?

    A group of 2^k cells removes k variables. A group of four cells removes two, leaving 4 - 2 = 2 literals.
  3. 3. Which cells form a valid group?

    The corners are neighbours through wrap-around, forming a 2x2 block on the doughnut-shaped map. Group sizes must be powers of two and the shape rectangular.
  4. 4. What is an essential prime implicant?

    If a 1 is covered by only one prime implicant, the minimal expression must include that implicant.
  5. 5. A 3-variable K-map for F has ones in the two middle columns (BC = 01 and BC = 11) in both rows. What is F?

    In those columns C is always 1 while A and B take every value, so the group of four reads just C.

Summary

  • A K-map is a truth table in a grid with Gray-coded labels, so adjacent cells differ in one variable.
  • Group rectangles of 1, 2, 4, 8 or 16 ones; groups may overlap and wrap around the edges and corners.
  • Each group gives a product term from the variables that stay constant; a bigger group means fewer literals.
  • Prime implicants are the largest groups; essential ones are the only cover for some 1 and must be used.
  • A function can have several equally minimal covers, and brute-force code can verify any hand result.

Next: Don't-Cares and Hazards.