Mathematical Foundation of Computer Science

DHARM

N-COM\APPENDIX.PM5

362 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

(ii) Consider the next Boolean function f 2 (x, y, z) = (x + y). z. (x + y′ + z); that is in
standard form (PoS). Express f in a product of maxterms. Since, function contains
three variables x, y, and z and the first term is missing of variable z so ORed (z z′) in
the first term. Similarly, ORed (x x′) and (y y′) in the second term and nothing ORed
in the third term. Therefore, we obtain,
f 2 (x, y, z) = (x + y + z z′). (x x′ + y y′ + z). (x + y′ + z)
Since,
(x + y + z z′) = (x + y + z) (x + y + z′); P4 [Distribution]
and, (x x′ + y y′ + z) = (x + y y′ + z) (x′ + y y′ + z) P4 [Distribution]
= (x + y + z) (x + y′ + z) (x′ + y + z) (x′ + y′ + z);
Combining all the maxterms and removing those maxterms that appear more than
once, thus we obtain,
f 2 (x, y, z) = (x + y + z) (x + y + z′) (x + y′ + z) (x′ + y + z) (x′ + y′ + z);
=M 0. M 1 .M 2 .M 4 .M 6
f 2 (x, y, z) = Π (0, 1, 2, 4, 6); PCNF
Example A.5. Express the following functions in a sum of minterms and a product of maxterms.
(i)f(r, s, t) = (r′ + s) (s′ + t)
Since, the Boolean function f is not in standard form (SoP/PoS) so use distributive law to
remove parenthesis thus, we get the function is in standard form i.e.
f(r, s, t) = (r′ + s) (s′ + t)
= r′ s′ + s s′ + r′ t + s t P4
= r′ s′ + 0 + r′ t + s t ∴ s, s′ = 0 P2
= r′ s′ + r′ t + s t ∴ x + 0 = x P1
(SoP form)
To express the function f in sum of minterms, we find that the missing variables in
the first, second, and in the third terms are t, s, and r; therefore ANDed expressions are
(t + t′), (s + s′), and (r + r′) respectively. Thus we have,
= r′ s′ (t + t′) + r′(s + s′) t + (r + r′) s t
= r′s′t + r′s′t′ + r′s t + r′s′ t + r s t + r′ s t P4
Simplifying and rearrange the minterms thus we obtain
= r′s′t′ + r′s′t + r′s t + r s t
(∴ r′s′t + r′s′t = r′s′t and r′s t + r′s t = r′s t)T1
so, f(r, s, t) = r′s′t′ + r′s′t + r′s t + r s t
f(r, s, t) = Σ (0, 1, 3, 7); PDNF
Hence, f(r, s, t) = Π (2, 4, 5, 6); PCNF
(ii) f(r, s, t) = 1
Since we know that sum of all minterms of a Boolean function of n variable is 1. Here
function has three variables thus we have,
f(r, s, t) = r′s′ t′ + r′s′t + r′s t′ + r′ s t + r s′ t′ + r s′ t + r s t′ + r s t
Conversely, we can prove above fact also i.e.
f(r, s, t) = r′s′ t′ + r′s′t + r′s t′ + r′ s t + r s′ t′ + r s′ t + r s t′ + r s t
= r′s′ (t′ + t) + r′s (t′ + t) + r s′ (t′ + t) + r s (t′ + t)