You now know that there are many gate-level implementations with the same truth table behavior. In this section, you will learn the methods for deriving a reduced gate-level implementation of a Boolean function in two-level form. This usually yields circuits with minimum delay, although gate counts are typically not minimized.
(
but not always)
means that the simpler expression will also contain fewer Boolean operations.+
0 =
X, written (
X +
0)
D, is the theorem X 1 =
X.+
0 =
X 1D. X 1 =
X +
1 =
1 2D. X 0 =
0 +
X =
X 3D. X X =
X (
X')
' =
X +
X' =
1 5D. X X' =
0 +
Y =
Y +
X 6D. X Y =
Y X (
X +
Y)
+
Z =
X +
(
Y +
Z)
7D. (
X Y)
Z =
X (
Y Z)
=
X +
Y +
Z =
X Y Z (
Y +
Z)
=
X Y +
X Z 8D. X +
(
Y Z)
=
(
X +
Y)
(
X +
Z)
+
X Y' =
X 9D. (
X +
Y)
(
X +
Y')
=
X +
X Y =
X 10D. X (
X +
Y)
=
X (
X +
Y')
Y =
X Y 11D. (
X Y')
+
Y =
X +
Y (
X +
Y +
Z +
...)
' =
X'
Y'
Z'
12D. (
X
Y
Z
...)
' =
X' +
Y' +
Z' +
{(
X1,X2,...,Xn,0,1,+
,' }=
{(
X1',X2',...,Xn',1,0,,+)}
(
X +
Y +
Z +
...)
D =
X
Y
Z
14D. (
X
Y
Z
...)
D =
X +
Y +
Z +
{(
X1,X2,...,Xn,0,1,+
,D)} =
(
X1,X2,...,Xn,1,0,,+)
(
X +
Y)
X' +
Z)
16D. X
Y +
X'
Z =
(
X +
Z)
X' +
Y)
=
X
Z +
X'
Y
Y +
Y
Z +
X'
Z =
X
Y +
X'
Z 17D. (
X +
Y)
Y +
Z)
X' +
Z)
=
(
X +
Y)
X' +
Z)
(
X1,X2,...,Xn,0,1,+
, used in theorems 13 and 15 represents an expression in terms of the variables X1, X2, , Xn, the constants 0, 1, and the Boolean operations +
and
. Theorem 13 states succinctly that, in forming the complement of an expression, the variables are replaced by their complements-that is, 0 is replaced by 1 and 1 by 0, and +
is replaced by and by +
. As another example, let's look at the second simplification theorem:X Y
+
XY'
=
X? X(
Y+
Y')
=
X distributive law(
8)
X(
1)
=
X complementarity theorem(
5)
X=
X÷
identity(
1D)
DeMorgan's Theorem DeMorgan's theorem gives a procedure for complementing a complex function. The complemented expression is formed from the original by replacing all literals by their complements; all 1's become 0's and vice versa, and ANDs become ORs and vice versa. This theorem indicates an interesting relationship between NOR, OR, NAND, and AND:X +
XY
=
X? X1
+
XY
=
X identity(
1D)
X(
1+
Y)
=
X distributive law(
8)
X(
1)
=
X identity(
2)
X=
X÷
identity(
1)
Let's use DeMorgan's theorem to find the complement of the following expression:
Step by step, the complement is formed as follows
Note that duality and DeMorgan's law are not the same thing. The procedure for producing the dual is similar, but the literals are not complemented during the process. Thus, the dual of NOR is NAND (
and vice versa)
; the dual of OR is AND (
and vice versa)
. Remember, any theorem that is true for an expression is also true for its dual.
Example The Full Adder Carry-Out
We can use the laws and theorems just introduced to verify the simplified expression for the full adder's carry-out function. The original expression, derived from the truth table, is
The first step uses theorem 3, the idempotent theorem, to introduce a copy of the term AB Cin. Then we use the commutative law to rearrange the terms:
We next use the distributive law to factor out the common literals from the first two terms:
We apply the complementarity law:
and the identity law:
We can repeat the process for the second and third terms. The steps are: (
1)
idempotent theorem to introduce a redundant term, (
2)
commutative law to rearrange terms, (
3)
distributive law to factor out common literals, (
4)
complementarity theorem to replace with 1, and (
5)
identity law to replace 1 X by X:
The final simplification, using the distributive theorem, complementarity theorem, and identity law, proceeds similarly:
This is exactly the reduced form of the expression we used in Chapter 1. Although it leads to a simpler expression, applying the rules of Boolean algebra in this fashion does not guarantee you will obtain the simplest expression. A more systematic approach will be introduced in Section 2.3.
Boolean Algebra and Switches We have already observed the close correlation between Boolean functions and switching circuits. Each of the laws and theorems we have discussed has a switching circuit analog. These provide a good way to remember the various theorems.
Some of the switch circuit equivalents are shown in Figure 2.13.
To simplify the diagrams, we show only the paths from true to the output. The idempotent theorems are depicted in Figure 2.13(
a)
. Obviously, two identically controlled switches, either in series or in parallel, behave as a single switch, since both are open or closed at the same time.
Figure 2.13(
b)
shows some of the identity laws. An open connection represents logic 0; a shorted connection represents logic 1. An open connection in parallel with a normally open switch has no effect on the switching function and can be eliminated. A shorted connection in parallel with a normally open switch guarantees that a connected path always exists to the output. This leaves the function completely independent of the normally open switch.
The complementarity theorems are shown in Figure 2.13(
c)
. Two switches in parallel, controlled by complementary signals, ensure that one is always open while the other is closed, thus guaranteeing a path to the output. Two switches in series, controlled by complementary signals, guarantee that the connection path is always broken by one of them. This is equivalent to an open connection.
Figure 2.13(
d)
shows the switch equivalents of some simplification theorems. In the first network, the existence of a connection between input and output depends only on X, since Y and are in parallel and one of the switches will be closed while the other is open. If X is true, the connection is made; if X is false, the connection is broken. In the second network, Y's effect is made redundant by the two X switches in parallel.
Figure 2.14 shows a truth table for a function and its complement. The min-term expansions for F and are
We can write such expressions in a shorthand notation using the binary number system to encode the min-terms. Figure 2.15 shows the relationship between the truth table row and the numbering of the min-term.
Note that the ordering of the Boolean variables is critical in deriving the min-term -index. In this case, A determines the most significant bit and C is the least significant bit. You can write the shorthand expression for F and as
where mi represents the ith min-term. The indices generalize for functions of more variables. For example, if F is defined over the variables A, B, C, then m3F (
A,B,C)
=
S m(
3,4,5,6,7)
=
m3+
m4+
m5+
m6+
m7(
A,B,C)
=
S m(
0,1,2)
=
m0+
m1+
m2
(
0112)
is the min-term . But if F is defined over A, B, C, D, then m3 (
00112)
is . The one step you may find tricky is the last one, which applies rule 11D, substituting A for Y and BC for X.
A and BC are called product terms: ANDed strings of literals containing a subset of the possible Boolean variables or their complements. For F defined over the variables A, B, and C, is a min-term and a product term, but BC is only a product term.
Each product term is realized by its own AND gate. The product term A is the degenerate case of a single literal. No AND gate is needed to form this term. The product terms' implementations are then input to a second-level OR gate. The sum of products form leads directly to a two-level realization.
We can repeat the simplification process for but DeMorgan's theorem gives us a good starting point for applying Boolean simplification:
Although this procedure is not guaranteed to obtain the simplest form of the complement, it does so in this case.
Product of Sums The involution theorem states that the complement of a Boolean expression's complement is the expression itself. By using DeMorgan's theorem twice, we can derive a second canonical form for Boolean equations. This form is called the product of sums and sometimes the conjunctive normal form or maxterm expansion.
The procedure for deriving a product of sums expression from a truth table is the logical dual of the sum of products case. First, find the rows of the truth table where the function is 0. A maxterm is defined as an ORed sum of literals in which each variable appears exactly once in either true or complemented form, but not both. We form a maxterm by ORing the uncomplemented variable if there is a 0 in its column for that row, or the complemented variable if there is a 1 there. This is exactly opposite to the way we formed min-terms. There is one maxterm for each 0 row of the truth table; these are ANDed together at the second level.
Once again, we often use a shorthand notation.
Figure 2.17 shows the relationship between maxterms and their shorthand form. We can write F and as
Fwhere Mi is the ith maxterm.(
A, B, C)
=
PM(
0,1,2)
=
M0 M1 M2(
A, B, C)
=
PM(
3,4,5,6,7)
=
M3 M4 M5 M6 M7
Of course, the same is true for deriving the min-term form of F from the maxterm form of
It is easy to translate a product of sums expression into a gate-level realization. The zeroth level forms the complements of the variables if they are needed to realize the function. The first level creates the individual maxterms as outputs of OR gates. The second level is an AND gate that combines the maxterms.
We can find a minimized product of sums form by starting with the minimized sum of products expression of To complement this expression, we use DeMorgan's theorem:
Figure 2.18 shows the four different gate-level implementations for F discussed so far: canonical sum of products (
F1)
, minimized sum of products (
F2)
, canonical product of sums (
F3)
, and minimized product of sums (
F4)
. In terms of gate counts, the product of sums canonical form is more economical than the sum of products canonical form. But the minimized sum of products form uses fewer gates than the minimized product of sums form. Depending on the function, one or the other of these forms will be better for implementing the function.
Conversion Between Canonical Forms We can place any Boolean function in one of the two canonical forms, sum of products or product of sums. It is easy to map an expression in one canonical form into the other. The procedure, using the shorthand notation we already introduced, is summarized here:
(
A,B,C)
=
S m(
3,4,5,6,7)
=
P M(
0,1,2)
(
A,B,C)
=
P M(
0,1,2)
=
S m(
3,4,5,6,7)
F(
A,B,C)
=
S m(
3,4,5,6,7)
F(
A,B,C)
=
P M(
0,1,2)
(
A,B,C)
=
S m(
0,1,2)
(
A,B,C)
=
P M(
3,4,5,6,7)
F(
A,B,C)
=
S m(
3,4,5,6,7)
F(
A,B,C)
=
P M(
0,1,2)
(
A,B,C)
=
P M(
3,4,5,6,7)
(
A,B,C)
=
S m(
0,1,2)
(
for example, "open the garage door")
, you place a positive voltage on the -signal and it is interpreted as a logic 1. An alternative convention is sometimes more convenient, especially when using NAND and NOR gates to implement logic that initiates an event (
enable logic)
or inhibits it from taking place (
disable logic)
. It is called active low or negative logic. In this case, a low voltage is used to denote that a signal is asserted, while the high voltage is used to represent an unasserted signal. Consider Figure 2.20, which shows a truth table expressed in terms of two relative voltages, high and low. Under the interpretation of positive logic, the truth table describes an AND function. But if we interpret the voltage levels according to negative logic, we obtain an OR function instead. This follows because an OR function and an AND function are duals, derived by replacing 0's in one truth table with 1's in the other, and vice versa.
Given a function in positive logic, we can find its equivalent negative logic function simply by applying duality. For example, the dual of the NOR function, is Of course, this is the NAND. We can verify this with the truth tables of Figure 2.21.
Example
Because of the very real possibilities for confusion, designers prefer to avoid mixing positive and negative logic in their designs. However, this is not always possible. For example, a positive logic output, asserted high, might connect to a negative logic input, asserted low. To illustrate this point, let's take an example from the traffic light controller from Chapter 1.
Your task is to define three signals, Change_Lights, Change_Request, and Timer_Expired, such that Change_Lights is asserted whenever -Change_Request and Timer_Expired are asserted. In positive logic/active high notation, the latter two signals should be ANDed to implement Change_Lights. This is shown in Figure 2.22(
a).
.
If you use negative logic, and the signals are to be asserted active low, the AND gate is replaced by its dual, an OR gate. Change_Lights is asserted low only when both Change_Request and Timer_Expired are low. In all other cases, Change_Lights is unasserted high. This is shown in Figure 2.22(
b)
.
It can be confusing to keep track of whether positive or negative logic conventions are being used in a circuit. As an alternative, we adopt a notation that assumes that all gates are positive logic, but we explicitly keep track of whether signals are asserted high or asserted low. A "bubble" is placed on the input or output that is to be asserted low.
To make it easier to follow signal polarity within a schematic, active low input bubbles should be matched with active low output bubbles. Continuing with the example, Figure 2.22(
c)
shows a case with mismatched bubbles. Starting with Figure 2.22(
d)
, we add bubbles to indicate the active low polarity of the three signals. You can see that the inputs and the output of the OR gate do not match the polarity of signals to which they are -attached.
How do we make the polarities match? By DeMorgan's theorem, the following is true:
An OR gate is equivalent to an AND gate with inverted inputs and outputs. By replacing the OR gate in Figure 2.22(
c)
with an AND gate of this kind, we do not change the sense of the logic but neatly match up the signal polarities. This is shown in Figure 2.22(
d)
. The figure clearly indicates that Change_Request and Timer_Expired must both be asserted low to cause the active low Change_Lights signal to become asserted.
Examples Incompletely Specified Functions
Let's consider a logic function that takes as input a binary-coded decimal (
BCD)
digit. BCD digits are decimal digits, in the range 0 through 9, that are represented by four-bit binary numbers, using the combinations 00002 (
0)
through 10012 (
9)
. The other combinations, 10102 (
10)
through 11112 (
15)
, should never be encountered. It is possible to simplify the Boolean expressions for the function if we assume that we do not care about its behavior in these "out of range" cases. Figure 2.23 shows the truth table for a BCD increment by 1 circuit. Each BCD number is represented by four Boolean variables, A B C D. The output of the incrementer is represented by four 4-variable Boolean functions, W X Y Z.
The output functions have the value "X" for each of the input combinations we should never encounter. When used in a truth table, the value X is often called a don't care. Do not confuse this with the value X reported by many logic simulators, where it represents an undefined value or a don't know. Any actual implementation of the circuit will generate some output for the don't-care cases. When used in a truth table, an X simply means that we have a choice of assigning a 0 or 1 to the truth table entry. We should choose the value that will lead to the simplest implementation.
To see that don't cares eventually are replaced by some logic value, let's consider the BCD incrementer truth table. The function Z looks as if it could be realized quite simply as the function If we choose to implement Z in this way, the X's will be replaced by real logic values. Since the inputs 10102 through 11112 will never be encountered by the operational circuit, it shouldn't matter which values we assign to those truth table rows. We choose an assignment that makes the implementation as simple as possible.
Don't Cares and the Terminology of Canonical Forms In terms of the standard S and P notations, min-terms or maxterms assigned a don't care are written as di or Di, respectively. Thus the canonical form for Z is written as
Proper specification of don't cares is critical for the successful operation of many computer-aided design tools that perform minimization of Boolean expressions. The terminology they use is slightly different from that commonly found in the logic design literature, but it is really nothing more than a reformulation of the basic truth table specification.Z =
m0+
m2+
m4+
m6+
m8+
d10+
d11+
d12+
d13+
d14+
d15 Z=
M1 M3 M5 M7 M9 D10 D11 D12 D13 D14 D15
{[
0,1,1,1]
, [
1,0,0,0]}
; its off-set is {[
0,0,0,0]
, [
0,0,0,1]
, [
0,0,1,0]
, [
0,0,1,1]
, [
0,1,0,0]
, [
0,1,0,1]
, [
0,1,1,0]
, [
1,0,0,1]
; and its don't-care set is {[
1,0,1,0]
, [
1,0,1,1]
, [
1,1,0,0]
, [
1,1,0,1]
, [
1,1,1,0]
, [
1,1,1,1]}
.