• Question 1(a) Indicate which of the following applications of the β-reduction rule are correct and which are incorrect.
1. λx.((λy.y+1) (x+1))
2. (λy.y+x) (x+x) → (x+x)+x
→ λx.(x+1)+1 → λx.x+(x+x)
3. (λy.λx.x+y) (x+x)
4. (λf.λx.f(fx)) (λy.y + 1) → λx.(λy.y + 1) ((λy.y + 1) x)
• Question 1(b) Reduce the following lambda expression to a normal form. Show all steps, and underline the expression that is reduced at each step.
(λx.((λy.y + 1) (x + 1)))((λz.z) 3)