# Given The Following Lambda Expressions And Corresponding Interpretations The Int

Given the following lambda expressions and corresponding interpretations:

1. The interpretation of λf.λx.x is natural number 0 (zero). The interpretation of λf λx.(f (f. (… x ))), with n applications of f on x, is the natural number n >0.
2. The interpretation of λn.λf.x(f ((n f) x )) is a successor function succ for natural numbers, where n is the formal parameter corresponding to the number whose successor is computed.
3. The interpretation of λm.λn.((m succ) n) is the addition function add for two natural numbers, where m and n are the formal parameters corresponding to the numbers whose sum is computed.
4. The interpretation of λm.λn.((m add) n)) zero) is the multiplication function mul for two natural numbers, where m and n are the formal parameters corresponding to the numbers whose product is computed.
5. The interpretation of λx.λy.x is propositional constant true.
6. The interpretation of λx.λy.y is propositional constant false.

Identify the mathematical/logical interpretation for the following expressions. Justify your answer. (In

all these problems, apply the functions on some actual arguments and examine the results; does the

result correspond to some already known interpretation, e.g., true, false, zero, some natural numbers;

does their exist some mapping between interpretation of the result and the corresponding input.)

(a) λx.((x false) true), where x is the formal parameter corresponding to propositional constants.

(b) λn.((n λp.((p false) true)) true), where n is the formal parameter corresponding to natural numbers.

(c) λn.((n λx.λy.λz.z) true), where n is the formal parameter corresponding to natural numbers.

(d) λm.λn.((m (mul n)) (succ zero)), where m and n are formal parameters corresponding to natural numbers.

0 replies