How Karnaugh maps work

A Karnaugh map is a truth table drawn so that the rows that can be combined algebraically end up physically next to each other. Understanding why it works avoids the typical mistakes: groups of the wrong size, forgetting that the edges touch or not using don’t cares.

The idea: combine terms that differ in one variable

The whole method relies on one Boolean algebra identity:

X·Y + X·Y' = X·(Y + Y') = X

If two minterms are identical except for one variable, their sum simplifies by removing that variable. For example, A'BC'D (m5) + A'BCD (m7) = A'BD. Applied twice, four minterms that differ in two variables reduce to a product two literals shorter, and so on.

Why Gray order

The map numbers rows and columns in Gray code: 00, 01, 11, 10. Between two consecutive positions only one bit changes, and also between the last and the first (10 → 00). With the usual binary order (00, 01, 10, 11) going from 01 to 10 would change two bits at once and two neighbouring cells could not be combined. Thanks to Gray order, neighbouring cells on the map = minterms that differ in one variable, including those on opposite edges.

Grouping rules

1. Groups contain only ones (or don’t cares) and have 1, 2, 4, 8 or 16 cells.
2. They are rectangular, remembering that the map “wraps” at the edges: the four corners of a 4-variable map form a group.
3. Each group should be as large as possible: a larger group removes more variables.
4. Groups may overlap, and every 1 must be in at least one group.
5. Use as few groups as possible.

To read a group, see which variables keep the same value in all its cells: they form the product (complemented if they are 0). The ones that change disappear.

Prime and essential implicants

A prime implicant is a group that cannot be enlarged any further. It is essential if it covers a 1 that no other prime implicant covers: then it must be in the solution. The practical procedure is:

1. Find the ones that can only be grouped in one way and take those groups (they are essential).
2. With the remaining ones, choose the groups that cover them with the fewest terms.

The site’s minimizer does exactly this, but exhaustively: it computes every prime implicant with the Quine-McCluskey method, takes the essential ones and searches for the best cover for the rest.

When there is more than one minimal solution

F(A,B,C) = Σm(0, 1, 2, 5, 6, 7) has no essential prime implicant: every 1 can be covered in two ways. It is a cyclic case, and it has two equally good solutions:

Both have 3 terms and 6 literals. The minimizer shows the first one. If your solution is the other one, it is also correct; the checking exercise uses this same function.

Don’t cares

A don’t care (X) is an input combination that never occurs or whose output does not matter. It can be treated as 1 if it helps to form a larger group and as 0 otherwise. It does not need to be covered. The digital logic path shows how the don’t cares of a BCD input reduce a prime detector from 4 terms to 2.

Product of sums by grouping zeros

The same map gives a product of sums (POS): group the zeros, which yields an expression for F', and apply De Morgan. For F = Σm(0, 2, 5, 7, 8, 10, 13, 15), the zeros are the cells where B ≠ D:

F' = BD' + B'D   →   F = (B' + D)(B + D')

The result is equivalent to the sum of products B'D' + BD. The site’s minimizer only produces the SOP form, so the POS has to be obtained by hand in this way.

Beyond 4 variables

With 5 or 6 variables you can stack several maps, but adjacencies between maps are easy to miss. Beyond that, tabular methods such as Quine-McCluskey are used: they do not rely on visual inspection and can be programmed.