Solutions to exercises from Chapter 2 of "Discrete Mathematics Using a Computer"

DiscreteMathComputer02.txt

Chapter 02 Equational Reasoning
of Discrete Mathematics Using a Computer

--------------------------------------------------------------------------------
Theorem 1 (length (++))
Let xs, ys :: [a] be arbitrary lists. 
Then length (xs ++ ys) = length xs + length ys
- Proof is by Induction, chapter 4

--------------------------------------------------------------------------------
Theorem 2 (length map)
Let xs :: [a] be an arbitray list and f :: a -> b be an arbitrary function. 
Then, length (map f xs) = length xs

- No proof given

--------------------------------------------------------------------------------
Theorem 3 (map ++)
Let xs, ys :: [a] be arbitrary lists
Let f :: a -> b be an arbitrary function

Then, map f (xs ++ ys) = (map f xs) ++ (map f ys)

--------------------------------------------------------------------------------
Theorem 4 
For arbitrary lists xs, ys :: [a]
and arbitrary function f :: a -> b,

the equation length (map f (xs ++ ys)) = length xs + ys holds.

Proof: 
length (map f (xs ++ ys)) = length (xs ++ ys) by Theorem (length map)
                          = length xs + length ys by Theorem (length (++))
Alternative Proof
length (map f (xs ++ ys)) = length ((map f xs) ++ (map f ys))  by Theorem (map ++)
                          = length (map f xs) + length (map f ys)  by Theorem (length ++)
                          = length xs + length ys by Theorem (length map)