Homework 3

1. For each of the following propositions, either present a natural deduction proof which establishes that it is a theorem or give a valuation which shows that it is not a theorem:
   1. (p -> q) -> (¬p -> ¬q).
   2. ¬(p ^ ¬p).
   3. (p -> q) -> ((p -> (q -> r)) -> (p -> r)).
   4. p ^ ¬(p ^ ¬q) <-> ¬(¬p ^ ¬(p ^ q)).
   5. (p ^ q -> r) -> ¬(¬(p -> (q -> r)) ^ s).
   6. (p -> q) v (q -> p) (try this two ways: first by treating the v as an abbreviation and using the natural deduction system of §1.4, and then by using the extended natural deduction system of §1.6. As an extra challenge, see if you can find proofs that don't use RAA.)
   7. (Extra credit) ((p <-> q) -> p ^ q ^ r) ^ ((q <-> r) -> p ^ q ^ r) ^ ((r <-> p) -> p ^ q ^ r) -> p ^ q ^ r.
2. Let me know what topic you would like to present in a one-class lecture in early November. Please see me if you need help choosing a topic.