Please write your solutions as clearly and concisely as possible.

1. (10 pts) Consider the following lambda terms:

   ADD = \p q x y. p x (q x y)

   and

   MULT = \p q x. p (q x)

   Prove that they represent the addition and multiplication respectively, i.e. that for every natural number m and n,

   ADD [m][n] = [m+n]

   and

   MULT [m][n] = [m*n]

   Note: ADD and MULT are different from the definitions of addition and multiplication seen in class (defined by primitive recursion), but they give the same result when applied to Church numerals.

2. (15 pts) Prove that, if we add the axiom [1] = [0] to the theory of the lambda calculus, then the theory becomes inconsistent, in the sense that we can derive M = N for every lambda terms M and N.

3. (15 pts) Give a possible definition of the logical conjunction, i.e. define a lambda term AND such that

   AND [true] [true] = [true],
   AND [true] [false] = [false],
   AND [false] [true] = [false],
   AND [false] [false] = [false].
   

4. (15 pts)
   1. Assume that two lambda terms M and N are such that, for every lambda term P, we have P M = P N. Does it follows that M = N ? (Prove that it follows, or give a counterexample.)
   2. Assume that two lambda terms M and N are such that, for every lambda term P, we have M P = N P. Does it follows that M = N ? (Prove that it follows, or give a counterexample.)
   Note: the equality symbol here denotes lambda conversion, i.e. conversion under alpha and beta.

5. (20 pts) Define a lambda term EXP such that, for every natural number n,

   EXP [n] = [2ⁿ]

6. (25 pts) Define a lambda term LOG such that, for every natural number n,

   LOG [n] = [k] if 2^k = n

   We are not interested on the behaviour of LOG in the case in which there exist no k such that 2^k= n.