The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+30 votes
2.1k 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 (68.9k points)
edited by | 2.1k views
What does "satisfies" mean here?? (Does it mean "satisfiability"?)

Are the terms "satisfiability" and "valid" equivalent??

2 Answers

+54 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 Veteran (13.3k 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.

Bi conditional Truth table ...

Just for thanking you I created account

Whenever I encounter your answer I can be assure that it must be checked or from trusted reference.

Thanks @sachin for your great effort and indeed wonderful explanation :)

@Jordan Thank you so much. :)

+30 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 (332k 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 !

Can you verify best answer selected?

In that LHS: (∀x)[Px].But LHS should be reduced to LHS: (∀x)[¬Px].

@rahul sharma 5 (∀x)[Px<->TRUE] reduced to (∀x)[Px] because final value depend on Px only,expand and see yourself !

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

Now [Qxy⇔¬Qyy] becomes false as mentioned in answer.

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

(∀x)[Px⇔[False]]

(∀x)[¬Px]

Please tell if i am wrong

@rahul sharma 5 correct !

Answer:

Related questions



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

32,732 questions
39,309 answers
110,280 comments
36,733 users