Scribd
Upload
5 views4 pages

Normal Forms

The document discusses logical equivalences and transformations in propositional logic, including examples of tautologies and the derivation of conjunctive and disjunctive normal forms. It illustrates the application of De Morgan's laws, distributive laws, and simplifications to various logical expressions. The examples demonstrate how to manipulate logical statements to achieve desired forms.

Uploaded by

adityakhot21
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
5 views4 pages

Normal Forms

The document discusses logical equivalences and transformations in propositional logic, including examples of tautologies and the derivation of conjunctive and disjunctive normal forms. It illustrates the application of De Morgan's laws, distributive laws, and simplifications to various logical expressions. The examples demonstrate how to manipulate logical statements to achieve desired forms.

Uploaded by

adityakhot21
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Example 2: Eliminating conditional and biconditional, find the

logicalequivalent forms of
() (g ’p) ’ (p’)
() p o(p vq)
(Note that q is ~ q)

Solution:(0 q’p= (qvp) = qvp


p’q = (p vq)

(q ’p) ’ (p ’ )
(qvp) (p vq).
Let, g Vp = s and p vg= t

then we have s - t =(s v t)

S = (qvp) =q Ap (by De Morgan's law)


= q Ap.

svt = (q ap) v(p vq)


= (q vp vq) a(p vp vq)
(by Distributive law)
(1.1
DISCRETE MATHEMATICS

= (qvq) vp)a(p vp) vq)


= (Tvp) A (Tvq)
= TAT=T.

The given form is logicallyquivalent to atautology.


(i1) p (p v q)

= (p ’ (p v q))a ((p vq) ’p)


= (p v (p v )) a (pv q)) v p)
=(p vp) v ) a(p A) vp)
= (p vq) ((p a ) vp)
(p a((p a q) v p)) v (q a (paq) vp))
=(p ap) v (p ap) v(q apag)
v(q ap)
=(cAq) vcv (cap) v (q a p)
= CVCVCV q ap

= pa q
(paq) are logically equivalent.

Example 7: Obtain the disjunctive normal form of


() (p ’ ) a(~ pA q),
(i) (pa(p -’ q)) 4.
Solution: (i) p qis logically equivalent to ~ pvq
(p’ q) a (~pa)=(~pv) a (~pa)
= (~pa ~pa) v(qa~paq)
= (~pA q) v(qa ~ p).
() (p a(p’ ) ’q=~ (pa(~pv q)) vq
=~p~ (~pv q) vg
=~pv (pa~q) vq

Example 8: Show that the following statenment is tautological:


(pa(p - q))’q
Solution:

(pa(p - ))’q = ~(pa (~pvq)) vq


=(~pV ~(~pv 9) vq
= (~pv (pa q)) vq
=(~pv ~ q) v q
=~p vT=T.

Example 9: Obtain the conjunctive normal form and disjunctive


normal form of the following formulae given below:
() pa (p ’ )

(i) ~(p v) (pa)


Solution:

()pa (p’ q) =pa(-pv q) - cnf


PA(~pv) = (pa~p) v (p A)
=Fv (p a )
(pa)- dnf. (a single conjunct)
15) PROPOSITIONAL LOGIC

() - (pv) (pA)
=(-~ (pvq) v (pa q) a (- (paq)
V~ (pvq))
=((p vq) v (p a )) a ((-pv q)
v(~pa~ q))
= (p vq) a((-pv ~qv~ p)
A(~pv ~qv~ q)
= (p vq) a(~pv ~q) a (~pv~)
= (p vq) a(~ p~ q) - cnf
Further,
(pv) A(~pv q) =((p v q) a~ p) v ((p v q) A~ q)
= (pa~ p) v(qa ~p) v((p A~)
v(qa~ q))
= Fv(q a ~ p) v(pa~ ) vF
= (qa p) v (p A~ q) - dnf.
Example 10: Find the conjunctive normal form and disjunctive
normal form for the following:
(0) (pvq) ’q

(i) pe(p vq)


Solution:

(0 ( vq)’q= (pvq) vq
=(p Aq) vq
(p Aq) vq - dnf
(p aq) vq = (p v q) a(qv)
= (~pv q) aq- cnf.
(i) px(p vq)= (p v(p vq) a(p vq)vp)
= (p vp vq) a((p a q)vp)
= (p vq) a (pvp) a (qv p)
= (p vq) apa(q v p) - cnf
= (p a p) v (q A p)) a (q vp)

= (Fv (q ap)) a(qvp)


= (q ap) A(q v p)
= (q apAq) v (q Apap)
= (Fap) v (q ap)
= Fv(g Ap)
= (q Ap) - dnf (Single conjunct)

You might also like