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. Also note that by Metatheorem (3.7), any two theorems are equivalent to each other. Perhaps the most useful application of this rule is to replace a subexpression that is a theorem by true.
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.13) Negation of false: ¬false ≡ true
2. On page 47, Gries proves theorem (3.11) (¬p ≡ q ≡ p ≡ ¬q) by showing it to be equivalent to an instance of theorem (3.5) (p ≡ p). Here you are asked to prove theorem (3.11) in three different ways. Specifically, for each of the equivalences below, transform its left-hand side into its right-hand side (or vice versa):
3. Prove (3.14): (p ≠ q) ≡ ¬p ≡ q
4. Prove (3.18) Mutual Associativity of ≡ and ≠: ((p ≠ q) ≡ r) ≡ (p ≠ (q ≡ r))
5. Prove (3.32) p ∨ q ≡ p ∨ ¬q ≡ p
Note that (3.27) is applicable.
6. Prove (3.39) Identity of ∧: p ∧ true ≡ p
7. Prove (3.42) Contradiction ∧: p ∧ ¬p ≡ false
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.)
(a) 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.)