Print this problem set out (there are 7 problems!) and answer the problems on the given sheet.
  1. Give the justification for each step of the simplifcation below. 
                                      Justification for each simplification step
F = ~(~x & y)

  = ~~x | ~y      __________________________________________________________________

  = x | ~y        __________________________________________________________________

  = ~y | x        __________________________________________________________________

  = y => x        __________________________________________________________________
  2. Simplify a|(~a => b) to a|b. Show each step and give a justification for each step (should look like the previous problem!).
  3. Below is a proof. Give the justification for each step. 
    	  Given ~(t0 | t4) => ~e1, (t0 | t4) & ~t1 => e1, e1 and ~t0, prove t4


1: e1                  _______________________________________________________________________

2: ~t0                 _______________________________________________________________________

3: ~(t0 | t4) => ~e1   _______________________________________________________________________

4: e1 => (t0 | t4)     _______________________________________________________________________

5: t0 | t4             _______________________________________________________________________

6: ~t0 => t4           _______________________________________________________________________

7: t4                  _______________________________________________________________________

  4. Below is a proof with the "reasons" listed for all the steps, but the actual formulas produced from those reasons missing. Fill in that missing information! 
    Given a => (b | ~c), a & b, and c, prove b

1: a => (b | ~c)                                    [Given]

2: a & b                                            [Given]

3: c                                                [Given]

4: _____________________________                    [And-elimination on 2]

5: _____________________________                    [Modus Ponens on 1 and 4]

6: _____________________________                    [Commutivity of "or" on 5 ]

7: _____________________________                    [Apply (x => y) <=> (~x | y) on 6]

8: _____________________________                    [Modus Ponens on 7 and 3]
  5. Here are a few facts: Being a CS major means you are smart and good-looking. If you're smart, you're a CS major. Given these, and that you are in fact smart, prove that you are good-looking.
    Note: Translate the above into propositional logic (clearly define your variables!) and do a complete step-by-step proof with numbers and justifications and all, as in the previous problems.
  6. Assume the following statements are true: If you're not cheating, you're not trying. If you're winning, you're cheating.

  7. I hate to do this to you, but you need to read the section "If and only if" vs "If" (i.e. ⇔ vs ⇒) and definitions from the class 11 notes. So go ahead and read it, I'll wait.

    Done? Great! Suppose we have the following definition regarding tennis:

    Definition: a serve is called a let if and only if the ball hits the net and its first bounce is in the service box.

    Here are some additional facts: There is a sensor that beeps if and only if the ball hits the net. If the ball's first bounce is not in the service box, the umpire yells "out".

    Given that during the serve the umpire doesn't yell "out" and the sensor beeps, prove that the serve is a let.
    Note: Translate the above into propositional logic (clearly define your variables!) and do a complete step-by-step proof with numbers and justifications and all, as in the previous problems. [This is a bit harder to finish, but defining variables, writing the givens, and making some progress should not be too bad.]