CMPU-145, Spring 2013
Asmt. 4
Due:  Fri., March 29 @ 5:00 p.m.


This assignment only involves proofs.  Thus, you need not submit
electronically.  You can turn in (neat) hand-written solutions; or you
can type them up (optional).

  PROBLEM 1.

    Recall the definition of the addition function, seen in class, where
    S stands for the "successor" function:

        (1) x +  0 = x            
        (2) x + Sy = S(x + y)

      Recall that we proved in class the following theorems:

        (GEORGE)  0 + x = x  for all natural numbers x.

        (CRACKIE) x + Sy = Sx + y for all natural numbers x and y.

    ==> Prove that the addition function defined by the above rules
        is COMMUTATIVE.  In other words, prove the following:  

            x + y = y + x    for all natural numbers x and y.

      Your proof should only use rules 1 and 2 above, as well as the
      results named GEORGE and CRACKIE.

      For full credit, you must clearly specify the proposition that
      you are using; and the structure of your inductive proof (i.e.,
      base case and recursive case) must be clear.  In addition, each
      step should be clearly justified.


  PROBLEM 2.

    Consider the following definition of a multiplication function
    on the natural numbers.

      (3)    x * 0  = 0
      (4)    x * Sy = (x*y) + x

    Use induction to prove that the DISTRIBUTIVE property holds for
    the multiplication and addition functions defined by rules 1-4.
    In other words, prove that:

        (x+y)*z = x*z + y*z   for all natural numbers x, y and z.

    HINTS:  Let P(z) be the proposition that (x+y)*z = x*z + y*z
              for all natural numbers x and y.

            Use induction to show that P(z) holds for all z.

            You may freely use the associative and commutative
            properties of ADDITION in your proof; however, be sure to
            indicate *where* you use these properties.  As in the
            first problem, you must clearly show the structure of your
            proof (base case, recursive case) and justify each step.