4.5k views

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
edited | 4.5k views
0
Actually option (II)  implies F.
0
Anyone explain what is mean "implied by F?"
0
@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.

+1

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

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$)
edited by
+1

It will help to understand ...

0
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.
0
See my other answers on ML. You will see those.
0
@Ahwan

0
You're making the subject relevant to the audience, nice articulation skills, good, keep it up!!!
0
sorry but i am not able to understand how 1st is correct. is there anyone who can explain it.
0

@Shubham Aggarwal
Cant you understand by the given example?

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

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

So, I and IV are only true.

edited
0
Is top of the arrow at both the side for $\forall x\forall y$ and  $\forall y\forall x$ ?
+1
exactly!!!
+2
What is the name of this method can you explain any link for it , how it works unable to understand
+1
plz tell how option 4th is right according to above  diagram????
+1
Sunidhi Chauhan

It is already implied. It is nothing but P==>P which is always true!!!
+1
ooh yes ....tx  Akash
0

Thanks.
0

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

@arjun @bikram
0
@Arjun sir @akash , please explain the polygon diagram
0
@akash are ¥x¥y = ¥y¥x ?

€x€y = €y€x ?

so B is the ans.

0

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

0
nice way to solve !
0
Your calculation of last part is wrong
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
0
Hi ..How option I is equivalent with the queston?

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

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

0

(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

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