Mathematical Foundation of Computer Science

DHARM

N-COM\APPENDIX.PM5

BOOLEAN ALGEBRA 369

in the K-map are so arranged that the adjacent cells are differs only by a single variable. This
variable must be prime (presence) in one cell and unprimed (absence) in other cell. Remaining
variables are same in both adjacent cells. Therefore, the summation (ORed) of two adjacent
cells (minterms) can be simplified to a single ANDed term consisting of one variable less.
For example, in a three variables K-map consider the summation of two adjacent cells
recognized by minterms m 4 and m 5 will be,
= x y′ z′ + x y′ z
= x y′ (z′ + z) = x y′. 1 = x y′ (free from one variable)
and is shown in Fig. A.14.

yz′′

x′

xx

yz′ yz

z

y

yz′

11

x

yz

Fig. A.14
Similarly summation of four adjacent cells can be simplified to a single term that will be
free from two variables, for example consider the summation of adjacent cells m 1 , m 3 , m 5 , and
m 7 in a three variables K-map is shown in Fig. A.15.
That will be, = m 1 + m 3 + m 5 + m 7
= x′ y′ z + x′ y z + x y′ z + x y z
= x′ (y′ + y) z + x (y′ + y) z
= x′ z + x z
= (x′ + x) z = 1. z = z (free from two variables)

yz′′

x′

x

yz′ yzyz′

1

1

1

1

x

yz

Fig. A.15

As we mentioned earlier that K-map is lies on the surface such that top and bottom

edges as well as left and right edges are touching each other to form adjacent cells. For example

in a three variables K-map cells recognized by m 0 , m 1 , m 3 , m 2 , are adjacent to cells m 4 , m 5 , m 7 ,

m 6 respectively; similarly cells m 0 , m 4 are adjacent to cells m 2 , m 6 respectively. In the similar

sense we can acknowledge the adjacent cells for four or more variables K-map.