# Propositional Logic

1. Jan 27, 2008

### cepheid

Staff Emeritus
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:

$$p \Rightarrow r$$

and if he is a knave, his reponse is false

$$\neg p \Rightarrow \neg r$$

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

So we have:

$$p \Rightarrow (p \Rightarrow q)$$

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?

$$\neg p \Rightarrow \neg (p \Rightarrow q)$$

We can show that

$$\neg (p \Rightarrow q) = p \wedge \neg q$$

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. Jan 27, 2008

### jambaugh

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

Try to translate your last bit of reasoning into symbolic form as well.

3. Jan 27, 2008

### cepheid

Staff Emeritus
I don't think I really follow. Are you saying I should have had r --> q instead of p --> q?

4. Jan 27, 2008

### jambaugh

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
5. Jan 28, 2008

### cepheid

Staff Emeritus

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?

6. Jan 28, 2008

### jambaugh

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