Boolean Function Minimization Using Karnaugh Maps

Hello! Last lesson, you built a truth table to specify exactly when a Boolean function is 1. A Karnaugh map, or K-map, rearranges those same output values so that opportunities for simplification become visible. In this lesson, you’ll transfer a truth table to a map, group its 1s, and read off a shorter Boolean expression. That shorter expression will be the starting point for the gate implementations in the next lesson.

From truth table rows to neighboring cells

Consider two input combinations that differ only in $B$. If the output is 1 for both, their corresponding product terms can be combined:

The result no longer depends on $B$. A K-map places such combinations in adjacent cells, making this cancellation easier to spot.

For three inputs, one convenient map has $A$ on its rows and $BC$ on its columns:

Each cell represents one truth-table row. For instance, the cell at $A=0,BC=11$ represents $A=0,B=1,C=1$. Copy that row’s output into the cell.

The column order is deliberately 00, 01, 11, 10, not ordinary binary counting order. Each neighboring pair differs in just one bit; this is called Gray-code order. The first and last columns are neighbors too: 00 and 10 differ only in $B$. In a four-input map, both the rows and columns use Gray-code order, and the top and bottom rows are also neighbors.

The following reading develops this layout and explains why a larger region of 1s produces a shorter product term.

Turn groups into an expression

To find a sum-of-products expression, group cells containing 1. A valid group is a rectangle with a power-of-two number of cells: 1, 2, 4, 8, and so on, up to the map’s size. Its sides follow rows and columns, not diagonals. A group may wrap across an edge of the map, and groups may overlap. It must never include a cell whose specified output is 0.

For each group, retain only the inputs whose values are constant throughout that group. Write an uncomplemented variable if its constant value is 1, or a complemented variable if its value is 0. Inputs that change within the group disappear. Finally, OR the group terms together.

The function from the previous lesson gives us a useful example:

Copying its eight truth-table outputs into a K-map gives:

The two 1s in the top row at columns 00 and 01 form a pair. Across that pair, $A=0$ and $B=0$, while $C$ changes. Its term is therefore $\overline{A}\overline{B}$. The two 1s in column 11 form another pair. There, $B=1$ and $C=1$, while $A$ changes, giving $BC$. Together they cover every 1 without covering a 0:

This example also shows how to check your transcription: the map has 1s at precisely the four input combinations that had output 1 in the truth table. If a map cell is misplaced, even flawless grouping will simplify the wrong function.

For another truth-table-to-map walkthrough, watch the three-input example and its four-input extension in the following video.

Wrapping, overlap, and choosing a minimal cover

In a four-input map, the cells at the four corners can form one group. They are not being grouped diagonally: the left and right edges meet, and the top and bottom edges meet. The image below shows this for rows labeled $AB$ and columns labeled $CD$.

That one four-cell group yields $\overline{B}\overline{D}$, rather than four separate four-literal terms. The same principle applies to any group: each time its size doubles, one more input can vary and one more literal drops out.

A practical minimization routine is:

1. Transfer every specified output to the correct Gray-code cell.
2. Find large valid groups of 1s, including groups that wrap across edges. Do not overlook overlap.
3. Include any group needed to cover a 1 that no other largest group can cover.
4. Cover the remaining 1s with as few additional groups as possible; among equally short covers, prefer fewer literals.
5. Write one product term per chosen group, OR the terms, and compare the result with the original truth table.

A group that cannot be enlarged into another all-1 rectangle is called a prime implicant. You do not necessarily need every prime implicant in the final expression: some cover only 1s already covered by other chosen groups. Nor does circling every large-looking group automatically give the shortest expression. The goal is a cover of every 1, with no 0s included and no unnecessary terms.

A few boundary cases are worth keeping straight. A lone 1 that has no suitable neighboring 1 remains a one-cell group and produces a term containing every input. A map containing only 0s represents the constant function $0$; one containing only 1s represents $1$. If a specification explicitly marks an input combination as a don’t-care, you may use that cell as either 0 or 1 when it helps form a larger group. An ordinary 0 is not a don’t-care.

Key takeaways

A K-map preserves the truth table’s behavior while placing input combinations that differ by one bit next to each other. For sum-of-products minimization, group 1s in the largest useful power-of-two rectangles, allowing edge wrapping and overlap. Each group contributes the variables that stay constant within it; the final OR must cover every specified 1 and no specified 0.

Next, you’ll turn a minimized expression into a circuit using basic gates, then explore implementations using only NAND or NOR gates.