For each of the following determine for each variable x the !x. it is bound to. I have numbered the variables and the abstractions. The variables are numbered using Arabic numerals and the abstractions are numbered using roman numerals. If variables 4 and 7 are bound to abstraction I, your answer should be of the form I 4, 7 to indicate that abstraction I has variables 4, and 7 bound by it.

Example ( !x. x x !x. x ) x

I 1 2 II 3 4

Answer

I -> 1, 2

II -> 3

a. x ( !x. x x ) x

1 I 2 3 4

b. x !x. x !x. . x !x. x

1 I 2 II 3 III 4

c . !x. x ( !x. x ) ( !y. x ) y

I 1 II 2 III 3 4

d. !x. ( !y. x ) !x. x x

I II 1 III 2 3

e. !x. ( !x. ( !x. x x ( !x. x ) x ) ( !x. x x ) ( !x. x ) ) x

I II III 1 2 IV 3 4 V 5 6 VI 7 8