Homework 4

1. Prove by induction that multiplication is distributive over addition, that is, k×(m+n)=k×m+k×n for all natural numbers k,m,n. You may use the fact (proved in the book and in class) that addition is associative and commutative.
2. Given the following inductive definitions of the predecessor and modified minus functions, prove by induction that (m+n)--n=m for all natural numbers m,n, and give an example which shows that it is not always true that (m--n)+n=m. You will almost certainly want to approach this proof by first establishing some useful lemmas about the behavior of P and --.

    { P(0) = 0              { m--0 = m
    { P(n+) = n             { m--n+ = P(m--n)

3. Given a set S (the alphabet), let S-STR be the smallest set which contains the empty string e and which is closed under the operation of concatenating a character onto the head of a string (that is, if a is in S and s is in S-STR, then a·s is in S-STR). Given the following inductive definition of the append operation, prove that s++(t++u)=(s++t)++u for all strings s,t,u in S-STR.

    { e++t=t
    { (a·s)++t=a·(s++t)

4. Given an alphabet S, let S-TREE be the smallest set which contains the leaf l(a) for each a in S and the node n(p,q) for each pair of trees p,q in S-TREE. Provide inductive definitions for two functions from S-TREE to the set of natural numbers which count, respectively, the number of leaves and the number of nodes in a tree. Prove by induction that every tree has exactly one more leaf than it has nodes.