SE 500 (Math for SE)   Fall 2026
HW #5: Implication and Knights & Knaves
Due: 6:30pm, Tuesday, October 6

The exercises and theorems referred to by number come from Chapter 3 of the Gries & Schneider text. In proving a numbered theorem, you may make use of only lower-numbered theorems (or metatheorems). Note that some of the exercises may have hints that appear in the book, but not here. Make sure to respect the relative precedences of operators, which are listed on the textbook's inside front cover (in the hardback version at least) and here.

The first set of problems concern Ann and Bill, who are natives of the Island of Knights and Knaves. Every native of the island is either a knight or a knave. Every proposition uttered by a knight is true, and every proposition uttered by a knave is false. Use a and b, respectively, to stand for the propositions Ann is a knight and Bill is a knight. If Ann were to utter the proposition modeled by the boolean expression X, then we would formalize that using the equation a ≡ X (because the truth of "Ann is a knight" corresponds to the truth of the proposition modeled by X).

For each premise described, make the strongest statement you can regarding the status (knight or knave) of each of Ann and Bill. Such a statement need not be so strong as to identify the status of each of Ann and Bill. For example, a premise may be such that the most that can be concluded from it is that Ann is a knight (while saying nothing about Bill), or that at least one of them is a knight, or that Ann's being a knight implies that Bill is a knave. (A given premise can, theoretically, be equivalent to any of the sixteen two-argument boolean functions. Of course, one might exclude premises that are equivalent to the "false in all states" function, as they are, in a sense, impossible.)

1. Ann said, "If exactly one among Bill and me is a knight, then it is I who is the knight."

2. Ann said, "If exactly one among Bill and me is a knight, then it is Bill who is the knight."

3. A visitor to the island, upon encountering Ann and Bill, asked, "Which of you is a knave?". Bill replied, but so softly that Ann could not hear Bill's answer. Ann then blurted out, "If Bill said that I am a knave, then he is a knave!".

The next three problems are to prove theorems that are implications. Rather than showing each one to be equivalent to an already-known theorem, it is suggested that you transform its antecedant to its consequent (or vice versa), where the operator connecting each line/formula to the next is either =, ⟹, or ⟸, as appropriate. (The theorems that make such steps possible begin, in a sense, at (3.76).) Gries suggests starting with the side having "more structure", making it more likely that a proof can be found without "pulling a rabbit out of the hat".

4. Prove Weakening/strengthening (3.76d): p ∨ (q ∧ r)  ⟹  p ∨ q

5. Prove Weakening/strengthening (3.76e): p ∧ q  ⟹  p ∧ (q ∨ r)

6. Prove Modus tollens: (p ⟹ q) ∧ ¬q  ⟹  ¬p

7. Prove (4.1): p ⇒ (q ⇒ p)