edited by
15,609 views
113 votes
113 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\)
edited by

6 Answers

Best answer
305 votes
305 votes

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 \text{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}]$

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

$\text{LHS}:(\forall x)[ P_x ⇔(\forall y)[\neg Q_{xy}]]$

consider only $(\forall \mathbf{y)[\neg Q_{xy}]}$ it says all values of $y$ does not divide $x$, but there will be at least one value of $y$ (when $y=x$, or when $y=1$) that divides $x$, i.e. $\mathbf{[\neg Q_{xy}]}$ is not true for all values of $y$.  $(∀ \mathbf{y)[¬Q_{xy}]}$ is false.

Now LHS becomes $(∀x)[P_x \Leftrightarrow \text{False}]$, "$P_x \Leftrightarrow \text{False}$" this means $P_x$ is False, which is same as writing "$ \neg P_x$".

Finally, we reduced LHS to $(∀x)[\neg P_x]$

$α: (∀\mathbf{x)[¬P_x]}⇒(∀x)[¬P_x]$  (which is trivial, $P(x)⇒ P(x)$ is trivially true)

Hence $(∀\mathbf{x)[¬P_x]}⇒(∀x)[¬P_x]$  is trivially true for any $P(x)$, doesn't matter if $P(x)$ is for prime number or for composite number $(I1$ or $I2)$.

$ ⇒ I1$ and $I2$ both satisfies $α$.

Option D.

edited by
61 votes
61 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. 

edited by
3 votes
3 votes

all logic concept is based on $T\rightarrow F$ .

1st let's see for $I_{2}$

If we somehow make a combination such that the implication will false, then we're done.

Now we have only one way to make an implication false, which is $T\rightarrow F$ combination.

If the domain is composite(means not prime) then right side of the $\alpha$ is always T, which implies we can't make $\alpha$ false.    $P_{x} = F$   i.e    $\sim P_{x} = T$ always.

So, $I_{2}$ satisfies $\alpha$.

 

Now, let's come in $I_{1}$

In $I_{1}$,  $\sim {Q_{yy}}$ is always false because in any circumstances y divides y.

now, try to make $T\rightarrow F$ combination.

let's forget about quantifiers & treat $\alpha$ as $[P_{x} \Leftrightarrow [Q_{xy}\Leftrightarrow Q_{yy}]] \rightarrow \sim P_{x}$.

take $P_{13}$, RHS is F.  LHS is $[P_{13} \Leftrightarrow [Q_{13.1}\Leftrightarrow Q_{1.1}]]$

So, $[P_{13} \Leftrightarrow [T\Leftrightarrow F]]$

$[P_{13} \Leftrightarrow F]$  = $F$, which means $F\rightarrow F$ implies T

So, using any number(composite or prime), we can't make the implication false.

So, $I_{1}$ also satisfies $\alpha$.

Option D is the answer.

 

 

0 votes
0 votes

Counter Example for I1 case :

X={11,121 }

Y={11}

 

Counter Example for I2 case :

X={4,6,2}

Y={2}

 

option D

Answer:

Related questions