SE 500 (Math for SE)   Fall 2025
HW #3: Proofs Involving Negation, Inequivalence, Disjunction, and Conjunction
Due: 5:00pm, Friday, Sept. 19

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 Gries & Schneider book, but are not repeated here. In particular, some of the problems call for the use of (3.23) Heuristic of Definition Elimination.

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. Prove (3.12) Double Negation: ¬¬p ≡ p

2. Prove (3.17) Associativity of : ((p ≠ q) ≠ r) ≡ (p ≠ (q ≠ r))

3. Prove (3.19) Mutual Interchangeability of and :   p ≠ q ≡ r   ≡   p ≡ q ≠ r

Note that (3.18) Mutual Associativity justifies writing (3.19) without using any parentheses.

4. Prove (3.30) Identity of : p ∨ false ≡ p

5. Prove (3.38) Idempotency of : p ∧ p ≡ p

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

7. Prove (3.47a) DeMorgan: ¬(p ∧ q) ≡ ¬p ∨ ¬q

Hint: Theorem (3.32) could come in handy.


8. Suppose that you took Axioms (3.24) through (3.28) and replaced each occurrence of ∨ by the symbol ⊙. 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 on page 26 of Gries & Schneider (and here.)

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, if all members of that subset are tautologies, then ⊙ necessarily stands for disjunction. (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.)