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.”


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) ?

  • 2
    $\begingroup$ Please try to make the titles of your questions more informative. For example, Why does $a<b$ imply $a+c<b+c$? is much more useful for other users than A question about inequality. From How can I ask a good question?: Make your title as descriptive as possible. In many cases one can actually phrase the title as the question, at least in such a way so as to be comprehensible to an expert reader. You can find more tips for choosing a good title here. $\endgroup$
    – Shaun
    Commented Aug 4, 2019 at 19:57
  • $\begingroup$ ""Every positive integer which is not prime divides some positive integer which is not prime.”" Is this a typo. Did you mean ""Every positive integer which is prime divides some positive integer which is not prime.”" as that is what the two sentences say. $\endgroup$
    – fleablood
    Commented Aug 4, 2019 at 20:22
  • $\begingroup$ That's right. I'm so sorry for that. I have just editted it. Thanks, $\endgroup$
    – boyler
    Commented Aug 4, 2019 at 21:17

2 Answers 2


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.


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.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .