[Solved] CS40032 Assignment 1 -Calculus

: Please solve the questions using pen and paper and scan the images. Every image should contain your roll number and name.

1. 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
2. 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
3. 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