A Karnaugh map (K-map) is a visual arrangement of truth-table outputs used to simplify Boolean expressions. It groups adjacent cells with an output of , allowing changing variables to be eliminated and producing a simpler expression with fewer logic gates.
How a Karnaugh Map Works
For input variables, a K-map contains cells, with one cell for every possible input combination. The rows and columns use Gray code, so only one input variable changes between horizontally or vertically adjacent cells.
After transferring the truth-table outputs into the map, group adjacent s into the largest possible rectangular groups. Each group must contain a power-of-two number of cells, such as , , , or .
| Rule | Purpose |
|---|---|
| Make groups as large as possible | Eliminates more variables |
| Use powers-of-two group sizes | Ensures variables change systematically |
| Allow groups to overlap | Can produce a simpler final expression |
| Treat opposite edges as adjacent | Reflects the Gray-code arrangement |
| Include every at least once | Ensures all true outputs are represented |
Within each group, retain only variables whose values remain constant. Variables that change are removed.
K-maps usually produce a minimized sum-of-products (SOP) expression: each group becomes an AND term, and the terms are joined using OR. If a question provides don't-care conditions, they may be treated as either or , but only when doing so creates larger groups.
For example, suppose a two-variable function is true for inputs , , and :
On the K-map, grouping with gives , because changes. Grouping with gives , because changes. Therefore:
This simplified expression requires fewer logic gates, reducing circuit complexity.
Exam Technique
In IB Computer Science A1.2, show the completed K-map, clearly draw the groups, and derive one Boolean term from each group. A common misconception is that diagonal cells are adjacent; they are not. Only horizontal, vertical, and wraparound edge adjacency is valid.
