Karnaugh Maps

Group adjacent 1s to minimize a Boolean function.

The idea

A Karnaugh map is a graphical method for minimizing a Boolean expression.

Any Boolean function can be written directly from its truth table, with one product term for every row whose output is $1$. That expression is correct but usually far longer than necessary, and it shortens by a single rule: $x \cdot y + x \cdot y' = x$. Two terms merge whenever they agree in every variable but one, and the disagreeing variable disappears, because its value made no difference to the result.

A Karnaugh map redraws the truth table as a grid whose rows and columns are ordered so that any two cells sharing an edge differ in exactly one variable — precisely the condition for the terms in those cells to merge.

Minimizing becomes a covering problem: each block of $1$s contributes a product term equal to $1$ exactly on the cells of the block, so once every $1$ is covered, the OR of the recorded terms is exactly $f$.

Algorithm.

Algorithm: K-map Minimization Input: the map of a Boolean function f Output: a minimized expression for f, an OR of product terms 1. pick a 1 that no block covers yet 2. enclose it in the largest rectangular block of 1s containing it whose side lengths are powers of two // blocks may overlap 3. record the block's term: the product of the variables constant across the block, complemented (x') where constant at 0 // a block of 2 drops one variable, a block of 4 drops two 4. if some 1 is uncovered, go to step 1 5. return the OR of the recorded terms // the minimized expression

The map below shows the method for three variables $x, y, z$. The block of four holds only $z$ constant and contributes the term $z$; the block of two holds $x$ and $y$ constant and contributes $x \cdot y$; the minimized expression is $z + x \cdot y$.

Ways to work on it

Not sure where to start? Take the ten-question placement test.