Chapter 1 Basic Principles of Digital Systems outlin e 1

Example 3.9

Distributive Property

❘❙❚ EXAMPLE 3.9 Find the Boolean expression of the POS circuit in Figure 3.24a. Apply the distributive

property to transform the circuit to an SOP form.

FIGURE 3.23

Distributive Properties

distributive property, we get the expression Y _ A_ C_ _ BC_ _ A_D _ BD. The logic diagram

for this expression is shown in Figure 3.24b.

In Example 3.9, we see that the distributive property can be used to convert a POS

circuit to SOP or vice versa. In this case, the circuit was not simplified, just transformed.

❘❙❚ EXAMPLE 3.10 Write the Boolean expression for the circuit in Figure 3.25a. Use the distributive property

to convert this to an SOP circuit.

FIGURE 3.25

Example 3.10

Distributive Property

A B C D

D

E

Y

Y

B

a. POS form

E F

ABCF

ABDF

property can be applied in two stages:

_ ABCE_ _ ABCF_ _ ABDE_ _ ABDF_

The logic diagram for this equation is shown in Figure 3.25b. This results in a network

that is “wider” (more gates on one level), but also “flatter” (fewer levels). The advantage of

the second circuit is that signals would pass through the network faster, since it has fewer

levels of gating. ❘❙❚

Single-Variable Theorems

There are thirteen theorems that can be used to manipulate a single variable in a Boolean

expression. An easy way to remember these theorems is to divide them into three groups:

1. Six theorems: x AND/OR/XOR 0/1

2. Six theorems: x AND/OR/XOR x/ x_

3. One theorem: Double Inversion

The theorems in the first group can be generated by asking what happens when x, a

Boolean variable or expression, is at one input of an AND, an OR, or an XOR gate and a 0

or a 1 is at the other.

Examine the truth table of the gate in question. Hold one input of the gate constant and

find the effect of the other on the output. This is the same procedure we used in Chapter 2

to examine the enable/inhibit properties of logic gates.

Each of these six theorems can be represented by a logic gate, as shown in Figure 3.26.

0 0 0

1 0 0

0 0 0

1 0 1

If x _ 0, Y _ 0

If x _ 1, Y _ 0

(Can never have both inputs HIGH, therefore output is always LOW.)

If x _ 0, Y _ 0

If x _ 1, Y _ 1

(LOW input enables OR gate.)

X AND/OR/XOR 0/1

0 0 0

1 0 1

If x _ 0, Y _ 0

If x _ 1, Y _ 1

(XOR acts as a noninverting buffer.)

0 0 0

1 0 0

0 0 0

1 0 1

If x _ 0, Y _ 0

If x _ 1, Y _ 1

(HIGH input enables AND gate.)

0 0 0

1 0 1

If x _ 0, Y _ 1

If x _ 1, Y _ 1

(One input always HIGH, therefore output is always HIGH.)

If x _ 0, Y _ 1

If x _ 1, Y _ 0

(XOR acts as an inverting buffer.)

Six theorems are generated by combining a Boolean variable or expression, x, with itself or

its complement in an AND, an OR, or an XOR function.

Again, we can use the AND, OR, and XOR truth tables. For the first three theorems,

we look only at the lines where both inputs are the same. For the other three, we use the

lines where the inputs are different.

0 0 0

1 0 1

Figure 3.27 shows the logic gates that represent these theorems.

If x _ 0, Y _ 0

If x _ 1, Y _ 1

Theorem 13: x _ x _ x

x _ x:

A x Y

0 0 0

1 0 1

If x _ 0, Y _ 0

If x _ 1, Y _ 1

Theorem 14: x _ x _ x

x _ x:

If x _ 0, Y _ 0

If x _ 1, Y _ 0

(Output is LOW if neither input is HIGH or if both are.)

0 0 0

1 0 0

X AND/OR/XOR X/X_

If x _ 0, Y _ 1

If x _ 1, Y _ 1

(One input HIGH, but not both.)

Theorem 18: x _x_ _ 1

Double Inversion

The final single-variable theorem is just common sense. It states that a variable or expression

inverted twice is the same as the original variable or expression. It is given by:

Theorem 19: x_ _ x

This theorem is illustrated by the two inverters in Figure 3.28.

Multivariable Theorems

There are numerous multivariable theorems we could learn, but we will look only at five of

the most useful.

3.3 • Theorems of Boolean Algebra 79

x _ x_:

A x Y

0 0 0

1 0 0

0 0 0

1 0 1

If x _ 0, Y _ 0

If x _ 1, Y _ 0

(Since inputs are opposite, can never have both HIGH. Output always LOW.)

0 0 0

1 0 1

If x _ 0, Y _ 1

If x _ 1, Y _ 1

(Since inputs are opposite, one input always HIGH. Therefore, output is always HIGH.)

x x x _ x

Double Inversion

We have already seen DeMorgan’s theorems. We will list them again, but will not comment

further on them at this time.

Theorem 20: x_y_ _ x_ _ y_

Theorem 21: x_____y_ _ x_y_

Other Multivariable Theorems

Theorem 22: x _ xy _ x

Proof:

x _ xy _ x (1 _ y) (Distributive property)

_ x _1 (1 _ y _ 1; Theorem)

_ x

Figure 3.29 illustrates the circuit in this theorem. Note that the equivalent is not a circuit

at all, but a single, unmodified variable. Thus, the circuit shown need never be built.

FIGURE 3.29

Theorem 22

x

y xy

❘❙❚ EXAMPLE 3.11 Simplify the following Boolean expressions, using Theorem 22 and other rules of Boolean

algebra. Draw the logic circuits of the unsimplified and simplified expressions.

a. H _ KL_ _ K

b. Y _ (A_____B_)CD _ (A_____B_)

c. W _ (PQR _ P_ Q_)(S _ T) _ (P_ _ Q_)(S _ T) _ (S _ T)

of the above expressions.

a. Let x _ K, let y _ L_:

H _ x _ xy _ K _ KL_

Theorem 22 states x _ xy _ x. Therefore K _ KL_ _ K.

b. Let x _ (A_____B_), let y _ CD:

Y _ x _ xy _ x _ A_____B_

c. Let x _ S _ T, let y _ (P_ _ Q_):

Let x _ S _ T, let y _ (PQR _ P_ Q_)

By the distributive property:

Let x _ S _ T, let y _ ((PQR _ P_ Q_) _ (P_ _ Q_)):

Example 3.11

Logic Circuits for Unsimplified and Simplified Expressions

❘❙❚

_ (x _ xy) _ xz _ yz (xx _ x; Associative property)

_ x _ xz _ yz (x _ xy _ x (Theorem 22))

_ (x _ xz) _ yz (Associative property)

_ x _ yz (Theorem 22)

Figure 3.31 shows the logic circuits for the left and right sides of the equation for Theorem

23. This theorem is a special case of one of the distributive properties, Theorem 6,

where w _ x.

Theorem 23

❘❙❚ EXAMPLE 3.12 Simplify the following Boolean expressions, using Theorem 23 and other rules of Boolean

algebra. Draw the logic circuits of the unsimplified and simplified expressions.

a. L _ (M _ N_)(M _ P_)

b. Y _ (A_____B_ _ AB)(A_____B_ _ C)

of the above expressions.

Example 3.12

Logic Circuits for Unsimplified and Simplified Expressions

3.3 • Theorems of Boolean Algebra 83

Theorem 23: (x _ y)(x _ z) _ x _ yz

a. Let x _ M, let y _ N_, let z _ P_:

L _ (x _ y)(x _ z) _ x _ yz _ M _ N_ P_

b. Let x _ A_ _ B, let y _ AB, let z _ C:

❘❙❚

_ 1 _ (x _ y) (x _ x_ _ 1)

_ x _ y

Figure 3.33 illustrates Theorem 24 with a logic circuit.

Theorem 24

Here is another way to remember Theorem 24:

If a variable (x) is ORed with a term consisting of a different variable (y) AND the

first variable’s complement (x_), the complement disappears.

x _ x_y _ x _ y

❘❙❚ EXAMPLE 3.13 Simplify the following Boolean expressions, using Theorem 24 and other rules of Boolean

algebra. Draw the logic circuits of the unsimplified and simplified forms of the expressions.

a. W _ U_ _ UV_

b. P _ QR_S _ (Q_ _ R _ S_) T

J _ K_M_ (K_ _ L _ M) _ KM

Solution Figure 3.34 shows the circuits for the unsimplified and simplified expressions.

Theorem 24: x _ x_y _ x _ y

a. Let x _ U_, let y _ V_:

W _ x _ x_y _ x _ y _ U_ _ V_

b. P _ QR_S _ (Q_ _ R _ S_) T

_ QR_S _ QR_S T (DeMorgan’s theorem)

Let x _ QR_S, let y _ T:

N O T E

c. Let x _ KM, let y _ (K_ _ L _ M):

_ K_ _ L _ (M _ KM) (Associative property)

_ K_ _ L _ M (Theorem 22)

❘❙❚

all these rules. The commutative, associative, and distributive properties are the same

Example 3.13

Logic Circuits for Unsimplified and Simplified Expressions

3.3 • Theorems of Boolean Algebra 85

as their counterparts in ordinary algebra. The single-variable theorems can be reasoned

out by your knowledge of logic gate operation. That leaves only five multivariable

theorems.

1. x _ y _ y _ x

2. x _ y _ y _ x

Associative Properties

3. x _ (y _ z) _ (x _ y) _ z

4. x(yz) _ (xy)z

Distributive Properties

5. x(y _ z) _ xy _ xz

6. (x _ y)(w _ z) _ xw _ xz _ yw _ yz

x AND/OR/XOR 0/1

7. x _ 0 _ 0

8. x _ 0 _ x

9. x _ 0 _ x

10. x _ 1 _ x

11. x _ 1 _ 1

12. x _ 1 _ x_

x AND/OR/XOR x/ x_

13. x _ x _ x

14. x _ x _ x

15. x _ x _ 0

16. x _ x__ 0

17. x _ x_ _ 1

18. x _x_ _ 1

Double Inversion

19. x_ _ x

20. x_

_ x_ _ y_

21. x_______y_ _ x_ y_

Other Multivariable Theorems

22. x _ xy _ x

23. (x _ y)(x _ z) _ x _ yz

24. x _x_y _ x _ y

❘❙❚ SECTION 3.3 REVIEW PROBLEMS

3.4 Use theorems of Boolean algebra to simplify the following Boolean expressions.

a. Y _ A_C_ _ (A_ _ C_)D

b. Y _ A_ _ C_ _ ACD

c. Y _ (AB_ _ B_C)(AB_ _ C_)

86 C H A P T E R 3 • Boolean Algebra and Combinational Logic

3.4 Simplifying SOP and POS Expressions

Maximum SOP simplification The form of an SOP Boolean expression that cannot

be further simplified by canceling variables in the product terms. It may be possible

to get a POS form of the expression with fewer terms or variables.

Maximum POS simplification The form of a POS Boolean expression that cannot

be further simplified by canceling variables in the sum terms. It may be possible

to get an SOP form of the expression with fewer terms or variables.

Earlier in this chapter, we discovered that we can generate a Boolean equation from a

truth table and express it in sum-of-products (SOP) or product-of-sums (POS) form.

From this equation, we can develop a logic circuit diagram. The next step in the design

or analysis of a circuit is to simplify its Boolean expression as much as possible, with the

ultimate aim of producing a circuit that has fewer physical components than the unsimplified

circuit.

In Section 3.2, we found the SOP and POS forms of the Boolean expression represented

by Table 3.9. These forms yield the logic diagrams shown in Figures 3.17 and 3.20.

For convenience, the circuits are illustrated again in Figure 3.35. The corresponding algebraic

expressions can be simplified by the rules of Boolean algebra to give us a simpler circuit

in each case.

K E Y T E R M S

Table 3.9 Truth

Table for the SOP and

POS Networks in

Figure 3.35

0 0 0 1

0 1 0 0

1 0 0 1

1 1 0 0

Unsimplified SOP and POS Networks

The sum-of-products and product-of-sums expressions represented by Table 3.9 are:

Y _ A_ B_ C_ _ A_ B C _ A B_ C_ (SOP)

and

The SOP form is fairly easy to simplify:

_ (A_ _ A) B_ C_ _ A_ B C (Distributive property)

_ 1 _ B_ C_ _ A_ B C (x _ x_ _ 1)

_ B_ C_ _ A_ B C (x _ 1 _ x)

Since we cannot cancel any more SOP terms, we can call this final form the maximum

SOP simplification. The logic diagram for the simplified expression is shown in

Figure 3.36.

Simplified SOP Circuit

Two terms in an SOP expression can be reduced to one if they are identical except

for one variable that is in true form in one term and complement form in the other.

Such a grouping of a variable and its complement always cancels.

xyz_ _ xyz _ xy(z_ _ z) _ xy

There is a similar procedure for the POS form. Examine the following expression:

Recall Theorem 23: (x _ y)(x _ z) _ x _ yz.

Let x _ A _ B, let y _ C_, let z _ C.

Y _ (A _ B) _ C_C (Theorem 23)

_ (A _ B) _ 0 (xx_ _ 0)

_ (A _ B) (x _ 0 _ x)

A POS expression can be simplified by grouping two terms that are identical except

for one variable that is in true form in one term and complement form in the other.

(x _ y _ z_)(x _ y _ z) _ (x _ y) _ z_z _ x _ y

Let us use this procedure to simplify the POS form of the previous Boolean expression,

shown again below with the terms numbered for our reference. The numbered value

of each term corresponds to the binary value of the line in the truth table from which it is

derived.

There can be more than one way to simplify an expression. The following grouping of

the numbered POS terms is one possibility.

N O T E

(1)(5): (A _ B _ C_) (A_ _ B _ C_) _ B _ C_

(2)(6): (A _ B_ _ C) (A_ _ B_ _ C) _ B_ _ C

(6)(7): (A_ _ B_ _ C) (A_ _ B_ _ C_) _ A_ _ B_

Combining the above terms, we get the expression:

Y _ (B _ C_)(B_ _ C)(A_ _ B_)

Figure 3.37 shows the logic diagram for this expression. Compare this logic diagram

and that of Figure 3.36 with the unsimplified circuits of Figure 3.35. Since there are no

more cancellations of POS terms possible, we can call this the maximum POS simplification.

We can, however, apply other rules of Boolean algebra and simplify further.

Y _ (B _ C_)(B_ _ C)(A_ _ B_)

_ (B_ _ A_C)(B _ C_) (Theorem 23)

_ B_ B _ B_ C_ _ A_ B C _ A_ C C_ (Distributive property)

_ B_ C_ _ A_ B C (x _ x_ _ 0)

This is the same result we got when we simplified the SOP form of the expression.

To be sure you are getting the maximum SOP or POS simplification, you should be

aware of the following guidelines:

1. Each term must be grouped with another, if possible.

2. When attempting to group all terms, it is permissible to group a term more than once,

such as term (6) above. The theorems x _ x _ x (POS forms) and x _ x _ x (SOP forms)

imply that using a term more than once does not change the Boolean expression.

3. Each pair of terms should have at least one term that appears only in that pair. Otherwise,

you will have redundant terms that will need to be canceled later. For example,

another possible group in the POS simplification above is terms (5) and (7). But since

both these terms are in other groups, this pair is unnecessary and would yield a term you

would have to cancel.

❘❙❚ EXAMPLE 3.14 Find the maximum SOP simplification for the Boolean function represented by Table 3.10.

Draw the logic diagram for the simplified expression.