Mathematical Foundation of Computer Science

DHARM

N-COM\APPENDIX.PM5

BOOLEAN ALGEBRA 363

= r′s′ + r′s + r s′ + r s ( t′ + t = 1) P2
= r′ (s + s′) + r (s′ + s) P4
= r′ × 1 + r × 1 P2
= r′ + r P1
= 1 P2
Therefore, f(r, s, t) = 1 = ΣΣΣΣΣ (0, 1, 2, 3, 4, 5, 6, 7); PDNF
f(r, s, t) = 1; then no maxterms; PCNF
(iii)p q + p′ q r
We first express the equivalent PDNF formula from the given formula. Since the
formula contains three variables and in the first term variable r is missing so ANDed the
expression (r + r′) in this term. Thus we have,
= p q. 1 + p′ q r P1
= p q (r + r′) + p′ q r P2
= p q r + p q r′ + p′ q r P4
which, is an equivalent PDNF formula.
To obtain the equivalent PCNF formula we write the formula as,
= p q + p′ q r = (p q + p′) (p q + q r)[∴ x + y z = (x + y) (x + z)] P4
= (p′ + p q) (p q + q r)[∴ x + y = y + x] P3
= (p′ + p) (p′ + q) (p q + q r) P4
= 1. (p′ + q) (p q + q r) P2
= (p′ + q) (p q + q r) P1
= (p′ + q) (p q + q) (p q + r) P4
= (p′ + q) (q + p q) (p q + r) P3
= (p′ + q) (q + p) (q + q) (p q + r) P4
= (p′ + q) (q + p) q (p q + r) T1
= (p′ + q) (q + p) q (r + p q) P3
= (p′ + q) (q + p) q (r + p) (r + q) P4
Above formula is in CNF; to obtain the PCNF we find the missing variables in each
terms. The missing variables from left to right terms are r, r, p and r, q, and p so, ORed the
expressions r r′, r r′, p p′ and r r′, q q′, and p p′ respectively. Thus we have,
= (p′ + q + r r′) (p + q + r r′) (p p′ + q + r r′) (p + q q′ + r) (p p′ + q + r) P3
= (p′ + q + r) (p′ + q + r′) (p + q + r r′) (p p′ + q + r r′) (p + q q′ + r) (p p′ + q + r) P4
= (p′ + q + r)(p′ + q + r′)(p + q + r)(p + q + r′)(p p′ + q + r r′)(p + q q′ + r)(p p′ + q + r)
P4
= (p′ + q + r)(p′ + q + r′)(p + q + r)(p + q + r′)(p p′ + q + r)(p p′ + q + r′)
(p + q q′ + r)(p p′ + q + r) P4
= (p′ + q + r)(p′ + q + r′)(p + q + r)(p + q + r′)(p + q + r)(p′ + q + r)
(p p′ + q + r′)(p + q q′ + r)(p p′ + q + r) P4
= (p′ + q + r)(p′ + q + r′)(p + q + r)(p + q + r′)(p + q + r)(p′ + q + r)(p + q + r′)(p′ + q + r)
(p + q q′ + r)(p p′ + q + r) P4
= (p′ + q + r)(p′ + q + r′)(p + q + r)(p + q + r′)(p + q + r)(p′ + q + r)(p + q + r′)(p′ + q + r)
(p + q + r)(p + q′ + r)(p p′ + q + r) P4