SE 500 (Math for SE)   Fall 2025
HW #4: Implication and Knights & Knaves
Due: 4:00pm, Friday, September 26

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. Among the theorems that are most useful in developing proofs involving disjunction, conjunction and implication are (3.32), (3.35), (3.48), (3.57), (3.59), and (3.60). 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.

1. Do Exercise 3.42, which is to prove

(3.60) p ⇒ q  ≡  p ∧ q  ≡  p

2. Do Exercise 3.45, which is to prove

p ⇒ q  ≡  ¬p ∨ ¬q  ≡  ¬p

Limit yourself to making use of theorems numbered no higher than (3.70).

3. Do Exercise 3.48, which is to prove

(3.64) p ⇒ (q ⇒ r)  ≡  (p ⇒ q) ⇒ (p ⇒ r)

4. Do Exercise 3.50, which is to prove

p ∧ (p ⇒ q)  ≡  p ∧ q

The next two 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 the left-hand side into the right-hand side, where the operator connecting each line/formula to the next is either = or ⟹. (At this point, the only theorems available to you by which you can connect one line/formula to the next by ⟹ are (3.76a)—(3.76c).)

5. Do Exercise 3.63, which is to prove Weakening/strengthening

(3.76d) p ∨ (q ∧ r)  ⟹  p ∨ q

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

7. Do Exercise 3.66, which is to prove

(3.78) (p ⇒ r) ∧ (q ⇒ r)  ≡  (p ∨ q ⇒ r)

The remaining 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. Thus, if Ann were to utter the proposition X, then we would formalize that using the equation a ≡ X.

For each scenario 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 scenario may be such that the most you can say is that Ann is a knight (while saying nothing about Bill), or that at least one of them is a knight. (A given scenario can, theoretically, correspond to any of the sixteen two-argument boolean functions.)

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

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

10. 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!".