Mathematical Foundation of Computer Science

DHARM

N-COM\APPENDIX.PM5

376 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

A.5 Using K-map representation find the minimal CNF expression for each of the following func-

tions:

(i)f(x, y, z, w) = Π (0, 1, 2, 3, 4, 10, 11) (ii)f(x, y, z) = Π (0, 1, 4, 5)

(iii)f(w, x, y, z) = Π (0, 1, 2, 3, 4, 6, 12) (iv)f(w, x, y, z) = Π (0, 2, 6, 7, 8, 9, 13, 15).

A.6 Consider X = 01001001, Y = 01111000, and Z = 10000111 then find

(i)X + Y′ + Z (ii)(X′ + Z) Y (iii) X Y Z.

A.7 Let f(A, B, C) = AB′ + ABC′ + A′BC′, then show that

(i)f(A, B, C) + AC′ = f(A, B, C) (ii)f(A, B, C) + A ≠ f(A, B, C)

(iii)f(A, B, C) + C′ ≠ f(A, B, C).

A.8 Write the dual of each Boolean equation,

(i)x + xy = x + y (ii)(x. 1) (0 + x′) = 0.

A.9 Show that the dual of f(x, y) = xy + x′y′ is equal to its complement.

A.10 In the truth table shown in Fig. A.26 that defines the functions f 1 and f 2 , obtain the simplified

functions in SoP and PoS.

xyzf 1 f 2

00011

00110

01011

01101

10001

10111

11000

11110

Fig. A.26