GATE CSE 2016 Set 2 | Question: 27

Question

Which one of the following well-formed formulae in predicate calculus is NOT valid ?

• A. $(\forall _{x} p(x) \implies \forall _{x} q(x)) \implies (\exists _{x} \neg p(x) \vee \forall _{x} q(x))$
• B. $(\exists x p(x) \vee \exists x q (x)) \implies \exists x (p(x) \vee q (x))$
• C. $\exists x (p(x) \wedge q(x)) \implies (\exists x p(x) \wedge \exists x q(x))$
• D. $\forall x (p(x) \vee q(x)) \implies (\forall x p(x) \vee \forall x q(x))$

Comments

@Souvik33 Go classes

---

Study From Amit Khurana Sir He will make this concept crystal clear.

https://www.youtube.com/watch?v=p8zqc46H7VY&list=PLC36xJgs4dxF5fTaOmUjEJJS8PMnbgO_Y&index=47&ab_channel=GATECSELECTURESBYAMITKHURANA

---

think like this alpha ---> beta  make  beta false and try to make alpha true if u r able to make alpha true then its not valid else this will be valid

Answer 1

Here, (D) is not valid

Let me prove by an example

What (D) is saying here is:

For all $x$ ( $x$ is even no or $x$ is odd no ) $\implies$ For all $x$( $x$ is even no ) or For all $x$ ( $x$ is odd no)

OR

If every $x$ is either even or odd, then every $x$ must be even or every $x$ must be odd.

If our domain is the set of natural numbers LHS is true but RHS is false as not all natural numbers are even or odd.

Answer is (D).

Comments

Let $P$ and $Q$ be two logical expressions.

1. Equivalence : $P \equiv Q $ means $P \iff Q$ i.e. $(P \implies Q)\wedge (Q \implies P)$

2. Implication : $P \implies Q$ only.

---

Given snapshot is valid in case of equivalence only, not in care of implication..

---

@ Madhab ji

the question says 

∃x(p(x)∧q(x))  ⟹  (∃xp(x)∧∃xq(x))

its a “ if then “ condition which means even if left hand is false, it does not matter what the right hand side is the entire statement is considered true so with the example you gave it is still valid

 

Answer 2

lets take there are two elements x1 and x2 in the UOD.

So ∀xp(x) = p(x1) ^ p(x2) so converting into digital logic formula p1.p2 and ∃xp(x)=p1+p2

so lets check the options

1)

(∀xp(x)⟹∀xq(x))⟹(∃x¬p(x)∨∀xq(x)) = (p1.p2 => q1.q2) =>((~p1+~p2)+(q1.q2)

A=(p1.p2 => q1.q2)

B=((~p1+~p2)+(q1.q2)

so now validate the formula to show if there is any case where we get A=True and B=False which is not possible now you can said it is a valid formula carry with rest of the options in similar way out of which you with get a True & False combination for option D 

Comments

Can you also explain this way for option b and c..

Answer 3

A valid proposition is one which is a tautology.

A) Here, both sides are equivalent. Use p -> q = ¬p v q to verify. Hence, is is valid.

B) The existential quantifier is distributive over disjunction. Hence, both sides are equivalent and thus, the statement is valid.

C) Here, both sides are not equivalent since existential quantifier is not distributive over conjunction. But, it is still valid because if left side is true, then there exists an x=a such that both p(a)=T and q(a)=T. Applying existential generalisation with a as the particular element in the domain of x, the right side is true.

D) When left side is true, the right side can be false. If left side is true, this means for every x, p(x) v q(x) = T. But at the same time, the right side can be false because both p(x) and q(x) can be false for different values of x.

So, D is invalid.

Comments

Can you also explain this way for option b and c..

---

@

A valid proposition is one which is a tautology.

is this statement correct here?

We are given first order logic in options and a FOL may be valid and cannot be a tautology at the same time.

 

 

 

Answer 4

$A)$

$(\forall _{x} p(x) \implies \forall _{x} q(x)) \implies (\exists _{x} \neg p(x) \vee \forall _{x} q(x))$

$(\forall _{x} p(x) \implies \forall _{x} q(x)) \implies (\neg\forall _{x}  p(x) \vee \forall _{x} q(x))$

$(p1p2\rightarrow q1q2)\rightarrow \neg(p1p2)+q1q2$

$\neg(p1p2)+q1q2\rightarrow \neg p1+\neg p2+q1q2$

$(\neg p1+\neg p2+q1q2)\rightarrow (\neg p1+\neg p2+q1q2)$

Valid

 

$D)$

$\forall x (p(x) \vee q(x)) \implies (\forall x p(x) \vee \forall x q(x))$

$(p1+q1).(p2+q2)\rightarrow p1p2+q1q2$

$(p1p2+p1q2+p2q1+q1q2)\rightarrow$ $(p1p2+q1q2)$

Set RHS : $(p1p2+q1q2)$ as False, and try to make LHS true. If you can make LHS true by trying different possibilities then this wff is NOT valid.  

If you consider $1.$ case of $p1p2\ \&\ 2.$ case of $q1q2$ then LHS can be made TRUE and hence $D)$ is not VALID

 

 

 

 

 

Similarly try for other 2 options.

Correct Answer : D

Comments

Can you also explain this way for option b and c..

---

For option B and C please find the explanation below ,

Hope , this helps.

---

Please refer this : https://gateoverflow.in/39618/gate-cse-2016-set-2-question-27?show=422338#c422338