SE 500 (Math for SE)   Fall 2024
HW #4: Proofs involving Equivalence, Negation, Inequivalence, Disjunction, and Conjunction
Due: 5pm, Wednesday, Sept. 25

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

1. Do Exercise 3.14, which is to prove mutual interchangeability of ≡ and ≠ (3.19):

(3.19) (p ≠ q ≡ r) ≡ (p ≡ q ≠ r)

using the heuristic of Definition Elimination (3.23). (Note that, due to the mutual associativity of ≡ and ≠, which is Theorem (3.18), the "absent" parentheses in the statement of (3.19) above are not needed. For that matter, the parentheses that are present are not necessary!)

2. Do Exercise 3.26, which is to prove Contradiction:

(3.42) p ∧ ¬p ≡ false

3. Do Exercise 3.27, which is to prove 1st Absorption (part a):

(3.43a) p ∧ (p ∨ q)  ≡  p

4. Do Exercise 3.29, which is to prove 2nd Absorption (part b):

(3.44b) p ∨ (¬p ∧ q)  ≡  p ∨ q
Hint: Use the Golden Rule (3.35).

5. Do Exercise 3.30, which is to 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).

6. Do Exercise 3.31, which is to prove Distributivity of ∧ over ∨:

(3.46) p ∧ (q ∨ r)  ≡  (p ∧ q) ∨ (p ∧ r)
Hint: Use (3.45) and absorption

7. Do Exercise 3.34, which is to prove

(p ∧ q) ∨ (p ∧ ¬q) ≡ p

8. Do Exercise 3.35, which is to prove

(3.48) p ∧ q  ≡  p ∧ ¬q  ≡  ¬p
Hint: Use (3.32).

9.(a) Suppose that you took Axioms (3.24) through (3.28) and replaced each occurrence of ∨ by ⊛. Call the resulting equations (3.24'), (3.25'), ..., (3.28'). (The idea is that ⊛ could stand for any of the sixteen functions with signature bool × bool ⟶ bool, as are described here and on page 26 of Gries & Schneider.)

Make a convincing argument that, among those sixteen functions, the only one that makes all of (3.24'), (3.25'), ..., (3.28') into tautologies is the one that we call disjunction. (In other words, show that if we let ⊛ stand for any of the fifteen functions other than disjunction, at least one among (3.24'), (3.25'), ..., (3.28') is not a tautology.)

(b) Now find a smallest subset of {(3.24'), (3.25'), ..., (3.28')} such that ⊛ must stand for disjunction in order for all members of that subset to be tautologies. (In effect, you are being asked to identify a smallest set of axioms, among (3.24), ..., (3.28), that suffice to uniquely identify disjunction among all sixteen two-argument boolean functions.)