A Karnaugh map (K-map) simplifies Boolean logic by arranging truth-table outputs in a grid. You place each 1 in its matching cell, combine adjacent 1s, and write one term for each group. Variables that change inside a group disappear from the resulting expression.
This Karnaugh mapping method uses Gray-code labels, power-of-two groups, overlap, and edge wraparound. The worked example below takes a four-variable function from minterms to its reduced Boolean expression.
How a Karnaugh map is arranged
For four variables, place two variables on the rows and two on the columns. Label both axes in Gray-code order:
- Rows: 00, 01, 11, 10
- Columns: 00, 01, 11, 10
Gray-code order matters because neighboring labels differ by only one bit. For example, 00 and 01 are adjacent, as are 01 and 11. The first and last labels also touch: 00 and 10 are adjacent through the map’s edge. Each cell represents one combination of the input variables, or one minterm.
How a K-map places truth-table values
Consider this function, using the variable order ABCD:
F(A, B, C, D) = Σm(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
Place a 1 in the cells for those minterms and a 0 in every other cell. With AB labeling the rows and CD labeling the columns, the completed K-map is represented as follows:
- Row AB = 00: 1, 1, 1, 1
- Row AB = 01: 1, 1, 1, 1
- Row AB = 11: 0, 0, 0, 0
- Row AB = 10: 1, 1, 1, 1
The values in each row follow the column order CD = 00, 01, 11, 10, not ordinary binary counting. For instance, the cell at row 00 and column 10 represents binary 0010, or minterm 2. The cell at row 10 and column 00 represents binary 1000, or minterm 8.
How to group cells by powers of two, overlap, and wraparound
In a K-map, legal groups contain 1, 2, 4, 8, or 16 cells. Each group must form a rectangle, and diagonal cells are not adjacent. Use the largest useful groups because larger groups remove more variables. You may overlap groups, and every 1 must belong to at least one group.
For this example, make two groups:
- Group 1: Combine rows AB = 00 and AB = 01 across all four columns. This is an eight-cell group. In it, A stays 0 while B, C, and D change.
- Group 2: Combine rows AB = 00 and AB = 10 across all four columns. This is also an eight-cell group. These rows are adjacent because they wrap around the map’s top and bottom edges. Here, B stays 0 while A, C, and D change.
The groups overlap across row AB = 00. That is valid and often useful: a cell can help more than one group produce a simpler result. Do not force each 1 to appear only once.
How to read the simplified expression from the groups
Keep only variables that remain constant within each group. Complement a variable when its constant value is 0:
- Group 1 keeps A = 0, so it produces A′.
- Group 2 keeps B = 0, so it produces B′.
Because the groups cover alternative sets of 1s, join their terms with OR:
F = A′ + B′
This result matches the map: the only row left at 0 is AB = 11, where both A′ and B′ are 0. For a sum-of-products result, group 1s this way; if you instead group 0s, you can derive a product-of-sums expression.