Query on Booleans in Lambda Calculus

functional-programming, lambda-calculus

Solution

To understand how to represent Booleans in lambda calculus, it helps to think about an IF expression, "if a then b else c". This is an expression which chooses the first branch, b, if it is true, and the second, c, if it is false. Lambda expressions can do that very easily:

lambda(x).lambda(y).x

will give you the first of its arguments, and

lambda(x).lambda(y).y

gives you the second. So if a is one of those expressions, then

a b c

gives either `b` or `c`, which is just what we want the IF to do. So define

 true = lambda(x).lambda(y).x
false = lambda(x).lambda(y).y

and `a b c` will behave like `if a then b else c`.

Looking inside your expression at `(n a b)`, that means `if n then a else b`. Then `m (n a b) b` means

if m then (if n then a else b) else b

This expression evaluates to `a` if both `m` and `n` are `true`, and to `b` otherwise. Since `a` is the first argument of your function and `b` is the second, and `true` has been defined as a function that gives the first of its two arguments, then if `m` and `n` are both `true`, so is the whole expression. Otherwise it is `false`. And that's just the definition of `and`!

All this was invented by Alonzo Church, who invented the lambda calculus.

Problem

Original source