Propositional Logic problem

In summary, Richard is either a knight or a knave. If he is a knight, he will eat his hat. If he is a knave, his statement is false.
  • #1
cepheid
Staff Emeritus
Science Advisor
Gold Member
5,199
38

Homework Statement



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)

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?
 
Physics news on Phys.org
  • #2
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.
 
  • #3
I don't think I really follow. Are you saying I should have had r --> q instead of p --> q?
 
  • #4
cepheid said:
I don't think I really follow. Are you saying I should have had r --> q instead of p --> q?

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:
  • #5
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?
 
  • #6
cepheid said:
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?
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:
 

1. What is propositional logic?

Propositional logic is a type of symbolic logic that deals with propositions or statements that can be either true or false. It is used to analyze and draw conclusions from logical arguments and is an important tool in mathematics, philosophy, and computer science.

2. What is a propositional logic problem?

A propositional logic problem is a question or puzzle that involves applying the principles of propositional logic to determine the truth or falsity of a given set of statements or propositions. These problems typically require the use of logical operators such as "and," "or," and "not" to evaluate the validity of an argument.

3. How is propositional logic different from other types of logic?

Propositional logic is a type of formal logic that deals with propositions and their truth values, whereas other types of logic, such as predicate logic, involve the use of variables and quantifiers to make statements about objects and their properties. Propositional logic is also simpler and more limited in scope compared to other types of logic, making it easier to apply to specific problems.

4. What are some common applications of propositional logic?

Propositional logic has many real-world applications, including in computer programming, where it is used to create logical conditions and control flow in software. It is also used in artificial intelligence, decision-making, and automated reasoning systems. In addition, propositional logic is used in philosophy to analyze and evaluate arguments and in mathematics to prove the validity of mathematical statements and theorems.

5. What are some strategies for solving propositional logic problems?

When faced with a propositional logic problem, it is important to carefully read and understand the given statements and determine which logical operators are being used. It can also be helpful to create a truth table or use a logical equivalency to simplify the problem. Another strategy is to apply the rules of inference, such as modus ponens or modus tollens, to make valid deductions. Practice and familiarity with logical operators and principles can also aid in solving propositional logic problems.

Similar threads

  • Precalculus Mathematics Homework Help
Replies
7
Views
2K
  • Calculus and Beyond Homework Help
Replies
2
Views
1K
  • Calculus and Beyond Homework Help
Replies
2
Views
2K
  • Calculus and Beyond Homework Help
Replies
2
Views
970
  • Set Theory, Logic, Probability, Statistics
Replies
11
Views
1K
  • Calculus and Beyond Homework Help
Replies
2
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
27
Views
3K
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
887
  • Calculus and Beyond Homework Help
Replies
6
Views
2K
Back
Top