Karnaugh Map

logic

Definition

Karnaugh Map

A Karnaugh map (K-map) is a graphical method for simplifying Boolean expressions. It arranges minterms in a grid where adjacent cells differ by exactly one variable — a Gray code ordering — so that groups of adjacent $1$s correspond to simplified product terms.

Each cell corresponds to one minterm. Cells are adjacent horizontally, vertically, and across edges (the map wraps around toroidally). A group of $2^k$ adjacent $1$s eliminates $k$ variables, producing a simpler product term. The goal is to cover all $1$s with the fewest, largest such groups.

Example

Example

In the map above, two groups cover all $1$s:

• The row $AB=01$ spans all four columns, so $A=0$ and $B=1$ stay fixed, yielding $\overline{A}B$.
• The two rows with $B=1$ and the two edge columns with $D=0$ form a wrapping group of $4$, yielding $B\overline{D}$.

The simplified expression is $f=\overline{A}B+B\overline{D}$.