Instructions: Please solve the questions using pen and paper and scan the images. Every image should contain your roll number and name.
1. Fully parenthesize the following λ-expressions: [1.5 * 3 = 4.5]
(a) λx. x z λy. x y
(b) (λx. x z) λy. w λw. w y z x
(c) λx. x y λx. y x
2. Mark the free variables in the following λ-expressions: [1.5 * 3 = 4.5]
(a) λx. x z λy. x y
(b) (λx. x z) λy. w λw. w y z x
(c) λx. x y λx. y x
3. Prove the following using encoding in λ-calculus: [2 * 8 = 16]
(a) NOT(NOT TRUE) = TRUE
Given:
NOT = λx. ((x FALSE) TRUE)
TRUE = λx. λy. x
FALSE = λx. λy. y
(b) OR FALSE TRUE = TRUE
Given:
OR = λx. λy. ((x TRUE) y)
TRUE = λx. λy. x
FALSE = λx. λy. y
(c) SUCC 2 = 3
Given:
2 = λf. λy. f (f y)
3 = λf. λy. f (f (f y))
SUCC = λz. λf. λy. f (z f y)
(d) (Y FACT) 2 = 2
Given:
Y = λf. (λx. f (x x)) (λx. f (x x))
FACT = λf. λn. IF n = 0 THEN 1 ELSE n ∗ (f (n − 1))
(e) Given: mul = λn.λm.λx. (n (m x))
Solve: mul 3 3
(f) Solve: add 8 1
Given: add = λn.λm.λf.λx. n f (m f x)
(g) IF FALSE THEN x ELSE y = y
Given:
IF a THEN b ELSE c = a b c
TRUE = λx. λy. x
FALSE = λx. λy. y
(h) Prove: add and mul are commutative Given:
mul = λn.λm.λx. (n (m x))
add = λn.λm.λf.λx. n f (m f x)
1
