Results 1 to 8 of 8

Math Help - Predicate Logic HELP.

  1. #1
    Newbie
    Joined
    Feb 2010
    Posts
    1

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Mar 2009
    Posts
    90
    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.

    Hmmm... what about:
    [(\forall x)(\exists y)(x \text{ beats } y) \rightarrow (x = y)] \rightarrow "the negation of the above." ? Does that work?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Apr 2008
    Posts
    1,092
    1.

    \exists x \in C \forall y <br />
\in C: y \neq x, f(x, y) and \forall y \in C<br />
: 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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Mar 2009
    Posts
    90
    Quote Originally Posted by icemanfan View Post
    1.

    \exists x \in C \forall y <br />
\in C: y \neq x, f(x, y) and \forall y \in C<br />
: 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)]
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Thanks
    1
    Hello everyone
    Quote Originally Posted by XDemonoid View Post
    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.

    Grandad
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Mar 2009
    Posts
    90
    Hi, I went and asked one of the PhD students at the uni about this question, and he explained it very well:

    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)
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Mar 2009
    Posts
    90
    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!
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member
    Joined
    Mar 2009
    Posts
    90
    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...
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Predicate Logic
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 5th 2010, 08:53 AM
  2. Predicate Logic
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: April 29th 2010, 04:51 PM
  3. Predicate Logic
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 21st 2010, 09:39 PM
  4. predicate logic
    Posted in the Discrete Math Forum
    Replies: 10
    Last Post: March 6th 2009, 07:04 AM
  5. More predicate logic
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 4th 2009, 07:45 PM

Search Tags


/mathhelpforum @mathhelpforum