Файл: Digital design with CPLD applications and VHDL (R. Dueck, 2000).pdf

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

The distributive property allows us to “multiply through” an AND function across several OR functions. For example,

Theorem 5: x(y z) xy xz

and

Theorem 6: (x y)(w z) xw xz yw yz

Figure 3.23 shows the logic gate equivalents of these theorems.

FIGURE 3.23

Distributive Properties

b. SOP form

Solution The Boolean expression for Figure 3.24a is Y (A B)(C D). Using the distributive property, we get the expression Y A C BC AD 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.

ABDF

b. SOP form

Solution The Boolean expression for Figure 3.25a is AB(C D)(E F). The distributive property can be applied in two stages:

Y (ABC ABD)(E F)

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

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

Multivariable Theorems

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

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

DeMorgan’s Theorems

We have already seen DeMorgan’s theorems. We will list them again, but will not comment further on them at this time.

Theorem 20: xy 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

Solution Figure 3.30 shows the logic circuits for the unsimplified and simplified versions 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):

Since x xy x, (P Q)(S T) (S T) (S T).

W (PQR P Q)(S T) (S T)

Let x S T, let y (PQR P Q)

W x xy x S T

Alternate method:

W (PQR P Q)(S T) (P Q)(S T) (S T)

By the distributive property:

W ((PQR P Q) (P Q))(S T) (S T)

Let x S T, let y ((PQR P Q) (P Q)):

W x xy x S T