GATE2015-2-55

Question

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

• A. $\forall x \, \exists y \, R(x,y) \, \leftrightarrow \, \exists y \, \forall x \, R(x, y)$
• B. $( \forall x \, [\exists y \, R(x,y) \, \rightarrow \, S(x, y)]) \, \rightarrow \, \forall x \, \exists y \, S(x, y)$
• C. $[ \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)]$
• D. $\forall x \, \forall y \, P(x,y) \, \rightarrow \, \forall x \, \forall y \, P(y, x)$

Comments

In option B in LHS(S(x,y)) is y a free variable ?

Just clearing my doubt

---

may be this link will help you...

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

---

@Arjun sir plz explain option b how to check it

---

Can anyone explain option B and prove it not tautology ?

---

can we say bidirectional is same as logical equivalent ?

---

I think Yes

Answer 1

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

Comments

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

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.

---

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

---

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

---

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.

---

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.

---

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.

---

@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 ?

---

@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

---

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 given that the quantifiers Forall (universal quantification) and Exist (existential quantification) have higher precedence than all Logical operators from propositional calculus.

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

---

@Hemant Parihar

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)

---

@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?

---

@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?

---

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.

---

∀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

---

@Warrior the quantifiers should be evaluated first 

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

---

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

---

∃xα∧β∃xα∧β is (∃xα∧β)(∃xα∧β), and not ∃x(α∧β)∃x(α∧β).

---

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

---

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

---

precedence order of operator -

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

Answer 2

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.

Comments

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 ?

---

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.

---

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

---

There are 3 things total in B.
1st one is made false to make total LHS true.

---

Got it. Thanks

---

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

 

---

@meghna "using same y which is checked for "if R(x,y)??"

---

Any other approach to solve option B

taking this type of counter-example in exam hall is difficult.

---

Very nicely explained!