SE 500 (Math for SE)   Fall 2026
HW #4: Proofs involving Equivalence, Negation, Inequivalence, Disjunction, Conjunction, and Implication
Due: 3pm, Friday, Oct. 2

The exercises referred to come from the end of Chapter 3 in the Gries & Schneider text. The theorems from that book can be found here.

In proving a 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 are not repeated here.

Don't forget the precedences of operators, which can also be found on the textbook's inside front cover (in the hardback version at least).

In exercises involving conjunction, expect to apply the Golden Rule (3.35) quite frequently and (3.32) occasionally.

1. Prove Absorption (3.43b):  p ∨ (p ∧ q) ≡ p

2. Prove Absorption (3.44b):  p ∨ (¬p ∧ q) ≡ p ∨ q

3. Prove Distributivity of ∨ over ∧ (3.45):  p ∨ (q ∧ r)  ≡  (p ∨ q) ∧ (p ∨ r)

Hint: Use the heuristic of Definition Elimination (3.23) and the Golden Rule (3.35).

4. Prove Distributivity of ∧ over ∨ (3.46):  p ∧ (q ∨ r)  ≡  (p ∧ q) ∨ (p ∧ r)

Hint: Use (3.45) and absorption.

5. Using only theorems numbered less than (3.47), prove   (p ∧ q) ∨ (p ∧ ¬q) ≡ p

6. Prove (3.48):   p ∧ q  ≡  p ∧ ¬q  ≡  ¬p

Hint: Use (3.32).

7. Using only theorems numbered less than (3.63), prove   p ⇒ q  ≡  ¬p ∧ ¬q  ≡  ¬q

8. Prove (3.64):  p ⇒ (q ⇒ r)  ≡  (p ⇒ q) ⇒ (p ⇒ r)

9. Prove (3.67):  p ∧ (q ⇒ p)  ≡  p

10. Prove (3.70):  (p ∨ q ⇒ p ∧ q) ≡ p ≡ q

Note that the parentheses are not necessary (due to ≡ having a lower precedence than ⇒) but were included to avoid any mis-interpretation.