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

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