Define the and operator in lambda calculus Prove that your

. Define the and operator in lambda calculus. Prove that your definition is correct, i.e., your lambda term for and implements the logical and operation

Solution

Lambda calculus is a model of computation.

We write a lambda expression for each function. Input and output are also lambda expressions.

Example:

x.x+1

In this example we use the lamda and plus operator.

        function of one argument, whose formal parameter is named \'x\'. The function body is: \"x+1\". Note that the function has no name (i.e., it is an anonymous function). To compute with this function, we need to apply it to an argument; for example:

(x.x+1)3

In this example, x.x+1 is the function, and 3 is the argument; the entire thing is itself a lambda expression.

Computation involves re-writing:

(x.x+1)3 3+1 4.

The syntax of (pure) lambda expressions is defined as follows: