Skip to main content

Discrete Mathematics for Computer Science: An open educational resource.

Ken Levasseur, Al Doerr, Michiel Smid, Oscar Levin, Charles M. Grinstead, J. Laurie Snell, Eric Lehman, F. Thomson Leighton, Albert R Meyer, Jeff Erickson, Kenneth P. Bogart, Carol Chritchlow, David Eck, OpenDSA Project, L.J. Miller

Section 12.8 Logic Circuit Minimization

Let’s start with a logic circuit and see how the laws of boolean algebra can help us simplify it.

Example 12.8.1. Simplification of a circuit.

Consider the circuit in Figure 12.8.2. As usual, we assume that three inputs enter on the left and the output exits on the right.
Complex gate diagram
Figure 12.8.2. Initial gate diagram
If we trace the inputs through the gates we see that this circuit realizes the boolean function
\begin{equation*} f\left(x_1, x_2, x_3 \right)=x_1 \cdot \overline{x_2}\cdot \left(\left( x_1 + x_2\right) + \left(x_1 + x_3\right)\right). \end{equation*}
We simplify the boolean expression that defines \(f\text{,}\) simplifying the circuit in so doing. You should be able to identify the laws of Boolean algebra that are used in each of the steps. See Exercise 12.7.1.
\begin{equation*} \begin{split} x_1 \cdot \overline{x_2}\cdot \left(\left( x_1 + x_2\right) + \left(x_1 + x_3\right)\right) & = x_1 \cdot \overline{x_2}\cdot \left(x_1+ x_2 + x_3\right)\\ & = x_1 \cdot \overline{x_2} \cdot x_1 + x_1 \cdot \overline{x_2} \cdot x_2 + x_1 \cdot \overline{x_2} \cdot x_3 \\ &= x_1\cdot \overline{x_2} + 0 \cdot x_1 + x_3 \cdot x_1 \cdot \overline{x_2}\\ &=x_1 \cdot \overline{x_2} + x_3 \cdot x_1 \cdot \overline{x_2} \\ &= x_1 \cdot \overline{x_2} \cdot \left(1 + x_3\right)\\ &= x_1 \cdot \overline{x_2} \end{split} \end{equation*}
Therefore, \(f\left(x_1, x_2, x_3\right)=x_1 \cdot \overline{x_2}\text{,}\) which can be realized with the much simpler circuit in Figure 12.8.3, without using the input \(x_3\text{.}\)
Simplified gate diagram
Figure 12.8.3. Simplified gate diagram
Next, we start with a table of desired outputs based on three bits of input and design an efficient circuit to realize this output.

Example 12.8.4.

Consider the following table of desired outputs for the three input bits \(x_1, x_2, x_3\) .
Table 12.8.5. Desired output table
\(x_1\) \(x_2\) \(x_3\) \(f(x_1,x_2,x_3)\)
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 0
1 0 0 1
1 0 1 1
1 1 0 0
1 1 1 0
A circuit diagram for this function is Figure 12.8.6. But is this the simplest circuit that realizes the table? See Exercise 12.8.3.
Circuit diagram of the desired table of outputs
Figure 12.8.6. A realization of the table of desired outputs.

Exercises Exercises for Section 12.8

1.

List the laws of boolean algebra that justify the steps in the simplification of the boolean function \(f\left(x_1, x_2, x_3\right)\) in Example 12.8.1. Some steps use more than one law.
Answer.
  1. Associative, commutative, and idempotent laws.
  2. Distributive law.
  3. Idempotent and complement laws.
  4. Null and identity laws
  5. Distributive law.
  6. Null and identity laws.

2.

Write the following Boolean expression in the notation of logic design.
\begin{equation*} \left(x_1\land \overline{x_2}\right)\lor \left(x_1\land x_2\right)\lor \left(\overline{x_1}\land x_2\right). \end{equation*}
Answer.
\begin{equation*} (x_1\cdot \overline{x_2})+(x_1\cdot x_2)+(\overline{x_1} \cdot x_2). \end{equation*}

3.

Find a further simplification of the boolean function in Example 12.8.4, and draw the corresponding gate diagram for the circuit that it realizes.
Answer.
A simpler boolean expression for the function is \(\overline{x_2} \cdot (x_1 + x_3)\text{.}\)
Diagram of simplified circuit with 3 gates
Figure 12.8.7. An even simpler circuit

4.

Consider the switching circuit in Figure 12.8.8.
Switching circuit diagram
Figure 12.8.8. Can this circuit be simplifed?
  1. Draw the corresponding gate diagram for this circuit.
  2. Construct a table of outputs for each of the eight inputs to this circuit.
  3. Determine the minterm normal of the Boolean function based on the table.
  4. Simplify the circuit as much as possible.

5.

Consider the circuit in Figure 12.8.9 .
Circuit diagram with 4 gates
Figure 12.8.9. Can this circuit be simplifed?
  1. Trace the inputs though this circuit and determine the Boolean function that it realizes.
  2. Construct a table of outputs for each of the eight inputs to this circuit.
  3. Find the minterm normal form of \(f\text{.}\)
  4. Draw the circuit based on the minterm normal form.
  5. Simplify the circuit algebraically and draw the resulting circuit.

6.

Consider the Boolean function \(f\left(x_1, x_2, x_3, x_4\right)=x_1 + \left(x_2 \cdot \left(\overline{x_1} + x_4\right) + x_3 \cdot \left(\overline{x_2} + \overline{x_4}\right)\right).\)
  1. Simplify \(f\) algebraically.
  2. Draw the gate diagram based on the simplified version of \(f\text{.}\)
PrevTopNext