Math 2510 Spring 2010 -- Homework Problem Set #1

Due: Friday, January 22nd
  1. Consider the theorem "\( A, \neg B \vdash_L \neg (A \rightarrow B) \)".
    1. Write down the truth table for "\( (A \wedge \neg B ) \rightarrow \neg (A \rightarrow B) \)" to show it is a tautology.
    2. Suppose that in the middle of my "proof" of this proposition, I have a line which says "\( \neg B \rightarrow (A \rightarrow B) \)". How do I know there is a mistake in my proof?

  2. My brother claims to have shown "\( A \vdash_L A \rightarrow B \)" in proof system \( L \). Could he possibly have found a proof? Explain why or why not.

  3. Consider Theorem L14 (on page 20) which says "\( \vdash_L A \rightarrow ((A \rightarrow B) \rightarrow B) \)"
    1. Show this proposition is a tautology by writing down its truth table (an abbreviated truth table is ok).
    2. Prove this proposition in \( L \) using the deduction theorem and modus ponens (no lemmas allowed).
    3. Prove this proposition in \( L \) without the deduction theorem (you may use any lower numbered theorems). Annoying hint: Using previous lemmas, there is a 2 line proof.

  4. Prove at least 3 of the 7 theorems L19 throught L25 (pages 21 and 22) -- except don't do the one I did in class. You may use the deduction theorem and theorems with lower numbers (including ones you've skipped) in your proofs.