The Gateway to Computer Science Excellence
+46 votes
6.5k views

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

  1. $\forall x \, \exists y \, R(x,y) \, \leftrightarrow \, \exists y \, \forall x \, R(x, y)$
  2. $( \forall x \, [\exists y \, R(x,y) \, \rightarrow \, S(x, y)]) \, \rightarrow \, \forall x \, \exists y \, S(x, y)$
  3. $[ \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)]$
  4. $\forall x \, \forall y \, P(x,y) \, \rightarrow \, \forall x \, \forall y \, P(y, x)$
in Mathematical Logic by Veteran (105k points)
edited by | 6.5k views
0
In option B in LHS(S(x,y)) is y a free variable ?

Just clearing my doubt
0
0
@Arjun sir plz explain option b how to check it
0
Can anyone explain option B and prove it not tautology ?
0
can we say bidirectional is same as logical equivalent ?
0
I think Yes

2 Answers

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

by Boss (13.6k points)
edited by
+4
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
+1
Because of the priority of ->. You can see the last part of given answer.
+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.
0
how u assume x<y & is there any other way to solve it not getting this
+6
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.
0

The below one is a tautology.

(xyP(x,y))(xyP(y,x)) 

How is this a tautology?

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

(xyP(x,y))(xyP(y,x)) 

                    or 

x y (P(x,y)  x y P(y,x))

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

(xyP(x,y))(xyP(y,x))  

+6
You should know the precedence rule. $\to$ has higher precedence than quantification.
+2

(xyP(x,y))(xyP(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
thanku sir
+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.
0
Then FALSE -> FALSE is TRUE.
0
How can LHS be true if the relation is not commutative?
0
Priority of "->" > "forall or existential"?
+1
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?

+1
yes, so the precedence I told is not obeyed here. I have updated the answer. See now.
+1
S​ir for D option , is it necessary to consider same domains  for x & y ?
0
yes the domain of x and y are not mentioned ,then how can we assume they are from same domain Arjun Sir?
+1
Yes, I do not think it is right to assume that. So, that is a stronger reason against option D.
+1
But according to Rosen, Quantification has the highest precedence?? Which one to follow??
+2
Of course follow Rosen, at least we can argue using Rosen. Wikipedia is not so authentic.
0
but why here implication has been given higher precedence??
0
Better option among choices :)
0

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

(∀xyP(x,y))→(∀xyP(y,x))  is a tautology.

But it wont be true for existential quantifiers right??

0
You mean both to $\exists$? Then it should because its just change of variable names.
0

yes i mean if the following a tautology??

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

If yes then y??

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.
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
+1
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.
+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
Thanku so much arjun sir for clearing the concept.
0

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.

+2
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 :)
+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.
0

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

+1

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

+1

@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
0
#madhab i am nt getting ur statement  "Sign <-> represents “not equivalent”." ?? can anyone explain ??
0
∃xα∧β∃xα∧β is (∃xα∧β)(∃xα∧β), and not ∃x(α∧β)∃x(α∧β).
0
Option d is not tautology as a relation may or may not be symmetric, therefore this won't be a tautology.
0

@, 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
+43 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.

by Boss (12.4k points)
edited by
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 ?
+5
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.
0
In option (B) isn't LHS false as there exists no y that could divide 11. Exists means atleast 1 (>=1).
+2
There are 3 things total in B.
1st one is made false to make total LHS true.
0
Got it. Thanks
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
@meghna "using same y which is checked for "if R(x,y)??"
0
Any other approach to solve option B

taking this type of counter-example in exam hall is difficult.
0
Very nicely explained!
Answer:

Related questions

+31 votes
8 answers
4
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
50,737 questions
57,312 answers
198,342 comments
105,033 users