: Please solve the questions using pen and paper and scan the images. Every image should contain your roll number and name.
- Fully parenthesize the following λ-expressions: [1.5 * 3 = 4.5]
- λx. x z λy. x y
- (λx. x z) λy. w λw. w y z x
- λx. x y λx. y x
- Mark the free variables in the following λ-expressions: [1.5 * 3 = 4.5]
- λx. x z λy. x y
- (λx. x z) λy. w λw. w y z x
- λx. x y λx. y x
- Prove the following using encoding in λ-calculus: [2 * 8 = 16]
- NOT(NOT TRUE) = TRUE
Given:
NOT = λx. ((x FALSE) TRUE)
TRUE = λx. λy. x
FALSE = λx. λy. y
- OR FALSE TRUE = TRUE
Given:
OR = λx. λy. ((x TRUE) y)
TRUE = λx. λy. x
FALSE = λx. λy. y
- SUCC 2 = 3
Given:
- = λf. λy. f (f y)
- = λf. λy. f (f (f y))
SUCC = λz. λf. λy. f (z f y)
- (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))
- Given: mul = λn.λm.λx. (n (m x))
Solve: mul 3 3
- Solve: add 8 1
Given: add = λn.λm.λf.λx. n f (m f x)
- 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
- 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
