Algebraic minimization

Section 3.2 Algebraic minimization

A logic equation is an algebraic representation of a truth table. Like a truth table, a logic equation is simplified by identifying logically adjacent product terms and combining them into simplified terms, e.g., \(X Y Z' + X Y Z = X Y\text{.}\)

Boolean algebra.

Logical variables (e.g., \(A, B, C\)), the logic values (0 and 1), and the operations (AND, OR, NOT) have a systematic structure called Boolean algebra. Like high school algebra, Boolean algebra has a number of rules that allow logical expressions to be manipulated and simplified. They are listed in Table 3.2.1, below, and may all be verified with truth tables. Some are familiar from high school algebra, others are unique to Boolean algebra. The final item in the list, DeMorgan’s Rules, is included here for completeness but will be described in a later section.

Table 3.2.1. Rules of Boolean Algebra

Identities with 0 and 1	\(A \cdot 0 = 0\)	\(A + 0 = A\)
	\(A \cdot 1 = A\)	\(A+1=1\)
Double negative	\((A')' = A\)
Idempotent	\(A \cdot A = A\)	\(A + A = A\)
Complementary	\(A \cdot A' = 0\)	\(A+A'=1\)
Commutative	\(A \cdot B = B \cdot A\)	\(A + B = B + A\)
Associative	\(A \cdot B \cdot C = (A \cdot B) \cdot C = A \cdot (B \cdot C)\)	\(A+B+C = (A+B)+C = A+(B+C)\)
Distributive	\(A \cdot (B+C) = A \cdot B + A \cdot C\)	\(A + (B \cdot C) = (A+B) \cdot (A+C)\)
DeMorgan’s Rules	\(\overline{A \cdot B} = \overline{A} + \overline{B}\)	\(\overline{A + B} = \overline{A} \cdot \overline{B}\)

The basic simplification of logically adjacent terms, \(AB + AB'\text{,}\) follows from an application of the distributive law, to factor out the A, and then complementarity, and finally, identity:

\begin{gather*} AB + AB' = A(B + B') = A \cdot 1 = A \end{gather*}

All logic minimization, fundamentally, comes down to this one move: factor and combine.

Examples of algebraic simplification.

The other rules of Boolean algebra are applied in more complex situations to reveal the basic move. See if you can spot the rules that are applied in the following simplification (parentheses for emphasis):

\begin{gather*} ABC + ABC' = (AB)C + (AB)C' = AB(C+C') = (AB)\cdot 1 = AB \end{gather*}

This one has a few more steps:

\begin{align*} ABC + AB'C \amp= A(BC) + A(B'C) = A(CB) + A(CB') = ACB + ACB' \\ \amp= AC(B+B') = AC \cdot 1 = AC \end{align*}

Of course, all the steps between \(ABC + AB'C\) and \(AC(B+B')\) are intuitive by analogy with high school algebra, and don’t need to be written out in such detail (unless you need to in order to be confident of your work).

A trickier situation arises when you have three terms, like this: \(ABC + ABC' + AB'C\text{.}\) You could combine the first two terms, giving

\begin{gather*} ABC + ABC' + AB'C = AB + AB'C \end{gather*}

or the first and third terms, resulting in

\begin{gather*} ABC + ABC' + AB'C = AC + ABC' \end{gather*}

In hardware, both would require the same gates, and neither is preferable to the other. However, there is something special about Boolean algebra that enables an even simpler form to be found. The idempotency rule, \(A + A = A\text{,}\) permits a term in an expression to be copied and used twice:

\begin{align*} ABC + ABC' + AB'C \amp= (ABC + ABC) + ABC' + AB'C\\ \amp= (ABC + ABC') + (ABC + AB'C) = AB(C+C') + AC(B+B')\\ \amp= AB + AC \end{align*}

How about that!

The complementarity rule is helpful when you’re given something like this: \(A + A'B\text{,}\) which, on the face of it, doesn’t look like it can be simplified. But note:

\begin{align*} A + A'B \amp= A \cdot 1 + A'B = A(B+B') + A'B = AB + AB' + A'B\\ \amp= (AB + AB) + AB' + A'B = (AB + AB') + (AB + A'B)\\ \amp= A(B+B') + (A+A')B = A+B \end{align*}

Finally, simplifications can lead to more simplifications, as in this example:

\begin{align*} ABC + ABC' + AB'C + AB'C' \amp= A(BC + BC' + B'C + B'C')\\ \amp= A( B(C+C') + B'(C+C') )\\ \amp = A(B+B') = A \end{align*}

Once you’ve factored out the \(A\text{,}\) every combination of \(B\) and \(C\) is there, and for any choice of \(B\) and \(C\text{,}\) one of them will be true!

All of these examples are variations on the same theme: to simplify a logic expression, look for ways to factor and combine, expanding (with idempotency and complementarity) if necessary to reveal additional combinations. And if you are ever in doubt as to whether your results are correct, you can always resort to a truth table.

Checkpoint 3.2.2.

Minimize the logic equation for the two-bit odd number detector, Checkpoint 1.4.2.

Solution.

Apply the basic factor-combine move,

\begin{equation*} y = \left( \overline{x_1} \cdot x_0 \right) + \left(x_1 \cdot x_0 \right) = \left( \overline{x_1} + x_1\right) \cdot x_0 = x_0 \end{equation*}

Of course, a number is odd if its least=significant bit is 1!

Checkpoint 3.2.3.

Write the full logic equation for the two-input multiplexer, then minimize it using Boolean algebra.

Solution.

The full equation, from the truth table, Checkpoint 1.3.6, is

\begin{equation*} y = S'AB + S'AB' + SA'B + SAB\text{.} \end{equation*}

The minimized equation is

\begin{equation*} y = S'A(B+B') + SB(A+A') = S'A + SB \end{equation*}

Checkpoint 3.2.4.

Write the full logic equation for the two-bit \(x > y\) function, Checkpoint 1.3.4, then minimize it using Boolean algebra. Compare your result with the compressed truth table, Checkpoint 3.1.3

Solution.

From the truth table, the unreduced equation is

\begin{equation*} g = x_1' x_0 y_1' y_0' + x_1 x_0' y_1' y_0' + x_1 x_0' y_1' y_0 + x_1 x_0 y_1' y_0' + x_1 x_0 y_1' y_0 + x_1 x_0 y_1 y_0' \end{equation*}

Look for factorizations, copying terms that can be used twice:

\begin{equation*} g = x_1 y_1' ( x_0' y_0' + x_0' y_1 + x_0 y_1' + x_0 y_1) + (x_1' + x_1) x_0 y_1' y_0' + x_1 y_1' y_0'(x_0' + x_0) \end{equation*}

After combining,

\begin{equation*} g = x_1 y_1' + x_0 y_1' y_0' + x_1 y_1' y_0' \end{equation*}

For comparison, writing an equation from the compressed truth table gives:

\begin{equation*} g = x_1' x_0 y_1' y_0' + x_1 x_0' y_1' + x_1 x_0 y_1' + x_1 x_0 y_1 y_0' \end{equation*}

It isn’t as simple as the one derived from Boolean algebra, and in fact, there appear to be no common terms! But both can be confirmed by going back to the original truth table.

The last exercise was fairly complicated. If you didn’t get my answer, you might have a sinking feeling that Boolean algebra is a difficult path to minimized logic. You might also be dismayed that the result did not match up with the compressed truth table derived previously. Your feelings are justified:

There are multiple ways to pair rows in a truth table to reveal don’t care entries.
It can be very difficult to discover the best simplification by mere inspection of the truth table.
Following the steps of Boolean algebra can also result in multiple results, all logically equivalent, but differing in complexity.

What to do? Once again, it must be emphasized that by-hand manipulation of truth tables and logic equations, while instructive, do not guarantee optimal results and are not how complex digital systems are designed. But before leaving the subject, there is one more by-hand method, that points more directly to computational simplification, and is also kind of fun.

Prev Top Next