Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Propositional Logic problem

  1. Jan 27, 2008 #1

    cepheid

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    1. The problem statement, all variables and given/known data

    Richard is either a knight or a knave. Knights always tell the truth, and only the truth; knaves always tell falsehoods, and only falsehoods. Someone asks, "Are you a knight?" He replies, "If I am a knight, then I'll eat my hat."

    a) Must Richard eat his hat?

    b) Set this up as a problem in propositional logic. Introduce the following propositions: p = "Richard is a knight" and q = "Richard will eat his hat." Translate what we are given into propositional logic i.e. re-write the premises in terms of these propositions.

    c) Prove that your answer from part (a) follows from the premises you wrote in (b)

    3. The attempt at a solution

    I didn't have an off-the-cuff answer, so I skipped to part (b). We have

    p: Richard is a knight
    q: Richard will eat his hat
    r: Richard's response is true

    If Richard is a knight, then his response is true. So we have:

    [tex] p \Rightarrow r [/tex]

    and if he is a knave, his reponse is false

    [tex] \neg p \Rightarrow \neg r [/tex]

    But Richard's response amounts to "If p, then q", or [itex] r = (p \Rightarrow q) [/itex]

    So we have:

    [tex] p \Rightarrow (p \Rightarrow q) [/tex]

    From this we can conclude that if Richard is a knight, he is telling the truth when he says that if he is a knight, he will eat his hat. Therefore, since is IS in fact a knight, he WILL eat his hat. What if Richard is a knave?

    [tex] \neg p \Rightarrow \neg (p \Rightarrow q) [/tex]

    We can show that

    [tex] \neg (p \Rightarrow q) = p \wedge \neg q [/tex]

    So it seems that if Richard is a knave, his statement is false. Which means that the negation of his statement is true. The negation of his statement is:

    Richard is a knight and Richard will not eat his hat

    This doesn't really make sense to me. It seems paradoxical since Richard is a knave in this case. Furthermore, the recursive nature of p --> (p --> q) is bothering me. Have I approached this problem in the right way?
     
  2. jcsd
  3. Jan 27, 2008 #2

    jambaugh

    User Avatar
    Science Advisor
    Gold Member

    Your analysis seems unfinished. You should show first that [itex] p = r \Rightarrow q[/itex] and then that [itex] p[/itex] equal some tautological statement such as [itex] q \wedge \neg q[/itex].

    Try to translate your last bit of reasoning into symbolic form as well.
     
  4. Jan 27, 2008 #3

    cepheid

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    I don't think I really follow. Are you saying I should have had r --> q instead of p --> q?
     
  5. Jan 27, 2008 #4

    jambaugh

    User Avatar
    Science Advisor
    Gold Member

    Not instead. r and p are equivalent by the assumption that knight's always tell the truth and knaves always lie. The man is a knight if and only if he speaks the truth. This then reduces the number of predicates you have to deal with:

    p = He's a knight and equivalently his statement is true.

    p = p--> q by form.
    p = q or not p, by parsing implication.
    Thence:
    p or not p = q or not p or not p
    which reduces (by distribution of inclusive or and by tautology of the left hand side) to:
    T = q or not p

    Then negating p we get:
    T = q or (p and not q)

    hmmm... from here we get by distribution:

    T = (q or p) and (q or not q)
    T = (q or p) and T
    T = q or p
    ... and so on.
    I can get T=q in three or so steps more. [I had typed them but decided to save the fun for you] You ought to see if you can trim the whole sequence down. But start with the postulates of predicate logic in symbolic form listed on a reference card as you work and make sure each step in your inference is justified by one of the postulates or a one of the basic theorems.
     
    Last edited: Jan 27, 2008
  6. Jan 28, 2008 #5

    cepheid

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Well considering that in the middle of your derivation, you had:

    T = q or not p

    and at the end, you have:

    T = q or p

    the only way these can both be true for any truth value of p is if q = T.

    Right?
     
  7. Jan 28, 2008 #6

    jambaugh

    User Avatar
    Science Advisor
    Gold Member

    Right. I guess I didn't leave much for you to do. To be explicit you'd combine the two with:

    T and T = (q or not p) and (q or p) >> = q or (p and not p) >> = q or T >> = q.
    where >> is progression of applied logic rules.
    They call it boolean algebra for a reason :wink:
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook