1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Propositional Logic

  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:
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Propositional Logic
  1. Propositional Logic (Replies: 9)

Loading...