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

Ans is B.

1st Method: $F:\forall x(\exists yR(x,y))$

Take option 4: $¬\exists x(\forall y¬R(x,y))$

$\quad \equiv \forall x(\exists yR(x,y))$  $($Since we know that $\neg \forall x \equiv \exists x $ And  $ \neg\exists x =\forall x )$

F:  For all girls there exist a boyfriend. (Given)
( $x$ for girl and $y$ for boys)

1. There exists some boys who have girlfriends.  (True)
2. There exists some boys for whom all the girls are girlfriend. (False)
3. For all boys there exists a girlfriend. (False)
4. For all girls, there exists a boyfriend (True) (Same as given statement $F$)

Comments

Maja aya 😂

---

Best example I have seen in my whole life😂😂

---

Example Op in the chat boys XD

Answer 2

 

Solution.

1. $\forall x\exists y$$R(x,y)$ $\rightarrow$$\exists y\exists x$$R(x,y)$     True
2. $\forall x\exists y$$R(x,y)$ $\rightarrow$$\exists y\forall x$$R(x,y)$     False
3. $\forall x\exists y$$R(x,y)$ $\rightarrow$$\exists x\exists y$$R(x,y)$     False
4. $\forall x\exists y$$R(x,y)$ $\rightarrow \neg \exists x(\forall y\neg R(x,y))$

                                    $ \rightarrow \forall x\exists yR(x,y)$   True

So, I and IV are only true.

Answer is option B.

Comments

Say, for this example.

LHS= 'Some friends are best friends of all friends."

RHS='All friends are best friend of some friends.'

Is here $LHS\rightarrow RHS?$

---

@ srestha mam, I had a same doubt regarding this , but check it once, 

I don't Find any True -> False case arise for  this ∃x∀yP(x,y)→∀y∃xP(x,y). Since we know if any T -> False case arise for this then This formula don't remain valid.

Now I'll break down every thing in variables to make better understanding,

LHS= 'Some friends are best friends of all friends."

RHS='All friends are best friend of some friends.'

 

let's take X = {Raju , Mukesh}

Y = {Rani , Rakesh}

and P(x,y) => x is a friend of y.

I want to proof if it can arise T-> F then given formula goes invalid implication.

∃x∀yP(x,y)=>  LHS

[ P(Raju, Rani) ^ P(Raju, Rakesh) ] or [  P(Mukesh, Rani) ^ P(Mukesh, Rakesh) ]  (Lets say everyone is friend of Raju )

then LHS = TRUE (I don't care about Mukesh  ,right now)

 ∀y∃xP(x,y)=> RHS

[ P(Raju, Rani) or P(Mukesh,, Rani) ] ^ [  P(Raju, Rakesh) or P(Mukesh, Rakesh) ]  Goes True (T ^ T => T)

case 2nd when X = Y i.e have same domain then making RHS false we never got True for LHS

one more intresting Example i was able to plug and play P(X, Y) = X < Y.

case 1 : X = Y = {2,3} and predicate P(x, y) => x<y.(X and Y same domain)

T -> F case note arise for this also , i get RHS false and LHS also false,  False -> anything goes True

case 2: X= {2, 3} Y ={1, 5} first I get False for RHS then I don't able to make LHS True

so again T-> F case not arises here.

Even if we take X= {2,3} and Y = {4,5} it gives Tatoulogy, since X < Y so don't required such case for proving by contradiction.

Eventually we can say that Formula 

 

∃x∀yP(x,y)→∀y∃xP(x,y) is valid.

but it's converse not true.

Please check it mam , if anything goes wrong.

 

 

 

---

akash.dinkar12 How is III “∀x∃yR(x,y) →∃x∃yR(x,y)“ False

∀x∃yR(x,y) → ∃x∃yR(x,y) and ∃x∃yR(x,y) $\equiv$ ∃x∃yR(x,y).

So shouldn’t ∀x∃yR(x,y) →∃x∃yR(x,y) be true?

Answer 3

so B is the ans.

Comments

How come are you getting R(1a) + ~R(1a)~R(1b) = ~R(1b) & also for R(2a) + ~R(2a)~R(2b) = ~R(2b) your last method ? Shouldn't it be

R(1a) + ~R(1a)~R(1b) = R(1a) + ~R(1b)   ??

And also in the 2nd last method, you wrote: "So if the left side is false for all x,y then the right side can't be true". I think the statement should be "So if the right side is false for all x,y then the left side can't be true"

Please correct me if I'm misinterpreting something.

Thanks

---

nice way to solve !

---

Your calculation of last part is wrong

Answer 4

Here is a very simple method using which we can solve this type of problems easily.

Given F: $\forall$x($\exists$yR(x,y))

Let the Domain of x be (1,2) and y be (1,2)

Then above expression F can be rewritten as

F : ( (R(1,1) v R(1,2) ) ^ (R(2,1) v R(2,2) ) for all x there must exist some y such that R(x,y) is true.

Now questions asks for which of the expressions are implied by this means given an expression E, is F$\rightarrow$E a tautology ?

Let's consider options one by one.

(I)$\exists$y ($\exists$xR(x,y))

 Considering above domains of x and y we can rewrite them as

( (R(1,1) v R(2,1) ) v ( R(1,2) v R(2,2) )

Now is this expression implied by F? means

is ( (R(1,1) v R(1,2) ) ^ (R(2,1) v R(2,2) ) $\rightarrow$ ( (R(1,1) v R(2,1) ) v ( R(1,2) v R(2,2) ) a tautology?

Yes, it is absolutely a tautology because this implication will only be false when the antecedent is true and the consequent is false and you can check the above expression, it will never happen. So this is implied expression.

(II)$\exists$y($\forall$R(x,y))

   This can be rewritten as

( (R(1,1) ^ R(2,1) ) v ( R(1,2) ^ R(2,2) ) ) for some y there must exist all x such that R(x,y) is true.

is this implied by F?

( (R(1,1) v R(1,2) ) ^ (R(2,1) v R(2,2) ) $\rightarrow$ ( (R(1,1) ^ R(2,1) ) v ( R(1,2) ^ R(2,2) ) ) a tautology?

This implication can be false when R(1,1) is true, R(2,2) is true and R(1,2) is false and R(2,1) is false.So, this is not implied expression.

(III)$\forall$y($\exists$xR(x,y)) can be rewritten as

( (R(1,1) v R(2,1) ) ^ ( R(1,2) v R(2,2) ) ) for all y there must exist some x such that R(x,y) is true.

is  ( (R(1,1) v R(1,2) ) ^ (R(2,1) v R(2,2) ) $\rightarrow$ ( (R(1,1) v R(2,1) ) ^ ( R(1,2) v R(2,2) ) ) a tautology?

This implication can also become false when only R(1,1) and R(2,1) are true. So, this is also not implied expression.

(IV) $\sim\boldsymbol{ \exists x(\forall y \sim R(x,y))}$ The expression in bold is just the complement of the Given F. and so this option looks like $\sim$( $\sim$ F) which is equal to F. and so this is trivially implied by F.

So, answer is (I) and (IV).

Comments

Ayush Upadhyaya

(I)∃∃y (∃∃xR(x,y))

 Considering above domains of x and y we can rewrite them as

( (R(1,1) v R(2,1) ) v ( R(1,2) v R(2,2) )

HOW DID U WRITE THIS NOT GETTING PLEASE EXPLAIN

 

---

for(i=1;i<=n;i++)

{    for(j=1;j<=n;j++)

         {

             if(R(x,y)==true)

             { flag=true;

               break;

              }

            

 

          }

    if(flag==true)

    break;

}

if(flag==true)

printf("expression is true");

I hope you now must get it.