Homework 1
Due on Sept 21 Wednesday

Prove that ,

(1)

Proof:

## 2. Structural Induction

A set is defined as follows:
(1)
(2) if , then .
(3) if , then .
Prove that if and , then is divisible by 4.

Proof:

## 3. $\lambda$-Calculus

Reduce the following -terms to their normal form:
(1) .
(2) .
(3)

## 4. Operator Precedence and Associativity

What does 3 @@ 5 @@ 7 + 1 evaluate to under the following three definitions? Explain.
(1)

multThenInc :: Int -> Int -> Int
multThenInc x y = x * y + 1

infixl 3 @@
(@@) = multThenInc

(2)

multThenInc :: Int -> Int -> Int
multThenInc x y = x * y + 1

infixr 3 @@
(@@) = multThenInc

(3)

multThenInc :: Int -> Int -> Int
multThenInc x y = x * y + 1

infixl 7 @@
(@@) = multThenInc

(4)

multThenInc :: Int -> Int -> Int
multThenInc x y = x * y + 1

infixr 7 @@
(@@) = multThenInc

(5)

multThenInc :: Int -> Int -> Int
multThenInc x y = x * y + 1

infix 5 @@
(@@) = multThenInc