Page 60 - DCAP108_DIGITAL_CIRCUITS_AND_LOGIC_DESIGNS

Unit 4: Minimization of Boolean Algebra

Unlike a truth table, in which the input values typically follow a standard binary sequence Notes
(00, 01, 10, 11), the Karnaugh map’s input values must be ordered such that the values for adjacent
columns vary by only a single bit, for example, 00, 01, 11, and 10. This ordering is known as a
Gray code. We use a Karnaugh map to obtain the simplest possible Boolean expression that
describes a truth table.
In this section we will examine some Karnaugh maps for three and four variables. As we use
them be particularly tuned in to how they are really being used to simplify Boolean functions.

4.1 Minterms and Maxterms

Any Boolean expression may be expressed in terms of either minterms or maxterms. To do this
we must first define the concept of a literal. A literal is a single variable within a term which may
or may not be complemented. For an expression with N variables, minterms and maxterms are
defined as follows:

• A minterm is the product of N distinct literals where each literal occurs exactly once.
• A maxterm is the sum of N distinct literals where each literal occurs exactly once.
The establish a formal procedure for minterms for comparison to the new procedure for maxterms.
Figure 4.1: Comparison of Minterms and Maxterms

A minterm is a Boolean expression resulting in 1 for the output of a single cell, and 0s for all other
cells in a Karnaugh map, or truth table. If a minterm has a single 1 and the remaining cells as 0s,
it would appear to cover a minimum area of 1s. The illustration above left shows the minterm
ABC, a single product term, as a single 1 in a map that is otherwise 0s. We have not shown the 0s
in our Karnaugh maps up to this point, as it is customary to omit them unless specifically needed.
Another minterm A’BC’ is shown in Figure 4.1 right. The point to review is that the address of
the cell corresponds directly to the minterm being mapped. That is, the cell 111 corresponds to
the minterm ABC above left. The minterm A’BC’ corresponds directly to the cell 010. A Boolean
expression or map may have multiple minterms.
Referring to the Figure 4.1, let’s summarize the procedure for placing a minterm in a K-map:

• Identify the minterm (product term) to be mapped.
• Write the corresponding binary numeric value.

• Use binary value as an address to place a 1 in the K-map
• Repeat steps for other minterms (P-terms within a Sum-Of-Products).

LOVELY PROFESSIONAL UNIVERSITY 55