# Predicate Logic HELP.

• Feb 15th 2010, 12:48 PM
XDemonoid
Predicate Logic HELP.
Ok, I need to convert an English sentence to predicate logic.

The domain is C , the set of Olympic competitors.

f(x,y) = x is faster than y
s(x,y) = x is the same person as y.
b(x,y) = x beats y
w(x) = x is the winner.

Translate the following English statements into precise symbolic notation. Only use the predicates and domain defined above.

1. There is exactly one fastest competitor.
2. If every competitor beats exactly one other competitor, then there is no winner.

Thank you guys
• Feb 15th 2010, 01:32 PM
bmp05
hello XDemonoid,
well, for 1 you need something like:
there exists a winner, such that for all y, if y beats x then x is the same person as y.

and for the second part... I dunno. I mean the consequent of the implication: "then there is no winner" is going to be the negation of part 1, I believe. So, you need to find a way to describe the antecedent, "If every competitor beats exactly one other competitor", and I think you're going to need the "x is the same person as y" predicate to describe the "exactly one" part.

$[(\forall x)(\exists y)(x \text{ beats } y) \rightarrow (x = y)] \rightarrow$ "the negation of the above." ? Does that work?
• Feb 15th 2010, 01:49 PM
icemanfan
1.

$\exists x \in C \forall y
\in C: y \neq x, f(x, y)$
and $\forall y \in C
: y \neq x, \exists z \in C: f(z, y)$

I don't know how to code the logical "and," but you get the idea.
• Feb 16th 2010, 01:38 AM
bmp05
Quote:

Originally Posted by icemanfan
1.

$\exists x \in C \forall y
\in C: y \neq x, f(x, y)$
and $\forall y \in C
: y \neq x, \exists z \in C: f(z, y)$

I don't know how to code the logical "and," but you get the idea.

Oh yeah, great work icemanfan! I think you're right- as you see, I'm no expert at this and I find 2 Quantors difficult and 3 nigh on impossible, but, you're saying that:

"there exists a swimmer, so that when he's not competing against himself, he's faster than every other swimmer."

$(\exists s)(\forall r)[\neg s(s, r) \rightarrow f(s, r)]$
• Feb 16th 2010, 05:01 AM
Hello everyone
Quote:

Originally Posted by XDemonoid
Ok, I need to convert an English sentence to predicate logic.

The domain is C , the set of Olympic competitors.

f(x,y) = x is faster than y
s(x,y) = x is the same person as y.
b(x,y) = x beats y
w(x) = x is the winner.

Translate the following English statements into precise symbolic notation. Only use the predicates and domain defined above.

1. There is exactly one fastest competitor.
2. If every competitor beats exactly one other competitor, then there is no winner.

Thank you guys

First of all, you don't need to keep saying
$x \in C$, $y \in C$, etc
because $C$ is the domain, the universe from which all elements are chosen. (Which at least makes things a bit easier.)

Then for number 1 (and this is complicated, so bear with me) I think you need to say:
There is a competitor, $x$, that is faster than all others ( $y$), and whenever we find a competitor, $z$, that is faster than all others, then $x$ and $z$ are the same person.
The second half is there to ensure that there is only one $x$ that is faster than all others.

Now to begin translating this. The first phrase 'There is an $x$' is obviously $\exists x$. But the phrase 'all others ( $y$)' is a bit tricky. You can't just say $\forall y$, because that will include $x$, and I think we must assume that $x$ cannot be faster than itself. So we must include somewhere that $y$ and $x$ are not the same person.

So the first section, that states the existence of a fastest competitor is:
$\exists x\forall y[\neg s(x,y) \Rightarrow f(x,y)]$
Then the bit that makes $z$ a fastest competitor is, in the same way:
$\forall y[\neg s(z,y) \Rightarrow f(z,y)]$
We now need to say that whenever this second statement is true (in other words, for all $z$), then $x$ and $z$ are the same person. This will look like this:
$\forall z \forall y[ \neg s(z,y) \Rightarrow f(z,y)]\Rightarrow s(x,z)$
We now join this to the first phrase with a logical 'and':
$\exists x\Big[\Big(\forall y[\neg s(x,y) \Rightarrow f(x,y)] \Big)\land \Big(\forall z \forall y[ \neg s(z,y) \Rightarrow f(z,y)]\Rightarrow s(x,z)\Big)\Big]$
I don't know whether all the brackets are strictly necessary, or whether there's a simpler expression, but I think that works.

If I have time, I'll have a look at number 2.

• Feb 16th 2010, 05:20 AM
bmp05

1. $\exists x \in C (\forall y \in C \backslash\{ x \}: f(x, y))$

which kind of makes it cleear what the problem is. Then you have a syntax issue, because you're not allowed to use set notation, but after first writing it down this way you can more easily make the change to:

$\exists x \in C : \forall y \in C: x \neq y \rightarrow f(x, y)$ or

$(\exists x)(\forall y)(x \neq y \rightarrow f(x, y))$

2. The first thing to do with 2 is to write down the implikation, which is fairly easy:
"something" $\rightarrow \forall x \in C: \neg w(x)$
and then think about the first half of the sentence:

$[\forall x \in C : \exists y \in C : f(x, y) \wedge \forall z \in C \backslash\{ x, y \} \rightarrow \neg f(x, z)] \rightarrow \neg w(x)$

"For all swimmers x there exists a swimmer y so that x is faster than y and so that there exists no other swimmers faster than that x faster than y."

$[\forall x \in C \exists y \in C : f(x, y) \wedge \forall z \in C: y \neq z \wedge x \neq z \rightarrow \neg f(x, z)] \rightarrow \neg w(x)$
• Feb 16th 2010, 05:25 AM
bmp05
Thanks grandad, I'll have a detailed look at what you have written. This question is turning out to be a real thriller- unfortunately, I have to go out for a while now. Thanks again!
• Feb 16th 2010, 08:54 AM
bmp05
Well, the following solution to part 2 is from my maths tutor, but I really think I have to look at Quantifiers again.

$(\forall x) [ (\forall s)(\exists r)(\forall r') [b(s,r) \land (\neg s(r,r') \rightarrow \neg b(s,r'))] \rightarrow \neg w(x)]$

Now to work through the solution...