Description
In each of the problems below it is especially important that your proof (or counter example) is correct,
clear, complete, concise, and carefully presented, using proper mathematical notation. Justifications have
to be given in the format of valid arguments. Points will be deducted if your presentation does not satisfy
these requirements.
1. A very special island is inhabited only by knights and knaves. Knights always tell the truth, and knaves
always lie.
You meet six inhabitants: Fiona, Diane, Cecil, Bob, Earl and Alice. Fiona says that either Bob is a
knight or Earl is a knight. Diane says, “Both Earl is a knave and Bob is a knight.” Cecil says that
Diane and Earl are not the same. Bob claims that either Earl is a knave or Alice is a knight. Earl
claims, “Alice and I are not the same.” Alice claims that Earl is a knave and Fiona is a knight.
Can you determine who is a knight and who is a knave?
2. Justify the rule of universal transitivity, which states that if ∀x (P(x) → Q(x)) and ∀x (Q(x) → R(x)) are
true, then ∀x (P(x) → R(x)) is true, where the domains of all quantifiers are the same.
Some of the following questions concern material presented only in Week 5, wait for proper introduction
before finalizing your assignments.
3. (a) Using equivalence transformations, prove that ((p ∨ q) ∧ (p → s) ∧ (q → t)) −→ (s ∨ t) ≡ T
Note: indicate the name of the equivalence used for each step, limit transformations to a single
transformation type per line
(b) Prove that (((p ∨ q) ∧ (p → s) ∧ (q → t)) → s ∨ t) is a tautology, using a direct proof (with
cases).
(c) Prove that (((p ∨ q) ∧ (p → s) ∧ (q → t)) → s ∨ t) is a tautology by proving the contrapositive.
4. (a) Prove that for natural numbers n, if n
3+3n+1 is even then n is odd, by proving the contrapositive.
(b) Prove that if x
3 + 3x + 3 is irrational then x is irrational, by proving the contrapositive.
5. Give a proof by contradiction to show that if the odd integers 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, are placed
randomly around a circle (without repetition), then there must exist three adjacent numbers along the
circle whose sum is greater than 32.
6. Give a proof by cases that shows that n(n
2 − 1)(n + 2) is a multiple of 4, for all integers n.
(Hint: Only two appropriately chosen cases need to be considered.)
