Mathematical Foundation of Computer Science

DHARM

N-COM\APPENDIX.PM5

374 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

Since, no more 0 left in the K-map for consideration, therefore we get the simplified
complemented function,
F′ = q s′ + p q + r s;
Take complement, thus
(F′)′ = (q s′ + p q + r s)′
F = (q′ + s) (p′ + q′) (r′ + s′) (Using DeMorgan and involution law)
(PoS)
Example A.11 Given truth table (Fig. A.24) that defines the functions X 1 and X 2 , obtain the
simplified functions in SoP and PoS.
Sol. From the table shown in Fig. A.24 we obtain the given function X 1 and X 2 are in sum of
minterms forms as,
X 1 = Σ (1, 3, 4, 5) = m 1 + m 3 + m 4 + m 5 ;
and, X 2 = Σ (0, 1, 2, 5, 7) = m 0 + m 1 + m 2 + m 5 + m 7 ;

xyzX 1 X 2

00001

00111

01001

01110

10011

10100

11000

11101

Fig. A.24 Fig. A.24 (a)

yz′′

x′

x

x yz′ yzyz′

yz

11

11

00

00

Fig. A.24 (b)
Functions X 1 and X 2 can be represented using K-map (Fig. A.24 (a) and (b)) where 1’s
placed in cells represent all the minterms of the functions X 1 and X 2 and the cells marked with
0’s represents the absence of the minterms in the functions hence it denotes the complement of
the functions X 1 and X 2.
Combining 1’s we get the simplified expressions of functions X 1 & X 2 in SoP as,
X 1 = x y′ + y z′ + x′ z
and X 2 = x′ y′ + z′

yz′′

x′

x

x yz′ yzyz′

yz

11

11

00

00