Mathematical Foundation of Computer Science

DHARM

N-COM\APPENDIX.PM5

368 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

Similarly K-map of 4 variables consists of 16 (= 2^4 ) cells for the minterms m 0 ,......m 15.

The arrangement of different cells is shown in the Fig. A.12.

m 0 m 3

m 4

m 8

m 12

m 7

m 11

m 15

m 1 m 2

m 5

m 9

m 13

m 6

m 10

m 14

wx′′

yz′′ yz′ yzyz′

wx′

wx

wx′

wx

yz

()a ()b
Fig. A.12
Since, Fig. A.12 (b) shows the prime implicants for rows and columns. The minterms of
each cell can be determined by the concatenation of the corresponding row label with column
label where rows and columns are labeled by the prime implicants.
For example, consider the function f(w, x, y, z) = w x y′ z′ + x y; the Ist term of the
function corresponds to minterm m 12. In the second term there is missing of variables w and z.
So, IInd term will be obtain from the summation of minterms i.e.
x y = (w + w′) x y
= w x y + w′ x y
= w x y (z + z′) + w′ x y (z + z′)
= w x y z + w x y z′ + w′ x y z + w′ x y z′
f(w, x, y, z) = w x y′ z′ + w x y z + w x y z′ + w′ x y z + w′ x y z′
After rearranging the terms we get,
= m 6 + m 7 + m 12 + m 14 + m 15
So, places 1’s in the K-map for cells m 6 , m 7 , m 12 , m 14 , and m 15 ; that is shown in Fig. A.13.

wx′′

yz′′ yz′ yzyz′

wx′

wx

wx′

1

1

1

1 1

Fig. A.13

It is also noted that each row or column has labeled by the expressions (prime implicants)

corresponding to the sequence of numbers generated using Gray code number system.

In general we assume that a minimized function Boolean function is that where sum of

products (product of sums) have minimal number of literals. Through K-map representation of

any Boolean function we may obtain the minimized Boolean function. (? How). Since, the cells