Simplifying Logic Functions: Minterms, Maxterms, and the Karnaugh Map

Every digital circuit, from a simple adder to a modern processor, starts with a logic function described in a truth table. From there, the engineer needs to find the Boolean expression that implements that function with the smallest possible number of logic gates. Fewer gates mean a smaller, cheaper, and faster circuit.

This article is the practical companion to the previous article Boolean Algebra: the mathematical foundation of digital computing: while that article built the theoretical foundations (postulates, theorems, and identities), this one puts them to work simplifying logic functions. We present three methods: the canonical forms (minterms and maxterms), which translate any truth table directly into an algebraic expression; algebraic simplification, which applies the theorems already studied to reduce terms and literals; and the Karnaugh map, a graphical tool that makes the process visual and systematic, without depending on algebraic intuition.

From the truth table to the expression: canonical forms

#

The two forms presented below, sum of minterms and product of maxterms, are the so-called canonical forms of a logic function: any truth table can be written directly in each of them.

Minterms and the SOP form

#

Consider the majority voter for three voters A, B, C: the output \(F\) is 1 when two or more voters vote 1.

By inspection, we can write one expression for each row where \(F = 1\):

Each of these products contains all three variables (in direct or complemented form). These complete products have a special name:

Each minterm gets an index \(m_i\) equal to the decimal value of the input combination: we read the values of the variables as a binary number and convert it to decimal. For example, the combination A=0, B=1, C=1 forms the binary number \(011_2 = 3_{10}\), so the corresponding minterm is \(m_3\).

The expression above can then be written in compact notation:

Maxterms and the POS form

#

The starting point is \(\bar{F}\), the complement of \(F\). Since \(F = 1\) in combinations 3, 5, 6, and 7, then \(\bar{F} = 1\) in the remaining combinations: 0, 1, 2, and 4. That is:

Now we apply De Morgan to the whole expression of \(\bar{F}\) to recover \(F\):

What is \(\bar{m}_i\)? It is De Morgan applied to a minterm. For example:

Generalizing: the negation of a minterm \(m_i\) is exactly the maxterm \(M_i\), in which the variables that were complemented become direct, and vice versa. Therefore:

In compact notation:

General table of minterms and maxterms (3 variables)

#

Notice the pattern: in the minterm \(m_i\), a variable appears complemented if the corresponding bit of \(i\) is 0, and in direct form if it is 1. In the maxterm \(M_i\) the opposite happens.

For example, row 5 has \(x=1, y=0, z=1\), that is, \(i = 101_2 = 5_{10}\):

• \(m_5 = x\bar{y}z\): x direct (bit 1), y complemented (bit 0), z direct (bit 1)
• \(M_5 = \bar{x}+y+\bar{z}\): x complemented (bit 1), y direct (bit 0), z complemented (bit 1)

Exercises

#

Algebraic simplification

#

With the expression in canonical form in hand, we can apply the postulates and theorems of Boolean algebra to reduce the number of terms and literals. The result is an equivalent but simpler expression.

Karnaugh map

#

To overcome these limitations, the Karnaugh map offers a visual and systematic procedure that leads to the minimal expression in sum of products (or in product of sums), as long as the groups are chosen correctly, without depending on algebraic intuition.

The Gray code: why the order matters

#

2-variable map

#

For \(F(A,B)\), the map is a 2×2 grid:

Example: \(F(A,B) = \bar{A}B + A\bar{B}\)

3-variable map

#

For \(F(A,B,C)\), the map is a 2×4 grid, with the columns labeled by the pair \(BC\) in Gray sequence:

Example: \(F(A,B,C) = \bar{A}\bar{B}\bar{C} + \bar{A}BC + A\bar{B}\bar{C} + ABC\)

The cells \(m_0, m_3, m_4, m_7\) are 1, which is equivalent to \(F(A,B,C) = \sum(0,3,4,7)\).

Next, we will see how these maps let us simplify logic functions.

Simplification rules with Karnaugh

#

Before looking at examples, it is worth systematizing the rules:

The simplification algorithm follows this order:

1. 1

   Isolated cells first

   Minterms with no neighbor equal to 1; they do not simplify, but they are part of the function.
2. 2

   Only one possibility

   Minterms that can belong to only one group; that group is mandatory (an essential prime implicant).
3. 3

   Maximum number of cells

   For the remaining minterms, form the largest possible group (a power of 2).
4. 4

   Avoid redundancy

   If all the minterms of a group have already been covered by previous groups, that group generates a redundant term and must be discarded.

Simplification: 3-variable map

#

Returning to the example \(F(A,B,C) = \sum(0,3,4,7)\) presented above, there are two groups of adjacent cells with value 1. The following figure highlights them:

• Group 1: \(m_0\) and \(m_4\) (column 00, both rows) → \(\bar{B}\bar{C}\)
• Group 2: \(m_3\) and \(m_7\) (column 11, both rows) → \(BC\)

Therefore, the function can be simplified to:

4-variable map

#

For \(F(A,B,C,D)\), the map is a 4×4 grid, with rows labeled by \(AB\) and columns by \(CD\), both in Gray sequence:

The map is toroidal: the edges touch

The Karnaugh map should be imagined as a torus: the first and last columns are adjacent, and the same holds for the first and last rows. This means that the four corners (\(m_0, m_2, m_8, m_{10}\)) also form a valid group!

To understand the geometry, think of folding the rectangle twice: first joining the side edges (forming a cylinder), then joining the circular edges of the cylinder (forming the torus):

The final result, with the minterms placed on the toroidal surface:

Source: Karnaugh map: Wikipedia

The figure below shows how the function \(F(A,B,C,D) = \bar{A}\bar{B}\bar{C}D + \bar{A}\bar{B}C\bar{D} + \bar{A}\bar{B}CD + \bar{A}BC\bar{D} + \bar{A}BCD + A\bar{B}\bar{C}D + AB\bar{C}\bar{D} \) can be simplified using the Karnaugh map:

The filled map, equivalent to \(F = \sum(1,2,3,6,7,9,12)\), is:

The groups identified are:

• Group of 4: \(m_2, m_3, m_6, m_7\), columns \(CD = 10\) and \(CD = 11\), rows \(AB = 00\) and \(AB = 01\); fixed variables \(A = 0\) and \(C = 1\) → \(\bar{A}C\)
• Group of 2 (toroidal): \(m_1, m_9\), column \(CD = 01\), rows \(AB = 00\) and \(AB = 10\) (the top and bottom edges touch on the torus); fixed variables \(B = 0, C = 0, D = 1\) → \(\bar{B}\bar{C}D\)
• Isolated cell: \(m_{12}\), all four neighbors are 0; \(A = 1, B = 1, C = 0, D = 0\) → \(AB\bar{C}\bar{D}\)

5-variable map

#

For \(F(A,B,C,D,E)\), the map grows to 32 cells, beyond the practical limit for manual work, but the structure follows the same principle. We use two 4×4 grids side by side: one for \(A=0\) and another for \(A=1\). In each grid, the rows are labeled by \(BC\) and the columns by \(DE\), both in Gray code (00 → 01 → 11 → 10).

Adjacency works normally within each grid. In addition, there is cross adjacency between the two grids: a cell at position \((i,j)\) of the \(A=0\) grid is adjacent to the cell at the same position of the \(A=1\) grid, since the two differ only in \(A\). Groups can therefore extend across both grids.

For functions with 6 or more variables the K-map becomes impractical; at that point, the Quine-McCluskey method (algorithmic) is the natural alternative.

Don’t-care conditions

#

In many real systems, some input combinations never occur or, if they do, the output does not matter. These conditions are called don’t-care conditions and are marked with X on the map.

The classic example is the BCD decoder (Binary-Coded Decimal): the decimal digits 0 to 9 use only the combinations 0000 to 1001. The combinations 1010 to 1111 (10 to 15) are invalid: they never appear as input. Therefore, the behavior of the output for these cells is irrelevant and can be marked as X.

Worked exercises

#

Ex. 1: \(F(A,B,C) = \sum(0,2,4,5,6)\)

#

On the map below, the two groups are highlighted in color. The red group crosses the side edge, which on the torus is a neighbor of the opposite edge:

• Group of 4 cells (red): \(m_0, m_2, m_4, m_6\) (columns 00 and 10, both rows) → \(\bar{C}\)
• Group of 2 cells (green): \(m_4, m_5\) (row \(A=1\), columns 00 and 01) → \(A\bar{B}\)

Ex. 2: \(F(A,B,C,D) = \sum(3,4,5,7,9,13,14,15)\)

#

The figure below highlights the four groups, each in its own color:

Identifying the essential prime implicants:

Check: \(\{3,7\} \cup \{4,5\} \cup \{9,13\} \cup \{14,15\} = \{3,4,5,7,9,13,14,15\}\) ✓

Ex. 3: \(F(A,B,C,D) = \sum(0,2,5,7,8,10,13,15)\)

#

The figure below shows the two groups: the four corners, in red, and the central block, in green.

• Group of 4 (red): \(m_0, m_2, m_8, m_{10}\) (four corners in columns 00/10, rows 00/10) → \(\bar{B}\bar{D}\)
• Group of 4 (green): \(m_5, m_7, m_{13}, m_{15}\) → \(BD\)

Ex. 4: \(F(A,B,C,D) = \sum(0,2,3,4,6,9,10,11,12,14)\)

#

The figure below highlights the four groups. Cells that belong to more than one group appear with overlapping colors:

Ex. 5: \(F(A,B,C,D) = \sum(0,1,2,4,8,9,10,12,14)\)

#

The figure below highlights the four groups, again with overlapping colors in the shared cells:

In this exercise the four groups are concentrated in a few cells: \(m_0\) belongs to three of them and \(m_8\) to all four, and the overlapping colors of the previous figure are hard to tell apart. The figure below shows the same groups, one per map, with the same colors as the table:

Checking with Python

#

Solving maps by hand is the goal of this article, but the check can be automatic. The SymPy library, which has a whole series here on the site, provides in the sympy.logic module the functions SOPform and POSform: they take the list of minterms and return the minimal expression in each form, the same problem the Karnaugh map solves. The block below checks Ex. 5:

from sympy import symbols
from sympy.logic import SOPform, POSform

A, B, C, D = symbols("A B C D")
minterms = [0, 1, 2, 4, 8, 9, 10, 12, 14]

sop = SOPform([A, B, C, D], minterms)
print(sop)
# (A & ~D) | (~B & ~C) | (~B & ~D) | (~C & ~D)

pos = POSform([A, B, C, D], minterms)
print(pos)
# (~B | ~D) & (~C | ~D) & (A | ~B | ~C)

# Answer obtained with the Karnaugh map
map_answer = (~B & ~C) | (~B & ~D) | (~C & ~D) | (A & ~D)
print(sop.equals(map_answer))
# True

The SOP form is the same as the map’s, just with the terms in a different order. The novelty is the POS form: three terms and 7 literals, against four terms and 8 literals for the SOP. This is exactly the comparison that the note “Which form to implement?” recommends making before choosing the circuit. To get there with the map, it would be enough to group the 0s: \(\{5,7,13,15\}\) gives \(\bar{B}+\bar{D}\), \(\{3,7,11,15\}\) gives \(\bar{C}+\bar{D}\), and \(\{6,7\}\) gives \(A+\bar{B}+\bar{C}\). For an expression already written, instead of a list of minterms, the simplify_logic function from the same module plays the equivalent role.

If you prefer to check without installing anything, Charlie Coleman’s interactive Karnaugh map solver takes the list of minterms, draws the map with the groups, and returns the minimal expression in SOP or POS, all in the browser.

Comparing the methods

#

The two methods presented in this article (algebraic simplification and the Karnaugh map) attack the same problem with very different approaches. The table below compares them and includes the Quine-McCluskey algorithm, a third alternative for computational use that was not detailed here:

The Quine-McCluskey algorithm is essentially the Karnaugh map converted into a tabular procedure: it finds all the prime implicants by systematically comparing minterms and then selects the minimal cover. The central idea is to group the minterms by the number of 1s in their binary representation and compare only adjacent groups, since two minterms can combine only if they differ in exactly one bit, and this implies that the number of 1s differs by exactly one. Because it is deterministic and mechanical, it is the reference for exact minimization (the logic synthesis tools used in industry for large functions usually resort to heuristics, such as Espresso, which gives up the guarantee of an exact minimum to gain speed), but its complexity grows exponentially with the number of variables, making it impractical by hand for large functions.

Conclusion

#

Starting from a truth table, we learned to:

1. Write the canonical form (sum of minterms, SOP, or product of maxterms, POS) directly by inspection.
2. Simplify algebraically, applying the theorems of Boolean algebra in sequence.
3. Use the Karnaugh map to identify groups of adjacent minterms and obtain the minimal expression visually.

The result of each simplification is a more economical digital circuit, with fewer gates and lower power consumption. This process is at the base of the design of all digital hardware.

To go deeper into the theorems and identities used throughout this article, see Boolean Algebra: the mathematical foundation of digital computing.

In the next article of the series, we leave the isolated logic gate behind and move on to the first major subsystem of the machine: the memory hierarchy. We will see how cells, addresses, and buses are organized to store data and instructions, and why every computer combines memories of such different speed, capacity, and cost.

See you then!