The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+34 votes

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 (59.4k points)
edited by | 2.4k views
What does "satisfies" mean here?? (Does it mean "satisfiability"?)

Are the terms "satisfiability" and "valid" equivalent??
satisfiability means true for at least one instance, valid means always true(true for all instances).

2 Answers

+61 votes
Best answer

Given: $(\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])\\$
$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


consider only (∀y)[¬Qxy] it says all values of y does not divide x, but there will be atleast one value of y (when y=x, or when y=1) that divides x, i.e. [¬Qxy] is not true for all values of y.  (∀y)[¬Qxyis false.

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

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

α: (∀x)[¬Px]⇒(∀x)[¬Px]  (which is trivial, P(x)⇒ P(x) is trivially true)

Hence (∀x)[¬Px]⇒(∀x)[¬Px]  is trivially true for any P(x), doent matter if P(x) is for prime number or for composite number (I1 or I2).

 ⇒ I1 and I2 both satisfies α.

Option D.


Thanks Soumya29 for suggesting edit.

answered by Boss (15.6k points)
edited 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:-


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


which means 

(∀x)[Px= 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. :)



(∀y)[¬Qxy] can also be interpreted as -
¬∃(y)[Qxy] - There doesn't exist a number y such that y divides x.
Which is false always as 1 divides every number - Counter-example
So LHS:(∀x)[Px⇔(∀y)[¬Qxy]] reduced to (∀x)[Px⇔False] .
I can write it as (∀x)[¬Px
(∀x)[¬Px] ⇒ (∀x)[¬Px]

Correct me if I am wrong.  :)

+33 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 (342k points)
edited by
option given by ,
made easy - (D) ,
GK publication - (A) ,
Ankur Gupta website - (C) ,
and happy mittal sir - (C) ,
@ 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 !


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




Please tell if i am wrong

@rahul sharma 5 correct !


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

35,458 questions
42,701 answers
42,105 users