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 formalComputer 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. 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.