Mathematical Foundation of Computer Science

DHARM

N-COM\APPENDIX.PM5

366 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

= (x x + z x + x y′ + z y′) (x′ + y) P4

= (x + x z + x y′ + y′ z) (x′ + y) T1 & P3

= x (x′ + y) + x z (x′ + y) + x y′ (x′ + y) + y′ z (x′ + y) P4

= x x′ + x y + x z x′ + x z y + x y′x′ + x y′ y + y′ z x′ + y′ z y P4

= 0 + x y + 0 + x y z + 0 + 0 + x′ y′ z + 0 P2 & P3

= x y + x y z + x′ y′ z P1

= x y (z + z′) + x y z + x′ y′ z P1

After Simplifying and rearranging we get the expression,

= x′ y′ z + x y z′ + x y z

PDNF

A.7 SIMPLIFICATION OF BOOLEAN FUNCTION USING K-MAP

Instead of squabble that simplification of Boolean function lacks specific deduction procedure
(Sec 5.4) in this section we will discuss a well known graphical method of minimization of the
Boolean functions for small values of n, where n is the number of Boolean variables. This
method developed in 1950s at AT and T lab known as Karnaugh Map or K-map method
simplifying the Boolean functions that are expressed in standard forms only.
A K-map of n variables function is a two dimensional array consisting of 2n cells that are
lying on a surface. It means, top and bottom boundaries and left and right boundaries of the
array touching each other to form adjacent cells. Each cell represents one minterms. Since,
SoP expression of any Boolean function consists of a sum of minterms; so entries of the cells in
the K-map will be 1 (0) with respect to presence (absence) of the corresponding minterms in
the Boolean function. The cells in the map are arranged according to the reflected-code sequence
(Gray-Code) such that logically adjacent minterms are almost adjacent to each other. The
presence of minterms in the function is all marked by 1 on the K-map, and the objective is to
frame the groups from the marked cells, so a minimal set is selected.

K-map for 2 variables

K-map for two variable Boolean function is shown in Fig. A.8. It has 4 (= 22) cells and

the cells are recognized by the minterms m 0 , m 1 , m 2 , m 3. Assume variables are x and y.

m 0 xy′′

y′ y

x′

xy′ x

xy′

m 2 xy

m 1

m 3

x

y

()a ()b ()c

Fig. A.8 K- map for 2 variables.

In the Fig. A.8 (b) minterms are shown. The presence of minterms in the function for

that cells entries are 1’s often called implicants. In the next figure prime implicants are shown

s.t. x′ and x are prime implicants corresponding to Ist and IInd row and similarly y′ and y are

the prime implicants corresponding to Ist and IInd column of the K-map.

Let the function f 1 (x, y) = x y′ (m 3 ); so place 1 on the cell represented by m 3 that shows

the presence of that minterms only. (see Fig. A.9 (a))