Writing Quantified Statements with Predicate Logic

I have a few examples I need help working out. I feel pretty comfortable with most English to Predicate logic statement problems but there were a few I was unable to figure out on my own and I could use some guidance.

This is what we were given: Write the following statements in predicate logic using the binary predicates livesIn(x, y) (meaning x lives in location y), owns(x, y) (meaning x owns y), faster(x, y) (meaning x is faster than y) and unary predicates (with a single parameter), such as car(x) (meaning x is a car) as appropriate. You can also use the equality predicate.

The questions I was unable to answer are:

1) No Two distinct (different) algorithms are equally fast.

2) A prime number is an integer that is not divisible by any smaller integer except for 1.

3)A number is divisible by 6 if and only if it is the product of 2 and some integer and it is the product of 3 and some integer.

These tripped me up most likely because of the length of them compared to the others as well as the smaller or equally aspects which I'm unsure of how to represent in Predicate logic.

Any advice would be much appreciated! Thank you!

1) says "For any two distinct algorithms, one is faster than the other" – or, in even more logic-like English, "For all algorithms $x, y$ with $x \neq y$, either $x$ is faster than $y$ or vice-versa". Representing that symbolically: $$\forall x \forall y\,((x\neq y \wedge algorithm(x) \wedge algorithm(y)) \to (faster(x,y) \vee (faster(y,x)) \text{.}$$

For 2) and 3) it's helpful to define the predicate "$x$ divides $y$": $$divides(x,y) \iff integer(x) \wedge integer(y) \wedge \exists u\, (integer(u) \wedge x \times u = y) \text{.}$$ Now 3) becomes simple. Notice that:

• "$n$ is divisible by 6" is just $divides(6,n)$,
• "$n$ is the product of 2 and some integer" is just $divides(2,n)$,
• and similarly for being the product of 3 and some integer.

So 3) can be expressed as: $$\forall n\, (divides(6,n) \leftrightarrow (divides(2,n) \wedge divides(3,n)))$$

Finally, 2), in logic-like English, says: n is a prime iff n is an integer, and for every integer x, if x < n and x ≠ 1 then x does not divide n. Expressing that symbolically is left as an exercise for the reader.

• Thanks this helps out quite a bit! – mm19 Oct 30 '15 at 1:18
• You're welcome. – BrianO Oct 30 '15 at 1:20