Mathematical Foundation of Computer Science

DHARM

N-COM\APPENDIX.PM5

364 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

= (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 + q + r) (p′ + q + r) P4
Rearrange the maxterms and remove those that are appears more than once, so we get
the required PCNF,
= (p + q + r) (p + q + r′) (p + q′ + r) (p′ + q + r) (p′ + q + r′)
(iv) Express the function f(x, y, z) = x in PCNF.
Since, function contains three variables x, y, and z and the first term is missing of the
variables y and z, so ORed the expression y y′ and z z′ in this term.
Thus we obtain,
f(x, y, z) = x + y y′ + z z′ [∴ y y′ = z z′ = 0] P2 and [∴ x + 0 = x] P1
= (x + y y′ + z) (x + y y′ + z′) [∴ x + y z = (x + y)(x + z)] P4
= (x + y + z) (x + y′ + z) (x + y y′ + z′) P4
= (x + y + z) (x + y′ + z) (x + y + z′) (x + y′ + z′) P4
f(x, y, z) = (x + y + z) (x + y + z′) (x + y′ + z) (x + y′ + z′)P 3
PCNF
(v) Express function f(x, y, z) = (x + y)′ in PCNF.
F(x, y, z) = (x + y)′
= (x′) (y′) T5 [DeM]
= (x′ + 0) (y′ + 0) P1
= (x′ + y y′) (y′ + z z′) P2
= (x′ + y) (x′ + y′) (y′ + z) (y′ + z′) P4
= (x′ + y + 0) (x′ + y′ + 0) (0 + y′ + z) (0 + y′ + z′) P1
= (x′ + y + z z′) (x′ + y′ + z z′) (x x′ + y′ + z) (x x′ + y′ + z′) P2
= (x′ + y + z)(x′ + y + z′) (x′ + y′ + z) (x′ + y′ + z′) (x + y′ + z)
(x′ + y′ + z′)(x + y′ + z′) (x′ + y′ + z′) P4
Rearranging the maxterms and remove those maxterms that appears in the expression
more than once so we obtain,
f(x, y, z) = (x + y′ + z)(x + y′ + z′)(x′ + y + z)(x′ + y + z′)(x′ + y′ + z) (x′ +y′ + z′)
PCNF
Example A.6 Obtain the PCNF and PDNF of following formulas.
(1) (y → x) (x′ y)
(2) x → (x. (y → x))
(3) x + (x′ → (y + (y′ → z)))
(4) (x′ → z) (y ↔ x)
Sol. Since we know that any formula can be expressed in either PDNF or PCNF that are
using only operations +,. , and ′. The other operators (connectives) like → or ↔ can be converted
into +,. , and ′ operators by following equivalence formulas,
(i)(A → B) = (A′ + B)
(ii)(A ↔↔↔↔↔ B) = (A → B). (B → A)
First, we obtain the PCNF of the formula,
(1) (y → x) (x′ y) = (y′ + x) (x′ y) Equiv. (i)
= (x + y′) (x′) (y) P3