Which of the following statements express the given sentence? Why not both?

Question

Suppose that the possible values of all variables are positive integers. Moreover, suppose that; D(x,y) stands for “x divides y” P(x) stands for “x is prime” .

Express the following statement using quantifiers, variables, logical connectives, positive integers, the symbols P and D.

"Every positive integer which is prime divides some positive integer which is not prime.”

---

Answers:

1) (∀x)(∃y) P(x)→( ¬P(y) Λ D(x,y) )

2) (∀x)(∃y) ( P(x) Λ ¬P(y) )→ D(x,y)

---

The first answer is obviously true. However, I could not understand whether the second answer is true or not. If the second answer does not "express" exactly the same logical statement with the given sentence, then is there any relation between these two answers (i.e. can we deduce any of the answers from the other) ?

Answer 1

The second “answer” is a true statement, but does not express the same thing as the first. To see that they are not equivalent, suppose that D(x,y) meant that x=y.

Then the first “answer” would be a false statement, since there would exist a prime X such that there was no non-prime y that equaled it.

However, the second “answer” would still be a true statement, since for every prime x there exists a prime y, which makes the first part of the implication false, making the statement true.

In the second “answer”, you can replace D(x,y) by any proposition, and the statement would still be true.

Answer 2

Both of the statements that you wrote are logically true within the given domain, which means that they are logically equivalent. However, the second one does not represent exactly the sentence given. Now to see that, it might be clearer to covert your statements to syntax. Remember: $p\rightarrow q$ is equivalent to $\lnot p \lor q$, and $\exists$ distributes over $\lor$. So your statements become

1). \begin{align*}&(\forall x)(\exists y) [p(x)\rightarrow (p(y)\wedge D(x,y))] \\\equiv & (\forall x)(\exists y) [\lnot p(x)\lor(p(y)\wedge D(x,y))] \\\equiv & (\forall x)[ \lnot p(x)\lor(\exists y)(p(y)\wedge D(x,y))] \end{align*}

2). \begin{align*}&(\forall x)(\exists y) [p(x)\wedge \lnot p(y)\rightarrow D(x,y)] \\\equiv & (\forall x)(\exists y) [\lnot p(x)\lor p(y)\lor D(x,y))] \\\equiv & (\forall x) [\lnot p(x)\lor (\exists y)p(y)\lor (\exists y)D(x,y))] \end{align*}

It is clearer now that the second statement is true for a wider range of $y$'s, given $x$. For instance, for $x=2$, the choice $y=3$ makes the second statement true (since $p(3)$ is true). However, $y=3$ does not make the first statement true, since $D(2,3)$ is false.