Exercise 7.1. -Expression for Boolean Truth Values and Connectives. Consider:

if b then c else a end.

Think of c and a in if b then c else a end as a pair, or more generally, as a list and b as a selector into that list. If b is true then c is selected. If b is false then a is selected. This determines our representation of true and false in the -calculus.

T, true : x.y.x

F, false : x.y.y

-calculus representation of the Boolean connectives are now suggested:

~ : x((xF)T)

: x.y.((xy)F)

: x.y.((xT)y)

1. Writing out T and F in full (i.e., as -expressions), show apply ~ to F to get T, and apply ~ to T to get F.

2. Writing out T and F in full apply to all four combinations of T and F and get what you expect.

3. Similarly for .