Mathematical Foundation of Computer Science

DHARM

N-COM\APPENDIX.PM5

BOOLEAN ALGEBRA 367

y′ yyy′

x′ x′

xx

()a ()b

111

1

Fig. A.9
Consider another example, f 2 (x, y) = x + y + xy; here first and second term of the function
are prime implicants so all the cells corresponding to IInd row (for x) and IInd column (for y)
are filled by 1’s. Also place 1 corresponding to the third term of the function in the cell m 3.
Therefore, K-map of f 2 could be seen in the Fig. A.9 (b).
Alternatively, f(x, y) = x + y + x y
= x. 1 + 1. y + x y P1
= x (y + y′) + (x + x′) y + x y (ANDed the missing term) P2
= x y + x y′ + x′y (Simplification)
which, is represented by K-map shown in Fig. A.9 (b).

K - map for 3 variables

K-map for three variables shall consists of 8(= 2

(^3) ) cells corresponds to the minterms
m 0 ,......m 7 shown in Fig. A.10. Here we assume the variables x, y, and z.
m 0 m 3
m 4 m 7
m 1 m 2
m 5 m 6
()a ()b
()c
xyz′′′
yz′′
x′
xyz′′
x
xyz′′
yz′
xyz′
xyz′
yz
xyz
xyz′′
yz′
xyz′
x
yz
Fig. A.10
Fig. A.10 (c) shows the prime implicants corresponding to rows and columns.
For example, let Boolean function f(x, y, z) = x y z′ + x y z + x′ y′ z′ = m 0 + m 6 + m 7 ; Boolean
function f can be represented by the K-map shown in Fig. A.11.
yz′′
x′
x
yz′ yzyz′
1
11 1
Fig. A.11