1. The boolean operation implication is defined by the following truth table:

X	Y	X implies Y
False	False	True
False	True	True
True	False	False
True	True	True

a.) Define the implication relation in the Lambda Calculus:

def implies = x.y (7 pts)

b.) Show that your definition satisfies the truth table for all boolean values of x and y.

That is, using your definition of implies (and of true and false), show that:

((implies false) false) true (2pts each for 8 pts total)

((implies false) true) true

((implies true) false) false

((implies true) true) true

2. Implement a Lambda Calculus definition of multiplication in Racket, and answer the following questions.

1. Using only the functions provided in this starter file (do not change the existing functions), write both a new function called mult and a new helper function called mult2 in Racket. You may use any of the functions that are listed below. Uncomment the tests in the starter file and include the output of these tests that are listed below as well.

What happens if you change #lang lazy to #lang racket and run the tests? (1 pt) Why? (3 pts)

Functions you can use:

#lang lazy

(define my-false (lambda (x) (lambda(y) y)))

(define my-true (lambda (x) (lambda (y) x)))

(define succ (lambda (cn) (lambda (s) ((s my-false) cn))))

(define pred (lambda (cn) (cn my-false)))

(define iszero (lambda (cn) (cn my-true)))

(define zero (lambda (x) x))

(define one (lambda (sel) ((sel my-false) zero)))

(define two (succ one))

(define three (succ two))

(define (cn-to-num cn) (if (((iszero cn) #t) #f) 0 (+ 1 (cn-to-num (pred cn)))))

(define add2 (lambda (f) (lambda (x) (lambda (y) (((iszero y) x) (((f f) (succ x)) (pred y)))))))

(define add (add2 add2))

(displayln "The result of adding Church Numerals two and three is: ") (cn-to-num ((add two) three))

; UNCOMMENT TO TEST YOUR MULT FUNCTIONS: ;(displayln "The result of multiplying Church Numerals one and two is: ") ;(cn-to-num ((mult one) two)) ;(displayln "The result of multiplying Church Numerals two and zero is: ") ;(cn-to-num ((mult two) zero)) ;(displayln "The result of multiplying Church Numerals two and three is: ") ;(cn-to-num ((mult two) three))