Karnaugh Maps

A Karnaugh map (K-map) is a truth-table layout in which adjacent cells differ by one variable, so that combining minterms becomes circling power-of-two blocks of 1s. It is the standard hand method for minimizing Boolean functions of up to four variables (sometimes five or six with care). The working tasks are finding a minimal SOP or POS, using don't-cares, and reading essential prime implicants off the map.

Row and column indices are Gray-coded so that neighbours (including wrap-around edges) are adjacent in the Boolean cube.

4-variable labeling convention used here. Rows $AB \in \{00,01,11,10\}$ top to bottom; columns $CD \in \{00,01,11,10\}$ left to right. Cell $(AB,CD)$ holds the truth value of minterm index whose bits are $ABCD$.

With that convention the cell indices are:

IMPERATIVE RULE. Columns 3 and 4 and rows 3 and 4 are swapped relative to binary order; a common error is using binary order, placing $m_2$ in the third column and $m_3$ in the fourth; Gray order requires $m_3$ then $m_2$. Every cell of an $n$-variable map has exactly $n$ neighbours (one per variable), counting wrap-around.

A valid group:

The group's product term keeps only the variables that are constant on the group; changing variables disappear.

Size and literals. A group of $2^k$ cells in an $n$-variable map gives a product of $n - k$ literals: in a 4-variable map a single cell has 4 literals, a pair 3, a quad 2, an octet 1, and the whole map is the constant 1.

Different count: primes, essential primes, minimal covers. Questions ask for each separately. A function can have many prime implicants, none essential, and more than one minimal SOP; see Example 6.

A don't-care cell $X$ (or $d$) may be treated as 0 or 1 to help grouping. It need not be covered. Don't-cares never force a 1 into the function; they only optionally enlarge groups.

Don't-cares can create primes that are never needed. In Figure 1, the quad $A'C'$ (cells 0, 1, 4, 5) is a prime implicant only because it uses $d_1$ and $d_4$; it covers no 1 that the essential primes miss, so the minimal SOP ignores it. The same don't-care may be read as 1 for the SOP and as 0 for the POS; the two minimal circuits can then differ on don't-care inputs, which is allowed.

For this function the prime implicants are $B'D'$ (cells 0, 2, 8, 10, the four corners), $BC'D$ (5, 13), $A'BD$ (5, 7) and $A'C'$ (0, 1, 4, 5, using both don't-cares). Three are essential: $B'D'$ for cell 8, $BC'D$ for cell 13 and $A'BD$ for cell 7. The minimal SOP is

the quad plus two pairs. Figure 1 marks all three and leaves $A'C'$ unlooped.

Group zeros instead of ones; each group becomes a sum term (maxterm-style), and $f$ is the product of those sums. Don't-cares may join 0-groups optionally.

Writing the sum term. For a 0-group, each variable that is constant on the group appears complemented if it is 1 and uncomplemented if it is 0 (the opposite of the SOP rule). Equivalently, minimize $f'$ by grouping the 0s as an SOP, then apply De Morgan.

Example. For Figure 1's function, the 0s are at 3, 6, 9, 11, 12, 14, 15. Grouping them with the don't-cares gives the essential 0-groups $B'D$ (1, 3, 9, 11) and $BD'$ (4, 6, 12, 14), and cell 15 is covered by either $ACD$ or $ABC$. So $f' = B'D + BD' + ACD$ and

7 literals against 8 for the SOP. Here both don't-cares are read as 0, and the POS is the cheaper form.

Related material. A two-level AND-OR circuit has a static-1 hazard when a single input change moves between two adjacent 1-cells that no common group covers: for a short time neither product term is 1 and the output glitches to 0. For $f = AB' + BC$, the cells $AB'C$ and $ABC$ are adjacent but lie in different groups, so with $A = C = 1$ a change of $B$ can glitch. Adding the consensus term $AC$ (redundant for the logic) covers that pair and removes the hazard. The hazard-free SOP therefore covers every pair of adjacent 1s by some single term.

Two 4-variable maps (for $E=0$ and $E=1$) stacked; a group may occupy corresponding cells in both maps, eliminating $E$. Six variables need four maps; errors rise quickly, so Quine-McCluskey is preferred beyond four variables when a tabulation method is allowed.

For $n\le 4$, "all maximal groups" is small enough to list by eye.

Each cell is a vertex of the $n$-cube. A valid group of size $2^k$ is a $k$-dimensional subcube, corresponding to a product of $n-k$ literals. Prime implicants are subcubes not contained in larger subcubes of 1s (and chosen don't-cares). The covering step is set cover, which is NP-hard in general; K-maps keep $n$ tiny so enumeration works.

$f=\sum m(0,1,2,5)$. Map (rows $A$, columns $BC$ Gray $00,01,11,10$):

Essential: $m_2$ only in $A'C'$; $m_5$ only in $B'C$; $m_0$ in both first two. One minimal SOP: $A'C' + B'C$. Check $m_1$ covered by $B'C$.

$f=\sum m(0,2,5,7)+d(1,3)$. Using $d(1,3)$ as 1s makes the whole $A = 0$ row (cells 0 to 3) a quad, $A'$. The 1s at 5 and 7 then join the column quad $\{1, 3, 5, 7\}$, which is $C$. Result $f = A' + C$ (2 literals). Without the don't-cares the best is $A'C' + AC$ (4 literals): the don't-cares halve the cost.

If one 1 sits in exactly one maximal valid group (prime implicant), that group's term is essential and must appear in every minimal SOP.

Zeros at $m(3,7)$ for three variables: the 0-group $\{3, 7\}$ has $B = C = 1$ constant, so its sum term is $(B' + C')$, and $f = B' + C'$. Check with maxterms: $M_3 M_7 = (A + B' + C')(A' + B' + C') = B' + C'$ by the dual combining rule.

$f(A,B,C,D) = \sum m(0, 1, 2, 5, 6, 7, 8, 9, 10, 14)$.

$f = \sum m(2, 3, 5, 7, 8, 10, 12, 13)$ has eight prime implicants, all pairs: $B'CD'$, $BC'D$, $A'CD$, $AC'D'$, $A'B'C$, $A'BD$, $AB'D'$, $ABC'$. Every 1 lies in exactly two of them, so no prime is essential. There are exactly two minimal SOPs, each with 4 terms and 12 literals:

Pick any prime to start, and the rest of that cover is forced.

Common misconceptions.