Translate the following English statements into predicate logic formulae. The domain is the set of integers. Use the following predicate symbols, function symbols and constant symbols.

  • Prime(x) iff x is prime
  • Greater(x, y) iff x > y
  • Even(x) iff x is even
  • Equals(x,y) iff x=y
  • sum(x, y), a function that returns x + y
  • 0,1,2,the constant symbols with their usual meanings

I tried them, but don't know if they're correct.

(a) The relation Greater is transitive.

(∀x(∃y(∃z (Greater(x,y) ∧ Greater(y,z) -> Greater(x,z))))

(b) Every even number is the sum of two odd numbers. (Use (¬Even(x)) to express that x is an odd number.)

(c) All primes except 2 are odd.

(∀x(Prime(x) ∧ ¬(Equals(x,2) -> ¬Even(x))

(d) There are an infinite number of primes that differ by 2. (The Prime Pair Conjecture)

(∀x(∃y (Prime(x) ∧ Equals(y,sum(x,2)) ∧ Prime(y)))) From what I remember, we aren't suppose to put predicate symbol (sum(x,2)) inside Equals. How do I do this?

(e) For every positive integer, n, there is a prime number between n and 2n. (Bertrand's Postulate) (Note that you do not have multiplication, but you can get by without it.)

(∀x(∃y (Greater(x,1) -> (Greater(x,y) ∧ Prime(y) ^ Greater(y, Sum(x,x))))) -Same problem as d.

  • (a) you want to universally quantify all three variables. Transitivity imposes a constraints on all triples of elements.

  • (b) You want to say that for every number that is even there are two numbers that are odd and such that their sum equals the given number.

  • (c) is correct. (Assuming that conjunction binds more strongly than implication.)

  • (d) What you say there is that every natural number is prime and has a twin. That's not the twin-prime conjecture. Note that "sum" is a function symbol, not a predicate symbol.

  • (e) You should switch the arguments to "Greater."


For d) and e): $sum$ is a function that denotes an object (the return value of the function), and therefore it can be used as an argument inside a predicate just fine!

However, as Fabio pointed out, your symbolization for d is not correct. To get an infinite number of twin primes, you can say that there is at least one twin prime, and that for every twin prime there is a larger twin prime.

Your e )is almost correct, but you need to use $Greater(y,x)$ and $Greater(sum(x,x),y)$. And if you really want to capture Bertrand's postulate (for any $x \ge 1$ there is a prime $y$ such that $x < y \le 2x$) you need to use $(Greater(sum(x,x),y) \lor Equals(sum(x,x),y))$ at the end.

Also: Careful with those parentheses! for example, c) should be $\forall x ((Prime(x) \land \neg Equals(x,2)) \rightarrow \neg Even(x))$


Bram has pointed out that in $(e)$ you need to add $Equals(sum(x,x),y)$ to the consequent but to make this translation the perfect one you also have to add $Equals(x,1)$ to the antecedent to capture the $x \ge 1$ part of the Bertrand's Postulate.

Lets look at $(d)$ now. For clearance I'm using slightly different notation for atomic formulas $$ \begin{array}{} P(x) & \text{for Prime (x)} \\ E(x,y) & \text{for Equals (x, y)} \\ G(x,y) & \text{for Greater (x, y)} \end{array} $$ Now we can translate $(d)$ into the following formula:

$$\forall x ((P(x) \land \exists y(P(y) \land E(y, sum(x, 2))) \to \exists z(P(z) \land G(z, x) \land \exists w(P(w) \land E(w, sum(z, 2)))))$$

It says that, for every $x$ which is $prime$ and has a $twin\ prime$, which is greater than $x$ by $2$, we can find a $prime\ z$ which is greater than $x$ and also have a $twin\ prime$.


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.