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

Yes , option D is wrong.But option C is also wrong, right ?

---

no. C is valid.

---

C) there exist x (x divisible by 2 and x divisible by 3) -> there exists x (x divisible by 2) and there exists x(x divisible by3)

for eg. left side contains set {6,12,18.............}

right side will also contain {6,12...........}

---

plz explain option (A).

---

but in option c if we assume that P(x) is positive and Q(x) is negative then in the option c then in the option c the left hand side is coming to be false while the right hand side is coming to be true because

∃x(P(x)⋀Q(x))) is false because here there  exits a x where it is positive and negative simultaneously is false but in the right hand side portion

∃x P(x)  ⋀ ∃x Q(x) is true because there exits a x ie the number is positive and there exits a x ie the number is negative.

---

i guess its something like this
      lets take left-side as p and right side as q

now that arrow inbetween shows conditional operator then answer will be false only if q is false

so even in your +ive and -ive number assumption  only option d will be false

---

According to Rosen-

We can distribute a universal quantifier over a conjunction only.

We can distribute a existential quantifier over a disjunction only.

But here we are not discussing about Logical equivalence.

The question is about Implication.. So in questions like these should we always consider examples?

---

For ex- In this question option a and b are 100% valid.

for option c and d. Let take two statements

Statement 1- P(x) x is a even number

Statement 2- P(y) y is a odd number.

Option C- LHS- For All x, x is a even no and a odd number (FALSE) So P->Q is true if P is false. Hence it is valid

Option D-LHS- For  all x, x is either a even no or a odd number(True) RHS- For all x, x is a even number or for all x, x is a odd number which is false. So P->Q is false if P is true and Q is false. Hence this is not valid (Because to be valid all the sets should be valid and here we found a non satisfying set.)

---

Lecture 4- Discrete Structures by Kamala MAM Nptel

---

thank for the answer @harveen singh

---

harveen singh what is the diference between Implication & Logical equivalence

---

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