GATE CSE
First time here? Checkout the FAQ!
x
+17 votes
1.5k views

Consider the following formula and its two interpretations \(I_1\) and \(I_2\).

\(\alpha: (\forall x)\left[P_x \Leftrightarrow (\forall y)\left[Q_{xy} \Leftrightarrow \neg Q_{yy} \right]\right] \Rightarrow (\forall x)\left[\neg P_x\right]\)

\(I_1\) : Domain: the set of natural numbers

\(P_x\) = 'x is a prime number'

\(Q_{xy}\) = 'y divides x'

\(I_2\) : same as \(I_1\) except that \(P_x\) = 'x is a composite number'.

Which of the following statements is true?

  1. \(I_1\) satisfies \(\alpha\), \(I_2\) does not
  2. \(I_2\) satisfies \(\alpha\), \(I_1\) does not
  3. Neither \(I_1\) nor \(I_2\) satisfies \(\alpha\)
  4. Both \(I_1\) and \(I_2\) satisfies \(\alpha\)
asked in Mathematical Logic by Veteran (64.6k points)  
edited by | 1.5k views

2 Answers

+25 votes
Best answer

 

@Arjun Sir plz verify this method.


$Q_{yy}$ is always True, this makes  $\neg Q_{yy}$ False.

Writing $(\forall y)[Q_{xy} \Leftrightarrow \neg Q_{yy}]$ is same as writing $(\forall y)[Q_{xy} \Leftrightarrow False]]$

This is equivalent to saying that, for all y $Q_{xy}$ is false and finally we can rewrite $(\forall y)[Q_{xy} \Leftrightarrow \neg Q_{yy}]]$ as $(\forall y)[\neg Q_{xy}]$

 

α: (∀x)[Px⇔(∀y)[¬Qxy]]⇒(∀x)[¬Px

LHS:(∀x)[Px⇔(∀y)[¬Qxy]]

consider only (∀y)[¬Qxy] it says all values of y does not divide x, It is true irrespective of x being prime or composite. Even if x is composite then only its factor divides x not all values.

Now LHS becomes (∀x)[Px⇔True], "Px⇔True" this means Pis True, which is same as writing "Px" only.

Finally, we reduced LHS to (∀x)[Px]

α: (∀x)[Px]⇒(∀x)[¬Px

LHS: (∀x)[Px].

LHS is false for I1 bcoz not all x are primes False ⇒ Anything is True. For I1 α is true hence I1 satisfies α.

Similarly, LHS is false for I2 also bcoz not all x are composite. hence I2 satisfies α.

Option D.

answered by Boss (7.1k points)  
selected by
Awesome explanation @sachin Mittal  (Y)
thnks :)
Correct and clear explanation sachin..
Can you please explain how we can rewrite

(∀y)[Qxy⇔¬Qyy]](∀y)[Qxy⇔¬Qyy]] as (∀y)[¬Qxy]?

I have doubt in this solution.As mentioned 

"consider only (∀y)[¬Qxy] it says all values of y does not divide x, It is true irrespective of x being prime or composite. Even if x is composite then only its factor divides x not all values."

How is this true always? when y and x are same in case of prime/non prime  then it will divide.

 (∀y)[¬Qxy] says that there is no number that divides x and so it should be false because if there is one case which is not satisfying for all then it is not FOR ALL.Please correct me if i understood it wrong.

Please tell me if following approach will work:-

α:(∀x)[Px⇔(∀y)[Qxy⇔¬Qyy]]⇒(∀x)[¬Px]

We know y will always divide y(assuming 0 is not a natural number as in group theory it says 0 is natural number set but some says if 0 is included then it becomes whole number.)

A Qyy is always false,means Qxy=False.

So i can reduce this to:-

(∀x)[Px⇔(∀y)[False]]

which means 

(∀x)[Px= false]

(∀x)[false]

and false implies anything must be true?

Please tell me if i am wrong in this approach?

sir u r really talented

Nice explanation.Thanks,  Sachin Mittal 1.

+25 votes

$\alpha: (\forall x)\left[P_x \Leftrightarrow (\forall y)\left[Q_{xy} \Leftrightarrow \neg Q_{yy} \right]\right] \Rightarrow (\forall x)\left[\neg P_x\right]$

This is can be interpreted as:

  • $\alpha: \left( (\forall x)\left[P_x \Leftrightarrow (\forall y)\left[Q_{xy} \Leftrightarrow \neg Q_{yy} \right]\right] \right) \Rightarrow \left((\forall x)\left[\neg P_x\right] \right)$

See the RHS. It says $P(x)$ is false for any natural number. But there are natural numbers which are prime and hence this RHS is FALSE. Now, to make $\alpha$ TRUE, LHS must be FALSE for any $x$. Here, LHS is bit complex, so lets consider it separately. 

$ (\forall x)\left[P_x \Leftrightarrow (\forall y)\left[Q_{xy} \Leftrightarrow \neg Q_{yy} \right]\right] $

LHS is TRUE only if the given implication is TRUE for all $x$. Here the rightmost double implication $(\forall y)\left[Q_{xy} \Leftrightarrow \neg Q_{yy} \right]$ is always FALSE, because $x$ can be equal to $y$ and hence forall can never be TRUE. So the LHS reduces to just $(\forall x) \neg P(x)$ and returns FALSE as we have prime as well as non-prime natural numbers. So, FALSE $\Rightarrow$ FALSE returns TRUE making both $I_1$ and $I_2$ satisfy $\alpha$. D choice. 

 

answered by Veteran (294k points)  
edited by
option given by ,
made easy - (D) ,
GK publication - (A) ,
Ankur Gupta website - (C) ,
and happy mittal sir - (C) , http://www.cse.iitd.ac.in/~mittal/gate/gate_math_2003.html
@ Arjun sir , I think you are right(B) , but I am still doubt , please remove my doubt , with the help of a example .
Sorry, my answer was wrong. I had missed the possibility of $x = y$. Also, two interpretations are possible here as shown now.
@Happy-Mittal These are the two cases for 'precedence'.
The scope of quantified variable is determined by square brackets, which is clear from the question and hence your second interpretation is correct.
Also, your first interpretation doesn't make sense, as once we are arguing about all x, then we don't write $\forall x$ inside that, we are anyway arguing about every x.
That make sense. I'll change. Thanks :)
@Arjun, So the LHS reduces to just ~P(X), make this change for more correctness & Readablity !
Answer:

Related questions



Top Users Sep 2017
  1. Habibkhan

    6836 Points

  2. Arjun

    2310 Points

  3. Warrior

    2306 Points

  4. rishu_darkshadow

    2092 Points

  5. A_i_$_h

    2004 Points

  6. nikunj

    1980 Points

  7. manu00x

    1750 Points

  8. Bikram

    1744 Points

  9. SiddharthMahapatra

    1718 Points

  10. makhdoom ghaya

    1690 Points


26,038 questions
33,650 answers
79,695 comments
31,069 users