UGC NET CSE | June 2019 | Part 2 | Question: 6

Question

Which of the following is principal conjunctive normal form for $[(p\vee q)\wedge\ \neg p \rightarrow \neg q ]$ ?

• A. $p\ \vee \neg q$
• B. $p \vee q $
• C. $\neg p \vee q$
• D. $\neg p\ \vee  \neg q$  

Comments

Ans $1)$

---

Ans : A  

 

p ∨⌉q

Answer 1

Conjunctive Normal Form of a given well formed formulae (wff) is an equivalent wff consisting of product of elementary sum terms.

Principal Conjunctive Normal Form of a given wff is an equivalent wff consisting of product of sums where each sum term consists of all variables used in the formulae in negated or non-negated form.

---

---

Here, one question may arise:

HOW THE REDUCED WFF IS IN PRINCIPAL CNF FORM?

ANSWER: 

In principal conjunctive normal form, every sum term must contain every variable, used in the given formulae, in negated or non-negated form. 

PRINCIPAL CNF FORM  ⟺ CANONICAL PRODUCT OF SUM FORM

Here in reduced formulae of the given question, there is only one sum term, which is:   p∨⏋q 

This sum term contains all variables used in the original wff ( p and q ) in negated or non-negated form i.e. p is in non-negated form and q is in negated form. 

This satisfies the condition of principal conjunctive normal form and hence the reduced wff is in PRINCIPAL CONJUNCTIVE NORMAL FORM.

---

Thus, answer is OPTION 1.

Answer 2

Precedence in propositional logic:  $\neg >\wedge> \vee> \rightarrow> \leftrightarrow$

$[(p \vee q)\wedge\ \neg p \rightarrow \neg q]$

$\implies [((p \vee q)\wedge\ \neg p) \rightarrow \neg q]$

$\implies [((p \wedge\ \neg p)\vee (q \wedge\ \neg p)) \rightarrow \neg q]$ (using distributive law)

$\implies [(0\vee (q \wedge\ \neg p)) \rightarrow \neg q]$

$\implies [(q \wedge\ \neg p) \rightarrow \neg q]$

$\implies [\neg (q \wedge\ \neg p) \vee \neg q]$  (using demorgan's law)

$\implies [\neg q \vee p \vee \neg q]$

$\implies [p \vee \neg q]$

$\therefore$ Option $1.$ is correct.