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

Are the terms "satisfiability" and "valid" equivalent??
0
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

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

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
+3
Awesome explanation @sachin Mittal  (Y)
0
thnks :)
+1
Correct and clear explanation sachin..
0
Can you please explain how we can rewrite

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

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?

0
sir u r really talented
+1

Nice explanation.Thanks,  Sachin Mittal 1.

0

Bi conditional Truth table ...

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

@Jordan Thank you so much. :)

+2

@Sachin 

(∀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]
F⇒F
T

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
0
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 .
0
Sorry, my answer was wrong. I had missed the possibility of $x = y$. Also, two interpretations are possible here as shown now.
0
@Happy-Mittal These are the two cases for 'precedence'.
+1
The scope of quantified variable is determined by square brackets, which is clear from the question and hence your second interpretation is correct.
+1
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.
+1
That make sense. I'll change. Thanks :)
+1
@Arjun, So the LHS reduces to just ~P(X), make this change for more correctness & Readablity !
0

Can you verify best answer selected?

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

0

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

0
(∀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
0

@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

35,458 questions
42,701 answers
121,326 comments
42,105 users