DHARM
N-COM\APPENDIX.PM5372 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCEFurther, these expression lies on the adjacent edges so it can be simplified as,
= x′ z′ + x z′ = (x′ + x) z′ = 1. z′ = z′ ...(2)
Combining expressions (1) and (2) we obtain,
f(x, y, z) = z′ + z′
= z′
Example A.9. Simplify the Boolean function f(p, q, r, s) = Σ (0, 1, 2, 4, 5, 6, 8, 9, 12, 13, 14).
Sol. K-map representation of the function using four variables are is shown in Fig. A.21 and
the presence of minterms in the function are shown by placing 1’s in the corresponding cells.pqrspq′′pq′pqpq′rs′ rs′ rsrs′11 0 1111110110100Fig. A.21
We see from the figure that eight cells are adjacent so they can group as to give the
expression r′. Remaining 1’s (three) near the right edge are adjacent to the similar number of
1’s of left edge but grouping of these adjacent cells can’t return the minimized expression.
Therefore, we group these 1’s as,
p′r′s′ + p′r s′ = p′(r′ + r) s′ = p′. 1. s′ = p′ s′ (top two left 1’s are grouped with top two right
1’s), and
q r′s′ + q r s′ = q (r′ + r) s′ = q. 1. s′ = q s′ (grouping of 1’s that lies middle rows and two
end columns)
Hence, the simplified Boolean function is,
F(p, q, r, s) = r′ + p′ s′ + q s′
The simplification approach using K-map is convenient for Boolean function of variables
not more than five or six. Because, when number of variables increases then it is difficult to
visualize the logical adjacency between cells. Therefore K-map is unfeasible for the simplification
of Boolean functions of large variables. Of course, using similar approach with algebraic
manipulations known as Quine McCluskey method can be used for the minimizing the Boolean
function of variables up to ten. Functions of large variables can be simplified using
approximation techniques or heuristics approaches based on trial - and - chance.
Example A.10 Obtain the simplify the Boolean function F(p, q, r, s) = Σ(0, 1, 2, 5, 8, 9, 10) in
sum of products (SoP) and product of sums (PoS).
Sol. Since function f is given in the sum of minterms form such as,
F (p, q, r, s) = m 0 + m 1 + m 2 + m 5 + m 8 + m 9 + m 10 ;