MATH 1090.03D

Fall 2000

Date: Oct. 2, 2000

Due: Oct. 16, 2000—▶In class—NO papers will be accepted after 11:45am◀

Do not forget the Term Test on October 11th, in class (CLH G), 11:30am-12:50pm.

Problem Set No. 2—On Chapter 3 of “GS”.

NOTE. When the book asks you to “prove valid”—or “prove the validity” of—a

formula, it wants you to prove that said formula is a tautology.

BE-operator precedences continue to be as given in class. In particular, all associativities are right.

Axiom (schemata) and rules of inference are exactly those given in class†. In particular, we have no “Substitution Rule of Inference” (those who attend classes will know that the preceding comment does not contradict the fact that we express “Leibniz” via the substitution operation).

Please write and annotate your proofs in the equational style of the text.

• Do the following problems from the text, Chapter 3.

3.2, 3.9, 3.14, 3.18, 3.20, 3.22, 3.25, 3.28, 3.29, 3.34, 3.39

Hint. Ignore the hints!

• Something I promised in Chapter 0 (that I will assign): Prove by induction on A, that every formula A starts with one of

(1) Variable

(2) Constant

(3) A left bracket.

Supplementary question. In your induction, did you actually use the Induction Hypothesis?

† You will recall that we have made a number of small changes to the text’s exposition in Chapter 3.