Just clearing my doubt

53 votes

Which one of the following well-formed formulae is a tautology?

- $\forall x \, \exists y \, R(x,y) \, \leftrightarrow \, \exists y \, \forall x \, R(x, y)$
- $( \forall x \, [\exists y \, R(x,y) \, \rightarrow \, S(x, y)]) \, \rightarrow \, \forall x \, \exists y \, S(x, y)$
- $[ \forall x \, \exists y \, \left( P(x,y) \, \rightarrow \, R(x, y) \right)] \, \leftrightarrow [ \forall x \, \exists y \left(\neg P(x, y) \, \lor R(x, y) \right)]$
- $\forall x \, \forall y \, P(x,y) \, \rightarrow \, \forall x \, \forall y \, P(y, x)$

0

may be this link will help you...

http://www.geeksforgeeks.org/fundamentals-of-algorithms/#AnalysisofAlgorithms

http://www.geeksforgeeks.org/fundamentals-of-algorithms/#AnalysisofAlgorithms

45 votes

Best answer

Ans (**C**).

$\left(P \rightarrow Q\right) \leftrightarrow \left(\neg P \vee Q\right)$

(D) is wrong as shown below.

Let $S = \left\{2, 3, 4, 5\right\}$ and $P(x,y)$ be $x < y$.

Now, $P(2,3)$ is true but $P(3,2), P(4,2)$ etc are false and hence the implication also.

This is because the given formula is evaluated as:

$\forall x \, \forall y \, \left(P(x,y) \, \rightarrow \, \forall x \, \forall y \, P(y, x) \right)$

For every (x,y) if P(x,y) is true then for every (x,y) P(y,x) is true.

On the RHS, $P(y,x)$ can be replaced with $P(x,y)$ and then also the formula means the same. So, here precedence rule used is $\implies$ having more precedence than quantification which is against the convention used in Wikipedia. I guess all books only talk about conventions and there is no standard here. (C) option being so straight forward I guess, GATE didnot even consider this as an ambiguity. Also, it works only if $x, y$ belongs to same domain.

The below one is a tautology provided $x,y$ have the same domain.

$\left(\forall x \,\forall y P(x,y) \, \right) \rightarrow \,\left( \forall x \forall y \,P(y, x)\right)$

If P(x,y) is true for all (x,y), then P(y,x) is true for all (x,y).

5

Yes. But there were two ) missing in C in the GATE paper. ideally they should give marks for All here.

1

They are asking for well formed formula C is not well formed formula option D should be correct because its just change of variable names.

0

Why can't $\forall x\forall y P(y,x)$ be written as $\forall y\forall x P(x,y)$.

In that case option D will be true

In that case option D will be true

1

ans C is correct bcoz a<->b meansif a and b are equivalent then it is tautology ,option has same statement on both sides of<->

0

C is correct, but in actual GATE paper the ending braces were missing. GATE takers were supposed to ASSUME it.

8

P(x, y) is a predicate. And x < y, is just a chosen one, you can chose any other also.

To prove a formula is not valid, it is enough to give one counter example. Here, for D one is given like that.

To prove a formula is not valid, it is enough to give one counter example. Here, for D one is given like that.

1

Because the forall quantifier covers all possible combination of x and y and if it is true, that means there is no combination of x,y for which P(x,y) is false => P(y,x) also cannot be false, as both x and y are coming from same domain.

0

sir, in (d) option how can we think about braces () in exam..as given in both the following statement....

(∀*x*∀*y**P*(*x*,*y*))→(∀*x*∀*y**P*(*y*,*x*))

or

∀*x* ∀*y* (*P*(*x*,*y*) → ∀*x* ∀*y* *P*(*y*,*x*))

and sir, plz explain more how the following is tautology??

(∀*x*∀*y**P*(*x*,*y*))→(∀*x*∀*y**P*(*y*,*x*))

2

(∀*x*∀*y**P*(*x*,*y*))→(∀*x*∀*y**P*(*y*,*x*))

Here the LHS will be true only if P(x,y) is true for every possible x and y. Since both x and y are coming from the same universe, if this is true, then their order doesn't matter for P(x, y).

1

Option D is not proved as a contradiction. It is just proved as not tautology.

That is we just gave an instance where D is false. There may or may not be instances where D is TRUE- here there is and hence D is not a contradiction.

That is we just gave an instance where D is false. There may or may not be instances where D is TRUE- here there is and hence D is not a contradiction.

2

quantification has higher precedence than implication. But a brace, comma or sometimes even "." might be used to change this.

1

In the answer, this is given. Why it is evaluated in this way?

Quantification has higher precedence, then why like this?

0

yes the domain of x and y are not mentioned ,then how can we assume they are from same domain Arjun Sir?

0

its confusing. i am not getitng it. :-(

(∀*x*∀*y**P*(*x*,*y*))→(∀*x*∀*y**P*(*y*,*x*)) is a tautology.

But it wont be true for existential quantifiers right??

0

$\exists x \exists y = \exists y \exists x$

As both means there exists x and y.

This proves it rt? Actually implication can even be replaced by double implication.

As both means there exists x and y.

This proves it rt? Actually implication can even be replaced by double implication.

0

yeah thats completely fine. But the change of order of variable x and y in the predicates doesnt change its meaning?? I am really not able to understand how P(x,y) is same as P(y,x)?? plz clear it.

IF its UNIVERSAL QUANTIFIER then what i understand is that if P(x,y) is true for all all x and all y, it will be true for all combinations of x and y, So order will not matter if both x and y comes from same domain. But in existential quantifier how its true that order will not matter?? I am sounding silly. lol

IF its UNIVERSAL QUANTIFIER then what i understand is that if P(x,y) is true for all all x and all y, it will be true for all combinations of x and y, So order will not matter if both x and y comes from same domain. But in existential quantifier how its true that order will not matter?? I am sounding silly. lol

3

Yes, that can change the meaning. But $\exists x (P(x) ) \leftrightarrow \exists y P(y))$ rt?

Like this, when we put same quantification for both x and y, $P(x,y) \leftrightarrow P(y,x)$. If we change one of them to a different quantifier, then this no longer holds.

Like this, when we put same quantification for both x and y, $P(x,y) \leftrightarrow P(y,x)$. If we change one of them to a different quantifier, then this no longer holds.

1

Now i got the meaning. Thanx so much arjun sir. But it will be false if x and y comes from different domain? what is meant by this statemnt?? diffrent domain

1

yes, Think of something like every student has a car. So, the domains can be students of a school and say cars inside the parking.

1

If we give higher precedence to universal quantification and assume same domain for x and y, then this statement will be true/tautology right??

Ideally when quantification has higher precedence than implication why is there a need to assume things?

I know C is a stronger answer but just for knowledge i want the reason.

4

Yes, "Why is there a need"

Because GATE question papers are made by humans and not machines. And they do not copy questions. Such such mistakes do come and in such cases options are used to avoid ambiguity. Other way might have been to give "Marks to All", but say you get mark then so do anyone writing GATE which is not really correct as most people would have never even seen Mathematical Logic syllabus. So, justice prevails :)

Because GATE question papers are made by humans and not machines. And they do not copy questions. Such such mistakes do come and in such cases options are used to avoid ambiguity. Other way might have been to give "Marks to All", but say you get mark then so do anyone writing GATE which is not really correct as most people would have never even seen Mathematical Logic syllabus. So, justice prevails :)

1

Really nice reasoning sir. Marks should not be given to all. Thanx Arjun sir. Learned lot from this question.

0

For (∀x[∃yR(x,y)→S(x,y)])→∀x∃yS(x,y), is it correct to say: (∀x∃y[R(x,y)→S(x,y)]) <=> (∀x∃y[R'(x,y) V S(x,y)])?

Please explain how to negate B. Thanks.

Please explain how to negate B. Thanks.

1

Sign <-> represents “not equivalent”.

∀x∃y R( x, y ) is not equivalent to ∃Y ∀X R( X, Y )

Let R( X, Y ) represent X < Y for the set of numbers as the universe, for example. Then **∀X ∃Y R( X, Y ) reads** “for every number x, there is a number y that is greater than x”, which is true, while

**∃Y ∀X R( X, Y )** reads “there is a number that is greater than every (any) number”, which is not true. So this option is rejected.

**Option (d)**

Sign -> represents “equivalent”

∀X ∀Y R( X, Y ) is equivalent to ∀X ∀Y R( Y, X )

Let R( X, Y ) represent X < Y for the set of numbers as the universe, for example. Then **∀X ∀Y R( X, Y )** reads “for every number X, there is every Y that is greater than x”,

while **∀X ∀Y R( Y, X )** reads “for every number Y, there is every X that is greater than Y”.

And both can’t be equivalent (because at one time, one will be true and other one will be false) So this option is

rejected.

**Option (b)** is clearly rejected as two predicate can’t be equivalent to one predicate only. So Option (c) is the correct one.

**Explanation for option (c)** – as position of the quantifier is not changed and since LHS P -> R = ⌐P ᴠ R which is equal to RHS.

Option c is tautology and correct answer too.

0

Arjun Sir,

Is this is a tautology?

(∃*x*∃y)*P*(*x*,*y*))→(∃*x*∃y)*P*(*y*,*x*)

if yes then how. I know you have answered this above but symbols are not showing clearly.

0

@hement parihar , it will be true due to there exists, there will be atleast one pair of x,y which will follow this , am i wrong ?

1

@hemant

let P(x,y) : x likes y

(∃x∃y)P(x,y) : there exit a x who likes atleast y

(∃x∃y)P(y,x) : there exit a y who liked by atleast x

(∃x∃y)P(x,y))→(∃x∃y)P(y,x)

if (∃x∃y)P(x,y)) is TRUE then (∃x∃y)P(y,x) also be TRUE

let P(x,y) : x likes y

(∃x∃y)P(x,y) : there exit a x who likes atleast y

(∃x∃y)P(y,x) : there exit a y who liked by atleast x

(∃x∃y)P(x,y))→(∃x∃y)P(y,x)

if (∃x∃y)P(x,y)) is TRUE then (∃x∃y)P(y,x) also be TRUE

6

**Precedence Order **

The syntax for logical connectives is as follows:! (not), `^`

(and), `v`

(or), `=>`

(implies), `<=>`

(if and only if), `FORALL/forall/Forall`

(universal quantification), and `EXIST/exist/Exist`

(existential quantification). Operator precedence is as follows:

**not >**** ****and**** > ****or **** >**** ****implies**** > ****if**** and only ****if **** > ****forall**** = ****exists**.

Operators with the same precedence are evaluated left to right. You can use parentheses to enforce a different precedence, or to make precedence explicit (e.g., `(A=>B)=>C`

as opposed to `A=>(B=>C)`

). Universal quantifiers at the outermost level can be omitted, i.e., free variables are interpreted as universally quantified at the outermost level. Quantifiers can be applied to more than one variable at once (e.g., `forall x,y`

). The infix equality sign (e.g., `x = y`

) can be used as a shorthand for the equality predicate (e.g., `equals(x,y)`

).

Link:http://alchemy.cs.washington.edu/user-manual/4_1First_Order_Logic.html

- But in
**Kenneth****rosen**`Forall`

(universal quantification) and`Exist`

(existential**higher precedence than all**Logical operators from propositional calculus.

So which one is correct Precedence order? I am just confused.

2

Is this is a tautology?

(∃

x∃y)P(x,y))→(∃x∃y)P(y,x)

Yes.

Actually (∃*x*∃y)*P*(*x*,*y*) ) === (∃*x*∃y)*P*(*y*,*x*) means (∃*x*∃y)*P*(*x*,*y*)) <---> (∃*x*∃y)*P*(*y*,*x*)

2

@chottu Consider this case:

let P(x,y) be "x divides y" and P(y,x) be "y divides x"

Consider x = {2,3} and y = {9}

(∃*x*∃y)*P*(*x*,*y*)) (LHS) will be true as there exists an x that divides some y.

(∃*x*∃y)*P*(*y*,*x*) (RHS) will be false as there doesn't exist any y that divides x.

This gives T-->F. Where am I going wrong?

0

@arjun sir I did not get the answer whether (∃*x*∃y)*P*(*x*,*y*))→(∃*x*∃y)*P*(*y*,*x*) is a tautology or not.

Can you please tell again?

1

Hi @Warlock lord ji,

Why are you fixing X and Y for both sides ?

means $\exists_{x}\exists_{y}$(*P*(*x*,*y*) $\Leftrightarrow$ *P*(*y*,*x*)) and $\exists_{x}\exists_{y}$*P*(*x*,*y*) $\Leftrightarrow$ $\exists_{x}\exists_{y}$*P*(*y*,*x*) are different.

0

∀x∀y(P(x,y)→∀x∀yP(y,x))

For every (x,y) if P(x,y) is true then for every (x,y) P(y,x) is true.

i think this is a mistake in the above answer as the quantifiers have to be applied first i think

(∀x∀y)(P(x,y))→(∀x∀y)(P(y,x)) is correct

1

@Warrior the quantifiers should be evaluated first

https://math.stackexchange.com/questions/1150746/what-is-the-operator-precedence-for-quantifiers

0

#madhab i am nt getting ur statement "Sign <-> represents “not equivalent”." ?? can anyone explain ??

0

Option d is not tautology as a relation may or may not be symmetric, therefore this won't be a tautology.

0

@shankargadri, while reading above comment for this point I can't convience myself as this is similar to https://gateoverflow.in/3560/gate2006-it-21 this.

but,one doubt- can $\forall x\forall y$ be distributive over $\rightarrow$.

In Gate 2006 qsn (x,y) from the same relation but here (x,y) may not from the same relation.

0

precedence order of operator -

https://alchemy.cs.washington.edu/user-manual/4_1First_Order_Logic.html

57 votes

**A)** lets take R(x,y) means x is divisible by y.

X= {6,8,9}

Y={2,3}

For all x, there exists any y such that x is divisible by y. It is true in our example.

but here take y individually, no single y is capable of dividing all x. So it neither implies nor double implies the second one.

So FALSE.

**B)** lets take ...

R(x,y) means x is divisible by y ,

S(x,y) means means x/y =2 or 3

X={4,6,11} Y={2,3}

(∀x[∃yR(x,y)→S(x,y)])→∀x∃yS(x,y)

*(Always, make the LHS intentionally true, If we can make RHS false, then it is not tautology)*

Here for all X, there exists a y such that ..."if x is divisible by y then x/y=2 or 3".... 11 is not divisible by any y...so no problem.

So LHS is true.

Go to RHS. For all x, there exists a y such that x/y=2 or 3. Which is false. 11/2 and 11/3 are neither 2 nor 3

Here T-> F so False. Not tautology.

** D) **

X= 8,12,16

Y= 2,4

For all X and for all Y, Y divides X....... It does not imply X divides Y. So FALSE.

We are only left with option C. So it is the ans. The method I follow is to disprove it. Not to prove it. So here also you can try something by taking any example. You cant disprove it. **C is the ans.**

0

Nice one .. But i have one doubt, can we disprove it by some other example ? Bcoz it is quite difficult to come up with such example very fast ?

6

Just follow 3-4 types of examples always.

Pick on your own and apply them, and see how good it works.

Practice questions on it first.

Disproving using example is not that difficult, proving is.

Pick on your own and apply them, and see how good it works.

Practice questions on it first.

Disproving using example is not that difficult, proving is.

0

In option (B) isn't LHS false as there exists no y that could divide 11. Exists means atleast 1 (>=1).

0

@Ahwan in the B part on LHS, is S(x,y) taking 'y' as free variable or using same y which is checked for "if R(x,y)??

X={4,6,11} Y={2,3}

(∀x[∃yR(x,y)→S(x,y)])→∀x∃yS(x,y)

0