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.
Best Answer
(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."