GATE CSE 2017 Set 1 | Question: 02

Question

Consider the first-order logic sentence $F:\forall x(\exists yR(x,y))$. Assuming non-empty logical domains, which of the sentences below are implied by $F$?

1. $\exists y(\exists xR(x,y))$
2. $\exists y(\forall xR(x,y))$
3. $\forall y(\exists xR(x,y))$
4. $¬\exists x(\forall y¬R(x,y))$

• A. IV only
• B. I and IV only
• C. II only
• D. II and III only

Comments

@Chotu sir

 

Option 2 means,   there exists some Y which is related to ALL X's via the relation R.

 

The statement F means, For all X's individually there exist some Y. The Y's for different X's may or may not be the same

So option 2 seems to be a very particular case of F, when all X's are related to the same Y.

how then is option 2 implying F

---

@Mayank

Let us try to prove the implication false by making it T-->F.

There exists single y for all x such that R(x,y) is true-->for every x there exists some y for which R(x,y) is true.

Rhs of implication is false when there doesn't exist any y for some x for which R(x,y)is true.

In that case l.h.s can't be true. So we are unable to prove that T-->F is possible with this.So it is tautology and hence it is valid .

 

---

Meaning of 4th statement (without simplifying) in english  :-

Note :-  x for girl and y for boy

“(NOT)There exist a girl for none of boys”

Above have same meaning as given statement “F” i.e for all the girls there exists a boy. 

“girl-boy” example is inspired by below written “Ahwan” sir’s answer.

Answer 1

X implies Y (X->Y)means "Whenever X is true Y has to be True".

Here X is  F:∀x(∃yR(x,y)), now we have to find out what are the options will be definitely true if  F:∀x(∃yR(x,y)) is true.

Option I. will be obviously true if F:∀x(∃yR(x,y)) is true

Option II can be false when F:∀x(∃yR(x,y)) is true, for example let's say domain of x is {1,2} and domain of  y is {a,b,c} and R(1,a) and R(2,b) is true and R(1,b),R(2,a),R(1,c),R(2,c ) are false, hence ∀x(∃yR(x,y)) is true ,but  ∃y(∀xR(x,y)) is false

Option III. is also false, if we take the last example there is no x exists such that R(x,c) is true

Option IV is true, if we negate a statement twice then we will get back the original statement.(¬¬F=F).

We will negate F twice and then apply de morgan law in order to get option IV

∀x(∃yR(x,y))= ¬¬∀x(∃yR(x,y)) , now if we apply simple de morgan's law then we will get the option IV (De morgan law=>¬∀xP(x)=∃x¬P(x) and  ¬∃xP(x)=∀x¬P(x) )

¬¬∀x(∃yR(x,y))= ¬∃x¬(∃yR(x,y)) = ¬∃x(∀y¬R(x,y))

Answer B

Comments

nice explanation

Answer 2

from the rule of inference and validating we can say that logically

1 and 4 is correct answer here

so B is correct here

note:lambi cahudi edit is coming later

Comments

Hi ..How option I is equivalent with the queston?

Answer 3

SO 1 ANS IV are correct.

Answer 4

therefore option B is correct.