Chapter 4 Problem Solutions 4.1. W 0 0 0 0

Chapter 4 Problem Solutions 4.1. w

x

y

z

f

(a)

(b)

(c)

(d)

(e)

(f)

(g)

(h)

0

0

0

0

0

0

0

0

0

0

1

1

0

0

0

0

1

0

0

1

0

0

0

1

1

0

0

0

1

0

0

0

1

0

0

0

1

1

0

0

0

1

1

0

0

1

0

0

0

0

1

0

0

1

0

0

0

0

0

1

0

0

1

1

0

0

1

0

1

1

0

1

1

0

0

1

1

1

0

1

1

0

0

0

1

1

0

1

1

1

0

0

1

1

1

0

0

1

1

0

0

0

1

0

1

0

0

0

1

1

0

1

0

0

1

1

0

1

0

0

1

1

0

1

1

1

0

1

1

0

1

0

1

0

1

1

1

1

0

0

1

1

0

1

0

1

1

1

0

1

1

1

0

1

1

0

1

1

0

0

1

1

0

1

0

0

1

1

0

1

1

0

1

0

0

1

1

0

0

1

0

0

1

1

1

0

1

1

1

1

0

1

1

1

0

1

1

1

1

0

0

1

1

0

0

1

0

0

- is an implicant since it implies f. However, neither (a) wz - are implicants. Therefore, wz the term w nor the term z is a prime implicant (1). (b) y+z is neither an implicant or implicate (6). (c) w+x is an implicate since it is implied by f.

However,

nether the term w nor the term x are implicates. Therefore, w+x is a prime implicate (3).

- 4.1 -

4.1. (continued) -z is an implicant since it implies f. (d) wx - which is also an implicant. subsumes wx

-z However, wx -z Therefore, wx

is an implicant, but not prime (2). - is neither an implicant or implicate (6). (e) xyz -+y -+z - is an implicate since it is implied by f. (f) w -+y -+z - subsumes w+y - which is also an implicate. However, w -+y -+z - is an implicate, but not prime (4). Therefore, w -+x -+z - is an implicate since it is implied by f. (g) w -+x -, -, and - are Furthermore, none of the sum terms w w+z x+z -+x -+z - is a prime implicate (3). implicates. Therefore, w -xy -z is an implicant since it implies f. However, none (h) w -xy -, --z are of the product terms w wxz, w yz, and xy implicants.

-xy -z is a prime implicant (1). Therefore, w

4.2. (a)

(b)

- 4.2 -

4.2. (continued) (c)

(d)

(e)

(f)

4.3. The Karnaugh map is

- 4.3 -

4.3. (continued) The implicants correspond to all possible subcubes of 1cells. one-cell subcubes (minterms) wxyz

two-cell subcubes

four-cell subcubes

wxy wxz

wy

wxyz wxyz

wyz

-z wxy -yz wx

wxy -y wx

-yz wx wxyz

xyz

wxyz

wyz wyz

The prime implicants correspond to those subcubes which are not properly contained in some other subcube of 1-cells.

The prime implicants are shown on the map. ---yz -. wxy, w xz, w yz, and x

- 4.4 -

They are wy,

4.4. (a)

-z, yz -, x -The prime implicants are xz, xy, y z, and xy. There are no essential prime implicants.

(b)

-x, xz, w -The prime implicants are w yz, and wyz.

All four

prime implicants are essential as a result of the essential 1-cells indicated by asterisks.

- 4.5 -

4.4. (continued) (c)

-The prime implicants are w x, w __, z x __, z and x __. y

The

essential prime implicants are underlined.

(d)

-- x The prime implicants are y z, __, xy __, z and w ___. xz essential prime implicants are underlined.

- 4.6 -

The

4.5. (a)

-+y+z and x+y -+z -. The prime implicates are x

Both prime

implicates are essential. (b)

-+z, x+z, w+x+y -, and w -+x+y. The prime implicates are w All three prime implicates are essential.

- 4.7 -

4.5. (continued) (c)

-+x -, -+y+z -. The prime implicates are w x+z, and w

All three

prime implicates are essential. (d)

- _____, -+y -+z w -+x -+y -, and w -+y -+z -. The prime implicates are x+z ___, x The essential prime implicates are underlined.

- 4.8 -

4.6. (a)

Minimal sum: f = x + z Minimal product: f = x + z (b)

Minimal sums: - + x -y + xz f = xy - + x -y + yz f = xy Minimal product: -+y -+z) f = (x+y)(x

- 4.9 -

4.6. (continued) (c)

Minimal sum: --z + y -z + xyz f = x y + x Minimal product: -+z)(x -+y+z)(x -+y -+z -) f = (x+y (d)

Minimal sum: --yz f = y z + x Minimal products: -)(y -+z)(x -+z -) f = (y+z -)(y -+z)(x -+y -) f = (y+z

- 4.10 -

4.7. (a)

Minimal sum: f = x + yz Minimal product -) f = (x+y)(x+z (b)

Minimal sum: - + y + z f = x Minimal product: - + y + z f = x

- 4.11 -

4.7. (continued) (c)

Minimal sum: -f = x z + yz Minimal product: -)(x -+z) f = (y+z (d)

Minimal sum: -f = y + x z Minimal product: -+y)(y+z -) f = (x

- 4.12 -

4.8. (a)

Minimal sum: --f = xy + w xy + x yz Minimal products: -+y)(x+y -)(w -+y+z -) f = (x -+y)(x+y -)(w -+x+z -) f = (x (b)

Minimal sum: - + wz + x -yz f = xz Minimal products: -+z -)(w+x+y) f = (x+z)(w+x -+z -)(w+y+z -) f = (x+z)(w+x

- 4.13 -

4.8. (continued) (c)

Minimal sum: -z + yz + w -xz f = wz + x Minimal product: -+z)(x+z)(w+x -+y+z -) f = (w (d)

Minimal sums: --xy + wxz + wx -f = w xz + w y --z + xyz + w -yz f = x yz + wy

- 4.14 -

4.8. (continued)

Minimal products: -)(w+x -+y)(w -+x -+z)(w -+x+y -) f = (w+x+z -+y+z)(w+y+z -)(x+y -+z -)(w -+y -+z) f = (x (e)

Minimal sum: -f = x z + yz + wy Minimal products: -)(x -+y -+z)(w+x -+y) f = (w+y+z -)(x -+y -+z)(w+x -+z) f = (w+y+z

- 4.15 -

4.8. (continued) (f)

Minimal sum: --z + wz + x -y f = w x + y Minimal product: -+z)(w+x -+y -)(w -+y+z) f = (x (g)

Minimal sum: -z + xy -f = yz + x z Minimal product: -+z)(x -+y+z -) f = (x+z)(y

- 4.16 -

4.8. (continued) (h)

Minimal sums: - + xz + w -f = xy xy + wyz - + wx + w -yz + x -yz f = xy

Minimal product: -+x+z -)(w+x -+y -+z) f = (x+y)(w

- 4.17 -

4.8. (continued) (i)

Minimal sum: - + x ----z f = wx z + x y + w yz + wy Minimal product: -+y -)(w+x -+z -)(w+y -+z -)(w -+x -+z) f = (x

(j)

Minimal sum: - + x -y + wyz + w -xz f = wx Minimal products: -+z -)(w -+x -+z)(w -+x -+y) f = (w+x+y)(w+x -+z -)(w -+x -+z)(x -+y+z -) f = (w+x+y)(w+x

- 4.18 -

4.9. (a)

Minimal sums: --yz - + wx --xy f = w xz + xyz + x yz + w --yz - + wx --yz f = w xz + xyz + x yz + w Minimal products: -+y)(w -+y+z)(x+y -+z -)(w -+x -+z)(w+x+z -) f = (x -+y)(w -+y+z)(x+y -+z -)(w -+x -+z)(w+y+z -) f = (x (b)

Minimal sum: --x + w -f = x y + w z Minimal product: -+x -)(w -+y -)(x+y -+z -) f = (w

- 4.19 -

4.9. (continued) (c)

Minimal sum: --xy + w -f = x yz + xyz + w yz Minimal products: -)(x -+y+z)(w -+y+z -)(w -+y -+z) f = (x+y -)(x -+y+z)(w -+y+z -)(w -+x -+z) f = (x+y (d)

Minimal sum: -z + w -z + x -z + f = y wxy Minimal product: -+z)(y -+z)(w -+x -+y -) f = (x+z)(w

- 4.20 -

4.9. (continued) (e)

Minimal sums: --f = xyz + xy z + wy z + wxyz + wxy --f = xyz + xy z + wy z + wxyz + wxz Minimal products: -)(x -+y+z -)(w+x+z)(w+y -+z)(w -+x+z -) f = (x+y -)(x -+y+z -)(w+x+z)(w+y -+z)(w -+y+z -) f = (x+y (f)

Minimal sums: --y f = y z + wz + w -- + yz f = w z + wy

- 4.21 -

4.9. (continued)

Minimal product: -)(w -+y -+z) f = (w+y+z (g)

Minimal sum: -z + wy - + xz f = wx + y Minimal product: -) f = (w+z)(x+y

- 4.22 -

4.9. (continued) (h)

Minimal sums: -- + yz f = x z + xz + wy -- + xy f = x z + xz + wy Minimal product: -)(x+y -+z -)(w+x -+y+z) f = (w+x+z

(i)

Minimal sum: -z + wz f = x Minimal product: -+z -)(w+z) f = (x

- 4.23 -

4.9. (continued) (j)

Minimal sums: --f = x y + w y + wxz + xyz --z + w -xz - + wxy f = x y + y

Minimal product: -)(w+y -+z -)(w -+x -+y+z) f = (x+y

- 4.24 -

4.10. (a)

-The prime implicants are x __, z w y, xz __, and wy.

The

essential prime implicants are underlined.

-+z and x+z -. The prime implicates are x implicates are essential.

- 4.25 -

Both prime

4.10. (continued) (b)

-z, and wz -. The prime implicants are x, w

All three

prime implicants are essential.

-+x+z - and w -+y -+z -. The prime implicates are w+z ___, w _____, essential prime implicates are underlined.

- 4.26 -

The

4.10. (continued) (c)

-, w The prime implicants are wx __, yz __, y and xy.

The

essential prime implicants are underlined.

The prime implicates are w+y ___, x+y, w ___, +x and x+z. essential prime implicates are underlined.

- 4.27 -

The

4.11. (a)

Minimal sum: --f = x z + xyz + w yz Minimal product: -+z)(w -+y+z -)(x+y -+z -) f = (x (b)

Minimal sum: - + x -yz f = wy Minimal products: -+y -)(w+z -) f = (w+y)(x -+y -)(y -+z -) f = (w+y)(x

- 4.28 -

4.11. (continued) (c)

Minimal sum: -z + xz + wz f = y Minimal product: -+z -) f = (w+z)(x+y

(d)

Minimal sums: f = wx + wz + yz f = wx + wz + xz f = wx + wz + xy Minimal product: f = (x+z)(w+y)

- 4.29 -

4.11. (continued) (e)

Minimal sums: -f = x z + yz --f = x z + w z Minimal products: -(x -+y) f = z -(w -+x -) f = z (f)

Minimal sum: - + x -z + w -xz - + wy f = wx Minimal product: -+z -)(w -+x -+y -) f = (w+x+z)(w+x

- 4.30 -

4.11. (continued) (g)

Minimal sum: -- + w -xy f = x z + wy Minimal product: -+x -+y -)(x+y -+z -) f = (w+y)(w

(h)

Minimal sum: -y + xy - + y -z + xz f = w Minimal products: -+x+y -)(x -+y -+z) f = (x+y+z)(w -+x+y -)(w -+y -+z) f = (x+y+z)(w

- 4.31 -

4.11. (continued) (i)

Minimal sum: --z + wyz - + w -x f = w y + y Minimal product: -+y+z)(w+x+y -)(w -+y -+z -) f = (w (j)

Minimal sums: -z + wz - + w -xy f = w -z + wz - + xy -f = w z

- 4.32 -

4.11. (continued) Minimal products: -+z -)(y -+z)(w+x+y) f = (w -+z -)(y -+z)(w+x+z) f = (w

4.12. (a)

Minimal sums: -x + wx -y + wz f = w -x + wx -y + y -z f = w Minimal products: -+x -+y -) f = (y+z)(w+x)(w -+x -+z) f = (y+z)(w+x)(w

- 4.33 -

4.12. (continued) (b)

Minimal sums: -f = wx y + wyz + wxy f = wxy + wyz + xyz Minimal products: -)(w+z)(w -+x -+y)(y -+z -) f = (x+y -)(w+z)(w -+x -+y)(w+y -) f = (x+y

(c)

Minimal sum: --f = x z + w y + wxz Minimal product: -)(w -+x -+z)(w+x -+y -) f = (x+z

- 4.34 -

4.12. (continued) (d)

Minimal sums: --xz - + wxy f = w xz + w -- + xy -f = w xz + wxz z Minimal product: -+z -)(w -+y -) f = (x+z)(x

(e)

- 4.35 -

4.12. (continued) Minimal sums: --z + w -f = w y + y x f = wy + yz + xy Minimal product: -+z)(x -+y -) f = (w

(f)

Minimal sum: - + w -y + x -f = xz yz Minimal product: -+z -)(x+y+z)(w -+x+y -) f = (x

- 4.36 -

4.12. (continued) (g)

Minimal sum: --f = wx + w xy + wy z + xz Minimal products: -+z -)(w -+x+y -)(w -+x+z -) f = (w+y)(w+x -+z -)(w -+x+y -)(x+y+z -) f = (w+y)(w+x (h)

Minimal sum: -y + wz - + w -xz f = w

- 4.37 -

4.12. (continued) Minimal products: -+z -)(w+y+z)(w+x+y) f = (w -+z -)(w+y+z)(x+y+z -) f = (w (i)

Minimal sum: -f = xy + xz + wyz + wy z Minimal products: -)(w -+y -+z) f = (w+x)(w+y+z)(x+y+z -)(x+y -+z) f = (w+x)(w+y+z)(x+y+z (j)

- 4.38 -

4.12. (continued) Minimal sum: - + w -f = xy + wz yz Minimal product: -)(w -+y+z -) f = (w+z)(x+y

4.13.

To construct f2: If g=1 and f1=1, then f2=1. If g=0 and f1=0, then f2=-. If g=0 and f1=1, then f2=0. (Note: g=1 and f1=0 can not occur if the problem is solvable.) Using the above rules, the map for f2 is:

- 4.39 -

4.13. (continued) Minimal sum: - +w -z f2 = xy Minimal products: -+z)(w -+x) (Shown above) f2 = (x+z)(y Other possible minimal products: -+z)(w -+y -) f2 = (x+z)(y -+y -)(w -+x) f2 = (x+z)(x -+y -)(w -+y -) f2 = (x+z)(x

4.14. (a)

Minimal sums: -- + v -wx -z f = v yz + vwy + vxy -- + wx -yz f = v yz + vwy + vxy

- 4.40 -

4.14. (continued)

Minimal product: -)(v+z)(v -+x+y)(v+x -+y -) f = (w+y

(b)

Minimal sum: -wy - + vw -f = yz + v yz + vwxy

- 4.41 -

4.14. (continued)

Minimal products (shown above): -+w -+y)(v+y -+z)(w+y -+z)(x+y -+z)(v+w+y)(v -+y+z -) f = (v -+w -+y)(v+y -+z)(w+y -+z)(x+y -+z)(v+w+y)(w+y+z -) f = (v Another minimal product (not shown): -+w -+y)(v+y -+z)(w+y -+z)(x+y -+z)(w+y+z -)(v+w+z) f = (v (c)

Minimal sums (shown above): - + --- + v -wxy + f = vwz wxz + vy z + v wxy vxyz - + --- + v -wxy + f = vwz wxz + vy z + v wxy vwyz

- 4.42 -

4.14. (continued) Another minimal sum (not shown): - + --- + v -wyz + wxyz f = vwz wxz + vy z + v wxy

Minimal product: -+y)(v -+w -+z -)(w+x -+y -)(v -+x -+z -)(w+y -+z) f = (v+x+z)(v+w

(d)

Minimal sum: -z + y -z + wx -y + vwy f = w

- 4.43 -

4.14. (continued)

Minimal product: -+x -+y -)(v+y+z) f = (w+z)(w

4.15.

- 4.44 -

4.15. (continued) Minimal sums: -wz - + uvw - + f = v vwx + uvz -wz - + uvw - + f = v vwx + uwz

Minimal product: -)(w -+z -)(v+w+x) f = (u+v

- 4.45 -

4.16. x

y

z

f

0

0

0

0

0

0

1

0

0

1

0

0

0

1

1

1

1

0

0

0

1

0

1

1

1

1

0

1

1

1

1

1

Minimal sum (cost=9): f = xy + xz + yz Minimal product (cost=9): f = (x+y)(x+z)(y+z) Realization using the minimal sum:

- 4.46 -

4.17.

Minimal sum (cost=20): -z + xyz - + -p = wz + xy xyz + w xyz Minimal product (cost=20): -+z)(x -+y+z)(x -+y -+z -)(x+y -+z)(w+x+y+z -) p = (w Comparing Tables 3.10 and 3.12, it is seen that if the don't-cares for wxyz=1010, 1100, and 1111 are assigned values of logic-1, the two tables become identical. Since Table 3.10 is describable by the expression -rx)r(yrz), this same expression can be used for p=(w Table 3.12. 4.18. Truth table: xi

yi

ci

ci+1

si

0

0

0

0

0

0

0

1

0

1

0

1

0

0

1

0

1

1

1

0

1

0

0

0

1

1

0

1

1

0

1

1

0

1

0

1

1

1

1

1

- 4.47 -

4.18. (continued) For the ci+1 output:

Minimal sum (cost=9): ci+1 = xiyi + xici + yici Minimal product (cost=9) ci+1 = (xi+yi)(xi+ci)(yi+ci) For the si output:

Minimal sum (cost=16): - y - si = xiyici + x i ici + xiyici + xiyici Minimal product (cost=16) - +c - si = (xi+yi+ci)(xi+y i i)(xi+yi+ci)(xi+yi+ ci) However, - y - si = xiyici + x i ici + xiyici + xiyici - (y - = x xi(y i ici+yici) + ici+ yici) _______ = xi(yir ci) + xi(yir ci) = xi r (yir ci)

- 4.48 -

4.18. (continued) Realization:

4.19. Truth table: xi

yi

bi

bi+1

di

0

0

0

0

0

0

0

1

1

1

0

1

0

1

1

0

1

1

1

0

1

0

0

0

1

1

0

1

0

0

1

1

0

0

0

1

1

1

1

1

- 4.49 -

4.19. (continued) For the bi+1 output:

Minimal sum (cost=9): - y + x - b + y b bi+1 = x i i i i i i Minimal product (cost=9): - +y )(x - +b )(y +b ) bi+1 = (x i i i i i i For the di output:

Minimal sum (cost=16): - y - di = xiyibi + x i ibi + xiyibi + xiyibi Minimal product (cost=16): - +b - di = (xi+yi+bi)(xi+y i i)(xi+yi+bi)(xi+yi+bi) However, - y - di = xiyibi + x i ibi + xiyibi + xiyibi -(y - b +y - = x xi(y i i ibi) +_______ ibi+yibi) = xi(yir bi) + xi(yir bi) = xi r (yir bi)

- 4.50 -

4.19. (continued) Realization:

- 4.51 -

4.20. 8

4

2

1

w

x

y

z

f

0

0

0

0

0

0

0

0

1

0

0

0

1

0

0

0

0

1

1

0

0

1

0

0

0

0

1

0

1

0

0

1

1

0

0

0

1

1

1

0

1

0

0

0

0

1

0

0

1

0

Minimal sum (cost=6):

1

0

1

0

1

f = wx + wy

1

0

1

1

1

1

1

0

0

1

1

1

0

1

1

1

1

1

0

1

1

1

1

1

1

Minimal product (cost=4): f = w(x+y)

Realization:

- 4.52 -

4.21. Let: F=1 when the pressure in the fuel tank is equal to or above a required minimum. F=0 when the pressure in the fuel tank is below a required minimum. X=1 when the oxidizer tank pressure is equal to or above a required minimum. X=0 when the oxidizer tank pressure is below a required minimum. T=1 when there are 10 min. or less to lift off. T=0 when there are more than 10 min. to lift off. P=1 when the panel light is on. P=0 when the panel light is off. From the problem statement we can write the equation for the panel light to be on: -XT - + X -P = FXT + F T

Minimal sum (cost=10): --P = X T + F T + FXT Minimal product (cost=10): -)(X+T -)(F -+X -+T) P = (F+T

- 4.53 -

4.21. (continued) Realization using the minimal sum:

4.22. Let w, x, y, and z denote the bits of the 2421 code groups and A, B, C, and D denote the bits of the 8421 code groups where w and A are the most significant bits of their respective code groups. w

x

y

z

A

B

C

D

0

0

0

0

0

0

0

0

0

0

0

1

0

0

0

1

0

0

1

0

0

0

1

0

0

0

1

1

0

0

1

1

0

1

0

0

0

1

0

0

0

1

0

1

-

-

-

-

0

1

1

0

-

-

-

-

0

1

1

1

-

-

-

-

1

0

0

0

-

-

-

-

1

0

0

1

-

-

-

-

1

0

1

0

-

-

-

-

1

0

1

1

0

1

0

1

1

1

0

0

0

1

1

0

1

1

0

1

0

1

1

1

1

1

1

0

1

0

0

0

1

1

1

1

1

0

0

1

- 4.54 -

4.22. (continued)

- + wx B = xy -+y -) B = (w+x)(x

A = xy

- + w -y C = wy -+y -) C = (w+y)(w

(cost=6) (cost=6)

- 4.55 -

D = z

(cost=6) (cost=6)

4.23. 7

5

3

6

w

x

y

z

f

0

0

0

0

1

0

0

0

1

-

0

0

1

0

1

0

0

1

1

-

0

1

0

0

0

0

1

0

1

-

0

1

1

0

0

0

1

1

1

1

1

0

0

0

0

1

0

0

1

1

1

0

1

0

-

1

0

1

1

0

1

1

0

0

-

1

1

0

1

0

1

1

1

0

-

1

1

1

1

0

- 4.56 -

4.23. (continued) Minimal sum (cost=10): --z + x -f = w x + w yz Minimal products (cost=12): -+z)(w -+z)(w -+y -)(w -+x -) f = (x -+z)(w -+z)(w -+y -)(x -+y) f = (x Realization:

- 4.57 -

4.24. Inputs

Outputs

8

4

2

1

w

x

y

z

a

b

c

d

e

f

g

0

0

0

0

1

1

1

1

1

1

0

0

0

0

1

0

1

1

0

0

0

0

0

0

1

0

1

1

0

1

1

0

1

0

0

1

1

1

1

1

1

0

0

1

0

1

0

0

0

1

1

0

0

1

1

0

1

0

1

1

0

1

1

0

1

1

0

1

1

0

1

0

1

1

1

1

1

0

1

1

1

1

1

1

0

0

0

0

1

0

0

0

1

1

1

1

1

1

1

1

0

0

1

1

1

1

1

0

1

1

1

0

1

0

-

-

-

-

-

-

-

1

0

1

1

-

-

-

-

-

-

-

1

1

0

0

-

-

-

-

-

-

-

1

1

0

1

-

-

-

-

-

-

-

1

1

1

0

-

-

-

-

-

-

-

1

1

1

1

-

-

-

-

-

-

-

-a = w + y + xz + x z

- 4.58 -

- + b = x yz + yz

4.24. (continued)

- + z c = x + y

- + -z d = w + yz xy + xz + xy

-e = x z + yz

-- + xz f = w + y z + xy

- 4.59 -

4.24. (continued)

- + g = w + xy xy + yz

or

- + g = w + xy xy + xz

4.25. (a) wxyz

wxyz

wxyz

0

0000 T

0,2

00-0 T

0,2,8,10

-0-0 A

2

0010 T

0,4

0-00 T

0,4,8,12

--00 B

4

0100 T

0,8

-000 T

8,10,12,14

1--0 C

8

1000 T

2,3

001- D

3

0011 T

2,10

-010 T

10

1010 T

4,12

-100 T

12

1100 T

8,10

10-0 T

13

1101 T

8,12

1-00 T

14

1110 T

10,14

1-10 T

12,13

110- E

12,14

11-0 T

The prime implicants are: -A: x z -B: y z C: wz -D: w xy E: wxy - 4.60 -

4.25. (continued) (b) vwxyz

vwxyz

vwxyz

4

00100 T

4,5

0010- T

4,5,6,7

001-- A

5

00101 T

4,6

001-0 T

10,14,26,30

-1-10 B

6

00110 T

5,7

001-1 T

9

01001 E

6,7

0011- T

10

01010 T

6,14

0-110 C

7

00111 T

10,14

01-10 T

14

01110 T

10,26

-1010 T

19

10011 F

14,30

-1110 T

26

11010 T

26,30

11-10 T

30

11110 T

30,31

1111- D

31

11111 T

The prime implicants are: -A: v wx B: wyz -xyz C: v D: vwxy -wx -E: v yz -F: vw xyz

- 4.61 -

4.25. (continued) (c) wxyz

wxyz

wxyz

4

0100 T

4,12

-100 C

9,11,13,15

1--1 A

9

1001 T

9,11

10-1 T

12,13,14,15

11-- B

12

1100 T

9,13

1-01 T

7

0111 T

12,13

110- T

11

1011 T

12,14

11-0 T

13

1101 T

7,15

-111 D

14

1110 T

11,15

1-11 T

15

1111 T

13,15

11-1 T

14,15

111- T

The prime implicants are: A: wz B: wx -C: xy z D: xyz (d) wxyz

wxyz

wxyz

0

0000 T

0,1

000- T

0,1,2,3

00-- A

1

0001 T

0,2

00-0 T

1,3,5,7

0--1 B

2

0010 T

1,3

00-1 T

2,3,6,7

0-1- C

3

0011 T

1,5

0-01 T

5

0101 T

1,9

-001 D

6

0110 T

2,3

001- T

9

1001 T

2,6

0-10 T

10

1010 T

2,10

-010 E

12

1100 F

3,7

0-11 T

7

0111 T

5,7

01-1 T

6,7

011- T

- 4.62 -

4.25. (continued) The prime implicants are: -A: w x -z B: w -y C: w -D: x yz E: xyz -F: wxy z 4.26. (a) vwxyz

vwxyz

vwxyz

1

00001 T

1,3

000-1 T

1,3,17,19

-00-1 A

3

00011 T

1,17

-0001 T

6,14,22,30

--110 B

6

00110 T

3,11

0-011 D

10,11,14,15

01-1- C

10

01010 T

3,19

-0011 T

12

01100 T

6,14

0-110 T

17

10001 T

6,22

-0110 T

20

10100 T

10,11

0101- T

24

11000 G

10,14

01-10 T

11

01011 T

12,14

011-0 E

14

01110 T

17,19

100-1 T

19

10011 T

20,22

101-0 F

22

10110 T

11,15

01-11 T

15

01111 T

14,15

0111- T

29

11101 H

14,30

-1110 T

30

11110 T

22,30

1-110 T

- 4.63 -

4.26. (continued) The prime implicates are: A: w+x+z -+y -+z B: x -+y C: v+w -+z D: v+x+y -+x -+z E: v+w -+w+x -+z F: v -+w -+x+y+z G: v -+w -+x -+y+z H: v (b) wxyz

wxyz

wxyz

0

0000 T

0,2

00-0 T

0,2,8,10

-0-0 A

2

0010 T

0,4

0-00 T

0,4,8,12

--00 B

4

0100 T

0,8

-000 T

4,5,12,13

-10- C

8

1000 T

2,3

001- D

3

0011 T

2,10

-010 T

5

0101 T

4,5

010- T

10

1010 T

4,12

-100 T

12

1100 T

8,10

10-0 T

13

1101 T

8,12

1-00 T

5,13

-101 T

12,13

110- T

The prime implicates are: A: x+z B: y+z -+y C: x D: w+x+y

- 4.64 -

4.27. (a) wxyz

wxyz 4

0100 T

4,5

010- A

5

0101 T

4,12

-100 B

12

1100 T

5,7

01-1 C

7

0111 T

12,14

11-0 D

14

1110 T

7,15

-111 E

15

1111 T

14,15

111- F

-xy A: w -B: xy z

m4

m5

×

×

m7

m12

×

-xz C: w D: wxz

m14

m15

× ×

× ×

E: xyz

×

×

F: wxy

× ×

×

p = (A+B)(A+C)(C+E)(B+D)(D+F)(E+F) = (B+AD)(C+AE)(F+DE) = (BC+ABE+ACD+ADE)(F+DE) = BCF + BCDE + ABEF + ABDE + ACDF + ACDE + ADEF + ADE = BCF + ADE + BCDE + ABEF + ACDF There are five irredundant disjunctive normal formulas: -f1 = B + C + F = xy z + wxz + wxy -xy - + wxz - + xyz f2 = A + D + E = w -- + xyz f3 = B + C + D + E = xy z + wxz + wxz -xy - + xy -f4 = A + B + E + F = w z + xyz + wxy - + wxy f5 = A + C + D + F = wxy + wxz + wxz The costs of f1 and f2 are 12; while the costs of f3, f4, and f5 are 16. sums.

Therefore, f1 and f2 are minimal

- 4.65 -

4.27. (continued) (b) wxyz

wxyz

wxyz

0

0000 T

0,4

0-00 T

0,4,8,12

--00 A

4

0100 T

0,8

-000 T

4,5,12,13

-10- B

8

1000 T

4,5

010- T

8,9,10,11

10-- C

3

0011 T

4,12

-100 T

8,9,12,13

1-0- D

5

0101 T

8,9

100- T

9

1001 T

8,10

10-0 T

10

1010 T

8,12

1-00 T

12

1100 T

3,7

0-11 E

7

0111 T

3,11

-011 F

11

1011 T

5,7

01-1 G

13

1101 T

5,13

-101 T

9,11

10-1 T

9,13

1-01 T

10,11

101- T

12,13

110- T

m4 A: B: C: D:

-y z xy

m5

× ×

m9

×

m12

m13

×

×

wx wy

G: wxz

m8

×

×

×

×

×

×

×

×

×

(Note: Prime implicants E and F do not appear in the prime-implicant table since they do not cover any of the minterms having functional values of 1.)

- 4.66 -

4.27. (continued) p = (A+B)(B+G)(A+C+D)(C+D)(A+B+D)(B+D) = (A+B)(B+G)(C+D)(B+D) = (B+AG)(D+BC) = BD + BC + ADG + ABCG = BD + BC + ADG There are three irredundant disjunctive normal formulas: - + wy f1 = B + D = xy - + wx f2 = B + C = xy -- + w -xz f3 = A + D + G = y z + wy The costs of f1 and f2 are 6 and the cost of f3 is 10. Therefore, f1 and f2 are minimal sums.

4.28. (a) wxyz

wxyz

4

0100 T

4,5

010- B

8

1000 T

8,9

100- C

3

0011 T

3,11

-011 D

5

0101 T

5,13

-101 E

9

1001 T

9,11

10-1 T

11

1011 T

9,13

1-01 T

13

1101 T

11,15

1-11 T

14

1110 T

13,15

11-1 T

15

1111 T

14,15

111- F

- 4.67 -

wxyz 9,11,13,15

1--1 A

4.28. (continued) M3 -+z w -+y B: w+x -+x+y C: w

M4

M5

M8

A:

-+z D: x+y -+y+z E: x

×

M9

M11

M13

×

×

×

M14

M15 ×

× ×

×

×

× ×

×

-+x -+y F: w

×

×

p = DB(B+E)C(A+C)(A+D)(A+E)F(A+F) = BCDF(A+E) = ABCDF + BCDEF There are two irredendant conjunctive normal formulas: -+z -)(w+x -+y)(w -+x+y)(x+y -+z -)(w -+x -+y -) f1 = ABCDF = (w -+y)(w -+x+y)(x+y -+z -)(x -+y+z -)(w -+x -+y -) f2 = BCDEF = (w+x The cost of f1 is 19 and the cost of f2 is 20. Therefore, f1 is the minimal product. (b) wxyz

wxyz 0

0000 T

0,8

-000 B

8

1000 T

8,9

100- C

5

0101 T

5,7

01-1 T

6

0110 T

5,13

-101 T

9

1001 T

6,7

011- D

7

0111 T

9,13

1-01 E

13

1101 T

7,15

-111 T

15

1111 T

13,15

11-1 T

- 4.68 -

wxyz 5,7,13,15

-1-1 A

4.28. (continued) M0 A:

M6

-+z x

B: x+y+z -+x+y C: w

M7

M8

M9

× ×

× × ×

-+y D: w+x -+y+z E: w

M13

×

×

× ×

×

p = BD(A+D)(B+C)(C+E)(A+E) = BD(C+E)(A+E) = BD(E+AC) = BDE + ABCD There are two irredundant conjunctive normal formulas: -+y -)(w -+y+z -) f1 = BDE = (x+y+z)(w+x -+z -)(x+y+z)(w -+x+y)(w+x -+y -) f2 = ABCD = (x The cost of f1 is 12 and the cost of f2 is 15. Therefore, f1 is the minimal product. 4.29. (a) Referring to Table P4.29a, c2 dominates c1, c6 dominates c1, c6 dominates c2, c3 dominates c7, and c5 dominates c7. Deleting the dominating columns c2, c3, c5, and c6, the table reduces to c1

c4

r1 r2 r4

r7

cost

×

3

×

4

×

4

r5 r6

c7

× ×

4 6

×

6

(Note: r3 no longer appears since it has no crosses in the remaining columns.)

- 4.69 -

4.29. (continued) r1 equals r5, r2 equals r7, and r4 equals r6. Deleting those rows with the higher costs, i.e., r5, r6, and r7, the table becomes c1

c4

**r1

cost

± ×

3

× ±

**r2 **r4

c7

4

± ×

4

Since only single crosses exist in each column, the minimal cover consists of rows r1, r2, and r4. (b) Referring to Table P4.29b, r3 is an essential prime implicant since c11 has a single cross. Therefore, r3 must be selected and r3 and c11 can be deleted from the table.

Also, c1 dominates c8, c2 dominates c5, c9 dominates c3, and c10 dominates c6. Thus, columns c1, c2, c9, and c10 are deleted. The table now reduces to c3 r1

c4

c5

×

×

r2

c6

c7

c8

×

3

×

3

r4

×

r5

×

r6

×

×

× ×

r9

×

4 4 5

r7 r8

cost

× ×

Minimal cover: {r3,...}

- 4.70 -

×

6 7 7

4.29. (continued) r1 now dominates r5, r1 dominates r6, r8 dominates r2, r7 dominates r4, and r5 dominates r6. Rows r5 and r6 are deleted since they have a higher cost than their dominating rows.

However, r2 and r4 cannot be deleted since they have a lower cost than their dominating rows.

The resulting table is

c3 **r1

c4

c5

± ×

×

c6

c7

c8

×

r2

3

×

3

r4 r7

×

r8

×

r9

×

cost

×

4

×

6

×

7

×

7

Minimal cover: {r3,...} Since column c4 has a single cross, row r1 is selected to appear in the minimal cover. After deleting row r1 and columns c4, c5, and c7, the table reduces to c3 r2

c6

c8

cost

×

3

r4

×

4

r7

×

6

r8

×

r9

×

×

7 7

Minimal cover: {r1,r3,...}

- 4.71 -

4.29. (continued) r4 equals r7 and the cost of r4 is less than the cost of r7. Therefore, delete r7. Also, r8 dominates r9. r9 is deleted since it has equal cost. The table becomes

c3 r2

c6 ×

± ×

× ±

cost 3

**r4 **r8

c8

×

4 7

Minimal cover: {r1,r3,...} Finally, since columns c3 and c8 have single crosses, rows r4 and r8 must appear in the minimal cover. This completes the covering of the prime-implicant table. The minimal cover consists of rows r1, r3, r4, and r8. (c) Referring to Table P4.29c, c5 dominates c1, c2 equals c6, and c3 dominates c7. Deleting c3, c5, and c6, the table reduces to

c1 r1

c2

c4

c7

×

3

r2

×

r3

×

r4

×

r7

×

×

×

r5 r6

cost

×

4 4

×

5

×

5 6

×

- 4.72 -

7

4.29. (continued) r6 dominates r1, but cost prevents deleting r1. However, since r2 dominates r5, r2 dominates r7, r3 dominates r7, and r4 dominates r5, and since the dominated rows have a greater or equal cost than the dominating rows, delete r5 and r7. becomes

c1 r1

c2

c7

cost

×

3

r2

×

r3

×

r4

×

r6

c4

×

The table now

×

4

×

4 ×

5

×

6

The resulting table cannot be reduced any further. Petrick's method should be applied. p = (r1+r6)(r3+r4+r6)(r2+r3)(r2+ r4) = (r6+r1r3+r1r4)(r2+r3r4) = r2r6 + r3r4r6 + r1r2r3 + r1r3r4 + r1r2r4 + r1r3r4 = r2r6 + r3r4r6 + r1r2r3 + r1r3r4 + r1r2r4 Irredundant

cost

cover r2, r6 r3, r4, r6 r1, r2, r3 r1, r3, r4 r1, r2, r4

10 15 11 12 12

The minimal cost cover consists of rows r2 and r6. - 4.73 -

4.30. wxyz

wxyz

m3 A

2

0010 T

2,3

001- A

4

0100 T

2,10

-010 B

3

0011 T

4,5

010- C

5

0101 T

4,12

-100 D

10

1010 T

3,7

0-11 E

12

1100 T

5,7

01-1 F

7

0111 T

10,14

1-10 G

14

1110 T

12,14

11-0 H

15

1111 T

7,15

-111 I

14,15

111- J

m4

m5

m7

m14

m15

cost 4

×

C

×

D

×

F

m12

×

B

E

m10

4

×

4 ×

× ×

×

4

×

4

G

×

H I

4

×

×

4

×

4

×

J

×

×

4

×

4

Row E dominates row A and row G dominates row B. all rows have equal cost, delete rows A and B. reduced table is

- 4.74 -

Since The

4.30. (continued) m3

m4

m5

C

×

×

D

×

**E

m7

m10

m12

m14

m15

4 ×

± ×

F

×

4

×

4

×

4 ± ×

**G H

×

I

cost

×

4

×

4

×

J

×

×

4

×

4

Select prime implicants E and G for a minimal sum since columns m3 and m10 each have a single cross. Delete rows E and G as well as the columns having crosses in these rows.

The reduced table becomes

m4

m5

C

×

×

D

×

F

m12

m15

cost 4

×

4

×

H

4 ×

4

I

×

4

J

×

4

Minimal sum: f = E + G + ... Row C dominates row F, row D dominates row H, and rows I and J are equal.

Since all rows have the same cost,

delete rows F, H, and J.

The resulting table is

- 4.75 -

4.30. (continued) m4

m5

**C

×

± ×

**D

×

m12

m15

cost 4

± ×

4 × ±

**I

4

Minimal sum: f = E + G + ... Since columns m5, m12, and m15 each have a single cross, rows C, D, and I are selected for a minimal sum. Furthermore, by selecting these rows, all the columns of the above table are covered.

The minimal sum is

f = C + D + E + G + I -xy - + xy -- + xyz = w z + wyz + wyz (Note: If row I was deleted since it was equal to row J, then the minimal cover would consist of rows C, D, E, G, and J.

Applying Petrick's method to the

original prime-implicant table would result in 16 minimal sums of which only 2 are readily found when using table reduction procedures.)

- 4.76 -

4.31. 1 T

1,3 (2) C

8,9,12,13 (1,4) A

8 T

1,9 (8) D

8,10,12,14 (2,4) B

3 T

8,9 (1) T

6 T

8,10 (2) T

9 T

8,12 (4) T

10 T

3,7 (4) E

12 T

6,7 (1) F

7 T

6,14 (8) G

13 T

9,13 (4) T

14 T

10,14 (4) T 12,13 (1) T 12,14 (2) T

Prime implicants: wxyz A: 1-0- 6 wy B: 1--0 6 wz C: 00-1 6 wxz D: -001 6 xyz wyz E: 0-11 6 F: 011- 6 wxy G: -110 6 xyz

- 4.77 -

4.31. (continued) m1

m8

m9

A

×

×

*B

×

C

×

D

×

m3

m6

m10

m12

m14

× ± ×

3

×

×

×

3 4

×

E

cost

4

×

4

F

×

G

×

4 ×

B is an essential prime implicant.

4

Selecting row B and

deleting the columns having crosses in row B, the table reduces to m1

m3

m6

m9

cost

×

3

A C

×

D

×

E

×

4 ×

×

4 4

F

×

4

G

×

4

Minimal sum: f = B + ... Even though row D dominates row A, row A cannot be deleted because of cost. are equal.

Row C dominates row E and rows F and G

Since these rows have the same cost, delete

rows E and G.

The table becomes

- 4.78 -

4.31. (continued) m1

m3

m6

m9

cost

×

3

A **C

×

D

×

± ×

4 ×

4

× ±

**F

4

Minimal sum: f = B + ... Since columns m3 and m6 have single crosses, rows C and F must be selected. After deleting rows C and F and the columns having crosses in these rows, the reduced table is

m9

cost

A

×

3

D

×

4

Minimal sum: f = B + C + F + ... Row D can be eliminated since it is equal to row A and has a higher cost.

This results in the table

**A

m9

cost

×

3

Minimal sum: f = B + C + F + ... Selecting row A, the minimal sum is - + wz - + -xy f = A + B + C + F = wy wxz + w (Note: At an earlier point, row F could have been deleted since it was equal to row G.

In this case, a minimal

sum is - + wz - + w --) f = A + B + C + G = wy xz + xyz

- 4.79 -

4.32. xyz

xyz 0 2 3 5 6 7

000 f1 _ f3 010 _ f2f3 011 f1 _ f3 101 f1f2 _ 110 _ f2f3 111 f1 _ _

F

0,2 (2)

T

2,3 (1)

G

2,6 (4)

H

3,7 (4)

T

5,7 (2)

T

f1 m0 B:

-x z -y x

C:

yz

D:

yz

A:

xz -F: x yz -yz G: x

m3

f2 m5

m7

m2

m5

f3 m6

m0

m2

×

× ×

× ×

E:

-z H: xy

0-0 _ _ f3 A 01- _ _ f3 B -10 _ f2f3 C -11 f1 _ _ D 1-1 f1 _ _ E

×

m3

m6

×

×

×

× ×

×

×

× ×

× ×

×

p = F1(D1+G1)(E1+H1)(D1+E1)C2H2C2(A3+F3)(A3+B3+C3)(B3+G3)C3 = F1C2H2C3(D1+G1)(E1+H1)(D1+E1)(A3+F3)(B3+G3) = F1C2H2C3(D1+G1)(E1+D1H1)(A3+F3)(B3+G3) = F1C2H2C3(D1E1+D1H1+E1G1+D1G1H1)(A3B3+A3G3+B3F3+F3G3) = F1C2H2C3(D1E1A3B3+D1E1A3G3+D1E1B3F3+D1E1F3G3+D1H1A3B3 +D1H1A3G3+D1H1B3F3+D1H1F3G3+E1G1A3B3+E1G1A3G3 +E1G1B3F3+E1G1F3G3)

- 4.80 -

4.32. (continued) = A3B3C2C3D1E1F1H2 + A3C2C3D1E1F1G3H2 + B3C2C3D1E1F1F3H2 + C 2C3D1E1F1F3G3H2 + A3B3C2C3D1F1H1H2 + A 3C2C3D1F1G3H1H2 + B3C2C3D1F1F3H1H2 + C 2C3D1F1F3G3H1H2 + A3B3C2C3E1F1G1H2 + A 3C2C3E1F1G1G3H2 + B3C2C3E1F1F3G1H2 + C 2C3E1F1F3G1G3H2 Product terms

Distinct terms

Input terminals (E"i+G$j)

A3B3C2C3D1E1F1H2

7

8 + 16 = 24

A3C2C3D1E1F1G3H2

7

8 + 17 = 25

B3C2C3D1E1F1F3H2

6

8 + 14 = 22

C2C3D1E1F1F3G3H2

6

8 + 15 = 23

A3B3C2C3D1F1H1H2

6

8 + 14 = 22

A3C2C3D1F1G3H1H2

6

8 + 15 = 23

B3C2C3D1F1F3H1H2

5 *

8 + 12 = 20 *

C2C3D1F1F3G3H1H2

5 *

8 + 13 = 21

A3B3C2C3E1F1G1H2

7

8 + 17 = 25

A3C2C3E1F1G1G3H2

6

8 + 15 = 23

B3C2C3E1F1F3G1H2

6

8 + 15 = 23

C2C3E1F1F3G1G3H2

5 *

8 + 13 = 21

There are three multiple-output minimal sums when the cost is based on number of distinct terms: --z --z f1 = yz + x yz + xy f1 = yz + x yz + xy - + xy -z - + xy -z f2 = yz f2 = yz -y + yz - + - + f3 = x xyz f3 = yz xyz + xyz -f1 = xz + x yz + - + xy -z f2 = yz - + f3 = yz xyz +

-yz x -yz x

- 4.81 -

4.32. (continued) There is only one multiple-output minimal sum when the cost is based on number of input terminals in the realization: --z f1 = yz + x yz + xy - + xy -z f2 = yz -y + yz - + f3 = x xyz 4.33. (a) xyz 0 2 4 3 5 6

xyz

000 f1f2 _ 010 f1f2 _ 100 f1 _ f3 011 f1 _ f3 101 _ f2f3 110 f1 _ f3

T

0,2 (2)

T

0,4 (4)

T

2,3 (1)

F

2,6 (4)

G

4,5 (1)

T

4,6 (2)

xyz

0-0 f1f2 _ -00 f1 _ _ 01- f1 _ _ -10 f1 _ _ 10- _ _ f3 1-0 f1 _ f3

f1 A: *2 B:

z -x z

D:

-y x xy

*3 E:

xz

C:

m0

m2

×

×

×

× ×

m3

B

0,2,4,6 (2,4)

T C

T D E

f2 m4

m6

×

×

m0

m2

f3 m5

m3

m4

± ×

m6

± ×

cost

3,4

×

3

×

×

×

± × ± ×

-z f2 = xz + xy

- 4.82 -

3 ± ×

×

×

f1 = ...

m5

1

×

-yz *3 F: x -z *2 G: xy

--0 f1 _ _ A

3,4 4,5

×

4,5

- + f3 = xz xyz + ...

4.33. (continued) Reducing the table:

f1 A: B:

z -x z

D:

-y x xy

E:

xz

C:

m0

m2

×

×

×

× ×

m3

f3 m4

m6

×

×

m5

1 1

×

3 × ×

F: xyz -z G: xy

×

3 1

×

1 ×

-z f2 = xz + xy

f1 = ...

cost

1

- + f3 = xz xyz + ...

After deleting dominated and equal rows B, E, and D, the table becomes

f1 *1 A: C:

z -y x

F: xyz -z *3 G: xy - + ... f1 = z

m0

m2

± ×

× ×

m3

f3 m4

m6

± ×

± ×

m5

cost 1

×

3

×

1 × ±

-z f2 = xz + xy

- 4.83 -

1

- + -z f3 = xz xyz + xy

4.33. (continued) Reducing the table:

f1 m3

cost

-y x

×

3

-yz F: x

×

1

C:

- + ... f1 = z

-z f2 = xz + xy

- + -z f3 = xz xyz + xy

To cover the remain column, select F.

The multiple-

output minimal sum is -yz f1 = z + x -z f2 = xz + xy - + -z f3 = xz xyz + xy (b) xyz

xyz 0 1 2 4 3 5 6 7

000 _ _ f3 001 f1f2f3 010 f1 _ _ 100 _ f2f3 011 _ f2 _ 101 f1f2 _

T

0,1 (1)

J

0,4 (4)

T

1,3 (2)

T

1,5 (4)

T

2,6 (4)

T

4,5 (1)

110 f1f2f3 K 111 f1f2 _ T

4,6 (2) 3,7 (4) 5,7 (2) 6,7 (1)

xyz

00- _ _ f3 C -00 _ _ f3 D 0-1 _ f2 _ T -01 f1f2 _ E -10 f1 _ _ F 10- _ f2 _ T 1-0 _ f2f3 G -11 _ f2 _ T 1-1 f1f2 _ H 11- f1f2 _ I

- 4.84 -

1,3,5,7 (2,4) 4,5,6,7 (1,2)

--1 _ f2 _ A 1-- _ f2 _ B

4.33. (continued) f1 m1 *2 A:

z

B:

x -x y

C: D: E:

-y z -z y

G:

yz xz

H:

xz

*1 F:

xy J: xyz K: xyz

m2

f2 m5

m3

m5

± ×

×

f3 m6

×

×

m7

m1

m4

m6

×

1

×

1 ×

3 ×

×

×

cost

3

×

3,4

± ×

3 × ×

×

I:

×

×

×

×

3,4

×

3

×

×

4,5

× - + ... f1 = yz

3,4

×

f2 = z + ...

4,5

f3 = ...

Reducing the table: f1 m1 B: C:

m5

x -x y

E:

-y z -z y

G:

xz

H:

xz

D:

f2

xy J: xyz K: xyz

m6

f3 m1

m4

m6

×

1 ×

3 ×

×

3

×

3 ×

×

×

×

I:

3,4 3

× ×

- + ... f1 = yz

cost

3 ×

×

4,5 ×

f2 = z + ...

- 4.85 -

4,5 f3 = ...

4.33. (continued) After deleting equal row I and dominated rows D, H, and K, the table becomes

f1 m1 B: C:

m6

f3 m1

m4

m6

×

J: xyz

×

3

± ×

3 ± ×

× ×

- + f1 = yz yz

cost 1

× ×

*3 G:

m5

x -x y -z y xz

*1 E:

f2

± ×

3,4 4,5

f2 = z + ...

- + ... f3 = xz

Reducing the table:

B:

f2

f3

m6

m1

x -x y

×

xz -J: x yz

×

C: G:

- + f1 = yz yz

cost 1

×

3 1

×

4,5

f2 = z + ...

- + ... f3 = xz

After deleting equal rows G and J, the table becomes

*2 B: *3 C: - + f1 = yz yz

x -x y

f2

f3

m6

m1

± ×

cost 1

± ×

3

f2 = z + x

- 4.86 -

- + x -f3 = xz y

4.34. w

x

y

z

(a)

(b)

(c)

(d)

(e)

(f)

0

0

0

0

0

1

0

0

0

1

0

0

0

1

0

0

1

0

0

0

0

0

1

0

1

0

0

0

0

1

0

0

1

1

1

1

1

0

1

0

0

1

0

0

1

1

0

1

1

0

0

1

0

1

1

1

0

0

1

1

0

1

1

0

0

0

0

0

0

0

0

1

1

1

0

0

0

1

1

0

1

0

0

0

0

1

1

1

1

1

1

0

0

1

0

1

1

0

0

1

1

0

1

0

1

0

1

0

0

1

1

0

1

1

0

1

1

0

1

1

1

1

0

0

1

1

1

1

1

0

1

1

0

1

1

1

0

1

1

1

1

1

1

0

0

0

1

0

0

0

1

1

1

1

0

0

1

1

1

1

(a)

-yz - + xy - + f = x wxy

- 4.87 -

4.34. (continued)

-+x+z -)(x+y)(x -+y -) f = (w

-+y -+z -)(x+y)(x -+y -) f = (w

(b)

-yz + y -- + wy f = x z + xy

-+z)(w+x+y+z -)(x -+y -) f = (y (c)

-z + wz - + wy f = x

- 4.88 -

4.34. (continued)

-+y+z -)(w+x -) f = (w+z)(x (d)

--f = xyz + xy z + wy z + wxy

-+z)(x+z -)(w+y+z -)(w+x) f = (y (e)

-f = yz + wy z + xy

- 4.89 -

--f = xyz + xy z + wy z + wxz

4.34. (continued)

-+z)(x+y+z -)(w+x+z) f = (y

-+z)(x+y+z -)(w+x+y) f = (y

(f)

-z + f = wz + xy xz

-+z)(w+x+z -)(w+x -+y -) f = (x

- 4.90 -

-+z)(w+x+z -)(w+y -+z -) f = (x

4.35. w

x

y

z

(a)

(b)

(c)

(d)

(e)

0

0

0

0

-

-

0

0

0

0

0

0

1

0

1

1

0

0

0

0

1

0

1

0

-

0

1

0

0

1

1

1

-

-

-

1

0

1

0

0

-

-

0

0

1

0

1

0

1

1

1

1

1

0

0

1

1

0

0

1

-

1

0

0

1

1

1

0

1

1

1

-

1

0

0

0

-

0

0

-

0

1

0

0

1

0

1

0

-

-

1

0

1

0

-

0

1

0

1

1

0

1

1

-

1

1

0

-

1

1

0

0

1

1

0

1

0

1

1

0

1

0

1

-

1

1

1

1

1

0

1

0

0

1

1

1

1

1

1

0

0

0

0

1

(a)

- + x -y + f = wz wxy

- 4.91 -

4.35. (continued)

-+z -)(x+y)(w+x -+y -) f = (w (b)

-z + w -x + xy f = x

-+x -+y -) f = (x+z)(w

- 4.92 -

4.35. (continued) (c)

-z + x -y f = w

-+x -)(w -+y) f = (w+z)(w

-+x -)(w -+y) f = (y+z)(w

- 4.93 -

4.35. (continued) (d)

-xz + xyz - + wy f = w

-+y -+z -) f = x(w+y+z)(w (e)

-xy --y f = wz + w z + wy + x

- 4.94 -

4.35. (continued)

-+z -)(w -+y+z)(x+y)(w+x -+y -) f = (w+x

-)(w -+y+z)(x+y)(w+x -+y -) f = (w+y+z 4.36. (a)

-z + Bxz - + f = Ax xyz

- 4.95 -

4.36. (continued) (b)

- + B --y + xy -f = Ay xz + Bx z (c)

-f = ABz + Ayz + A xy 4.37. (a)

- + w -y + xz - + wx f = yz

- 4.96 -

4.37. (continued) (b)

-wy -- + w -xz + v -xy - + v -wx f = v z + vxyz (c)

-yz + vz - + wy -z f = x

- 4.97 -