Logic: Number x is a square of a prime number. Difference between conjunction and implication

63 Views Asked by At

Number x is a square of a prime number

Is there some difference if do that it like this:

$∃_{p}$$[(∀_{n∊N} $ $ n|p ⇒ n=p $ v $ n=1) ⋀ (p\neq1)] ⇒ x = p*p$

or

$∃_{p}$$[(∀_{n∊N} $ $ n|p ⇒ n=p $ v $ n=1) ⋀ (p\neq1)] ⋀ x = p*p$

And if there is, when i should use implication and when conjunction in tasks like this one.

1

There are 1 best solutions below

0
On BEST ANSWER

Putting an implication directly under an $\exists$ is almost always wrong.

Here your first attempt says

There is some $p$ such that if $p$ is a prime, then $x$ is its square.

And that is always true, no matter what $x$ it -- namely, you can just set $p$ to be $4$. Since $4$ is not a prime, the implication is automatically true, and that single example is enough to make the $\exists$ true.

The second attempt is much better (though bof may or may not be right when he thinks your bracketing is off; depends on your conventions for how tightly quantifiers bind syntactically):

There is a $p$ such that $p$ is a prime and $x$ is its square.


On the other hand for $\forall$ you would typically use an implication under the quantifier to limit which possible values you're interested in. As before, the implication will be automatically true when the condition is not satisfied, and for $\forall$ it is the true case that does not influence the truth value of the entire $\forall$ formula.