The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+27 votes

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))$
  1. IV only
  2. I and IV only
  3. II only
  4. II and III only
asked in Mathematical Logic by Loyal (7.7k points)
edited by | 4k views
Actually option (II)  implies F.
Anyone explain what is mean "implied by F?"
@srestha @Manish can u plz tell what does "implied by F means".

What m thinking is F-> ? (When F is true then the RHS must be true) .

correct me if m wrong.

thanks in advance.

It is similar to when we say A is implied by B ie B→A, here also in this question also when the question says below sentences are implied by F  means;

F →∃x(∃yR(x,y))

x(∃yR(x,y)) →∃x(∃yR(x,y))


6 Answers

+41 votes
Best answer

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$)
answered by Boss (11.1k points)
edited by

It will help to understand ...

It will work in similar models but not every where. I use it sometimes. The other one is divisible by 3 and 2.. Or something like that by taking set X and Y. I have used it in other qsns.  Depending on the qsn you have to modify that divisible by example too.
See my other answers on ML. You will see those.

Could you please share the link of your other answers you are mentioning about?
You're making the subject relevant to the audience, nice articulation skills, good, keep it up!!!
sorry but i am not able to understand how 1st is correct. is there anyone who can explain it.

@Shubham Aggarwal
Cant you understand by the given example?

yes sir thats why i do comment. is there any approach ,i just want to knwo only about 1st statement
+29 votes


  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))\forall x\exists yR(x,y)$   True

So, I and IV are only true.

answered by Boss (27.5k points)
edited by
Is top of the arrow at both the side for $\forall x\forall y$ and  $\forall y\forall x$ ?
What is the name of this method can you explain any link for it , how it works unable to understand
plz tell how option 4th is right according to above  diagram????
Sunidhi Chauhan

It is already implied. It is nothing but P==>P which is always true!!!
ooh yes ....tx  Akash
Can any one please explain how he made the polygon? A relevant link would be more helpful.


akash.dinkar1  can u please explain more about this polygon or refer some source .

thanks in advance !

Plz explain this polygon method... can anyone plz post a link to study this

@arjun @bikram
+13 votes

so B is the ans.

answered by Loyal (6.9k points)

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.


nice way to solve !
+5 votes
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
answered by Boss (18.7k points)
Hi ..How option I is equivalent with the queston?
+5 votes

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

answered by Active (1.9k points)
+1 vote

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.


   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).

answered by Boss (15.4k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

42,296 questions
48,419 answers
62,661 users