Computer Science 260
Assignment 2
Please submit your assignment electronically via moodle. Submissions will be accepted
in either plain text (.txt) or PDF. Clearly define all non-standard symbols used. For
example, if you use & in place of ∧, you must clearly state this in your assignment.
1. Give a formal proof that ((p → q) → p) → ((p → q) → q). Use the rules of
equivalence from Thm 2.1.1 of the text, or the rules of inference in table 2.3.1 of the
text, or the deduction theorem. For each step of the proof, give the reason for the step
and the numbers of any previous steps referred to.
2. A strange island is inhabited only by knights and knaves. Knights always tell the
truth, and knaves always lie.
You meet two inhabitants: A and B. A claims, ’ Both I am a knight and B is a knave’
, and B says, ‘I tell you A is a knight’.
Determine who is a knight and who is a knave, if possible.
Give a record of your reasoning by converting the above statements of the inhabitants
into logical expressions and deriving any necessary new expressions with valid rules of
equivalence or inference. You may use the Deduction Theorem. Use line numbers so
previous statements can be referred to. If you use logical variables, indicate what they
mean.
