Mathematical Foundation of Computer Science

DHARM

N-COM\APPENDIX.PM5

360 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

Thus we can express the Boolean function f containing n variables (x 1 , x 2 , .............xn) in
sum of minterms or product of maxterms respectively as,
f (x 1 , x 2 , .............xn) = Σ mk ...(I)
and f (x 1 , x 2 , .............xn) = Π mk ...(II)
Where, we take those k’s (0 ≤ k ≤ 2 n – 1) for which combination of variables results truth
value 1. The symbols Σ and Π denotes the logical sum (OR) and product (AND) operations. It
is also observed from the truth table that each maxterm is the complement of its correspond-
ing minterms, and vice-versa. A Boolean function expressed as a sum of minterms or product
of maxterms is said to be in canonical form.
Example A.3. Express the Boolean function f 1 and f 2 shown in Fig. A.7 in sum of minterms
and product of maxterms forms.
xyzf 1 f 2
00010
00110
01010
01101
10001
10101
11001
11101
Fig. A.7
Sol. Functions f 1 is of three variables x, y, and z. Since the combinations of terms x′y′z′, x′y′z,
and x′yz′ of corresponding minterms m 0 , m 1 , and m 2 respectively yields the truth value of
f 1 = 1. Thus we have,
f 1 (x, y, z) = x′y′z′ + x′y′z + x′yz′
= m 0 + m 1 + m 2 ;
or, equivalently it can be expressed as,
f 1 (x, y, z) = Σ (0, 1, 2);
Now to express the complement of function f 1 , we consider those minterms for which
combination of variables results truth value 0 in the f 1 such that m 3 ,....m 7.
So, we have f 1 ′(x, y, z) = m 3 + m 4 + m 5 + m 6 + m 7 = Σ (3, 4, 5, 6, 7);
= x′yz + xy′z′ + xy′z + xyz′ + xyz
Since, (f 1 ′)′ = f T3 (Involution)
Thus we obtain,
(f 1 ′(x, y, z))′ = (x′yz + xy′z′ + xy′z + xyz′ + xyz)′
f 1 (x, y, z) = (x′yz)′. (xy′z′)′. (xy′z)′. (xyz′)′. (xyz)′ T5 (De Morgan’s)
= (x + y′ + z′). (x′ + y + z). (x′ + y + z′). (x′ + y′ + z). (x′ + y′ + z′)
T5 (DeM)
= M 3. M 4. M 5 .M 6 .M 7
(Product of maxterms)
so, f 1 (x, y, z) = π (3, 4, 5, 6, 7);