3
$\begingroup$

Consider a language of predicate logic with a constant sybol $1$, with unary predicate symbols $prime$, $odd$ and $even$, and with a binary predicate symbol $|$.

The intended domain of discourse is the set of non-negative integers, and the intended interpretation of the predicate and constant symbols is what their names suggest. e.g. $prime(x)$ means that $x$ is a prime number, and the binary predicate symbols $|$ represents the "divides" relation, written in infix notation, so $x|y$ means that $y$ can be divided by $x$ without reminder.

Am I correct in my translations of the following sentences into predicate logic with equality, using only the above predicate and constant symbols?

a) One is an odd number.

My attempt: $odd(1)$

b) All prime numbers are odd or even.

My attempt: $\forall x (prime(x) → (odd(x) ∨ even(x)))$

c) No prime number is both odd and even.

My attempt: $ \neg\exists x (prime(x) ∧ (odd(x) ∧ even(x))$

d) Some even numbers can be divided by an odd number without remainder.

My attempt: $ \exists x \exists y (even(x)|odd(y))$

e) Prime numbers can only be divided by one and by themselves without remainder

My attempt: $ \forall x (prime(x) → prime(x)|1 ∨ prime(x)|prime(x)))$


Second attempt at d) $ \exists x \exists y (even(x) ∧ odd(y) ∧ y|x)$

Second attempt at e) $\neg \exists x \exists y (prime(x) ∧ y|x) $ where $y \ne 1$ or $y \ne x$


Fourth attempt at e)

$\neg \exists x \exists y (prime(x) ∧ y|x ∧ y \ne 1 ∧ y \ne x)$

$\endgroup$
  • 1
    $\begingroup$ They all look correct except you need to add two closing parentheses at the end of c) But your second attempt for d) is correct, and your fourth attempt for e) is also correct. Good job! :) $\endgroup$ – Bram28 Jun 21 '17 at 2:53
4
$\begingroup$

a,b,c are correct. Issues with d. First, odd and even are switched ($x|y$ means $x$ divides evenly into $y$, not the other way around). Second, more importantly, it should be $\exists x\exists y(even(x)\wedge odd(y) \wedge y|x)$ ($odd(x)|even(y)$ has no meaning).

Same two issues with e. You can't use $1|prime(x)$ to mean "x is prime and 1 divides x". For that you need to say $prime(x)\wedge 1|x.$

There is a more important issue with $e.$ What you're going for says that any prime number is divisible by one and itself. That's true of any number and not what you're asked to say. You need to say that it's divisible only by one and itself.

$\endgroup$
  • $\begingroup$ See my update answer: However I am not sure how can I say "only by one and itself" for e? $\endgroup$ – Mark Donaghue Jun 21 '17 at 1:18
  • $\begingroup$ @MarkDonaghue Prime is about there being no nontrivial divisors, so you can write "there does not exist a $y$ such that $y$ is a nontrivial divisor of $x.$", i.e. a divisor that is not one or itself. $\endgroup$ – spaceisdarkgreen Jun 21 '17 at 1:21
  • 1
    $\begingroup$ How about my attempt now? $\endgroup$ – Mark Donaghue Jun 21 '17 at 1:27
  • 1
    $\begingroup$ @MarkDonaghue $\forall x (prime(x) \rightarrow \forall y ((y \not = 1 \land y \not = x ) \rightarrow \neg y|x))$ $\endgroup$ – Bram28 Jun 21 '17 at 2:57
  • 1
    $\begingroup$ @MarkDonaghue Also, $x \not =y $ is pretty standard logic notation, but it is indeed short for $\neg x =y$ $\endgroup$ – Bram28 Jun 21 '17 at 2:58
3
$\begingroup$

Okay until (d).   That is not how the divides symbol operates.

d) Some even numbers can be divided by an odd number without remainder.

My attempt: $\exists x \exists y (even(x)|odd(y))$

odd() and even() are predicates, functions returning a true-or-false value.   They cannot be arguments for the divides binary operator.  

Also $a\vert b$ reads, "$a$ divides $b$".   That is, $b$ is divisible by $a$ without remainder; ie $b/a$ is an integer.

So... You wish to say there are some $x,y$ where $x$ is even, $y$ is odd, and $y$ (the odd number) divides $x$ (the even number).

$$\exists x~\exists y~\big(\operatorname{even}(x)\wedge \operatorname{odd}(y)\wedge y\vert x\big)$$

Now try $(e)$ again.


e) Prime numbers can only be divided by one and by themselves without remainder

Second attempt at e) $ \forall x (prime(x) → prime(x) ∧ 1|x ∨ x|x)$

No. You wish to say that: if any number, $x$, is prime then iff and only if any number, $y$, is $x$ or $1$, then $y$ divide $x$.

$${\forall x~\forall y~\Big(\operatorname {prime}(x)\to\big((y=1\vee y=x)\gets\hspace{-2ex}\to y\vert x\big)\Big)}$$


Third attempt at e) $\neg \exists x \exists y (prime(x) ∧ y|x) $ where $y \ne 1$ or $y \ne x$

"where" and "or" are not part of the language.   You do appear to be trying to say, "there does not exist an $x$ and an $y$ such that $x$ is primes, $y$ divides $x$, and $y$ is neither $1$ nor $x$". (aka "$y$ is not $1$ and $y$ is not $x$).

That is almost okay, but express this in symbols of the language. You also need to assert that a prime can be divided by $1$ and by itself.

$\endgroup$
  • $\begingroup$ See my update answer: However I am not sure how can I say "only by one and itself" for e? $\endgroup$ – Mark Donaghue Jun 21 '17 at 1:18
  • $\begingroup$ Say "If and only if $y$ equals $1$ or $y$ equals $x$, then $y$ divides $x$.", in symbols $\endgroup$ – Graham Kemp Jun 21 '17 at 1:26
  • 1
    $\begingroup$ How about my attempt now? $\endgroup$ – Mark Donaghue Jun 21 '17 at 1:26
  • $\begingroup$ @MarkDonaghue Improved, but needs work. $\endgroup$ – Graham Kemp Jun 21 '17 at 1:37
  • $\begingroup$ What about now? $\endgroup$ – Mark Donaghue Jun 21 '17 at 1:43
0
$\begingroup$

For the statement $(e)$ Graham Kemp has noticed in the comments that you have to explicitly assert that prime $x$ can be divided by $1$ and by itself. In a solution using implication and universal quantifier $$\forall x(prime(x)\to \neg\exists y(y|x\land y\ne 1\land y\ne x))$$ we have to add $(1|x\land x|x)$ to the consequent. So we end up with $$\forall x(prime(x)\to 1|x\land x|x\land \neg\exists y(y|x\land y\ne 1\land y\ne x))$$ But its a property of the binary operation $|$ on the set of positive integers that we can express using language of logic $\forall x(1|x\land x|x)$. I'm curious of how important to explicitly state this property in the translation.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.