Skip to content

Lambda Calculus for people a step behind me (2): Boolean Logic

Disclaimer: I’m not a computer scientist or mathematician. This post is about what I’ve learnt so far about Lambda Calculus. Most of the resources I’ve come across seem to assume either prior knowledge of advanced maths notation or extensive practical experience of lambda functions in software engineering. I’ve tried to avoid this and explain things step by step, but have no doubt made assumptions and mistakes of my own. Corrections (or questions) are welcome. I’ll include a list of the resources I’ve used to piece this together in a later post.

Hmm? Lambda what?

For those who came in late… start here.

What is Truth?

So how do we do TRUE and FALSE in Lambda Calculus? The solution isn’t entirely obvious, but it works: we can think of TRUE and FALSE as choices. So TRUE is not just a value but also a function that takes in two arguments (values/functions) and then returns one and throws away the other. The FALSE function will return the opposite value to the one chosen by true.

TRUE

TRUE looks like this:

λx.λy. x

The function takes in two arguments – x and y – and returns the first one. Here it is with the words TRUE and FALSE:

(λx.λy. x ) TRUE FALSE -> TRUE
(Technically this resolves step by step as: (λx.λy. x ) TRUE FALSE -> (λy. TRUE) FALSE – > TRUE. Note that the TRUE in “(λy.TRUE) FALSE” is not operating on FALSE – there is no y in the Lambda expression so the y argument is simply discarded).

FALSE

FALSE looks like this:

λx.λy. y

And evaluates like this:

(λx.λy. y ) TRUE FALSE -> FALSE
(Resolving step by step gives (λx.λy.y) TRUE FALSE -> (λy.y) FALSE (x is simply discarded) -> FALSE)

The words TRUE and FALSE here are abstractions from the actual Lambda Calculus. Using actual Lambda terms we can see that what’s returned is in fact a function that could be used to perform another operation:

(λx.λy. x) (λx.λy. x ) (λx.λy. y) -> λx.λy. x

IF-THEN

By definition, TRUE and FALSE allow us to choose between alternatives. You could do something like this:

(λa.λb.λz. z a b) [OUTPUT IF TRUE] [OUTPUT IF FALSE] [INPUT TRUE OR FALSE]

So using TRUE we get:

(λa.λb.λz. z a b ) [OUTPUT IF TRUE] [OUTPUT IF FALSE] [TRUE] ->
λb.λz. z [OUTPUT IF TRUE] b) [OUTPUT IF FALSE] [TRUE] ->
λz. z [OUTPUT IF TRUE] [OUTPUT IF FALSE] ) [TRUE] ->
[TRUE] [OUTPUT IF TRUE] [OUTPUT IF FALSE] ) ->
[OUTPUT IF TRUE]
True selects the first of two alternatives.

I don’t understand how we’d actually compare two values in order to get TRUE as an input… yet.

Logical Operators in Lambda Calculus

TRUE and FALSE are all we need to make the magnificent seven operators of Boolean Logic.

NOT

NOT takes in one value – TRUE or FALSE – and returns the opposite:

λa . a FALSE TRUE

e.g.

(λa. a FALSE TRUE) (λx.λy. x) -> (λx.λy. x) FALSE TRUE -> FALSE
(takes in TRUE, applies TRUE to FALSE TRUE, returns FALSE)

(λa. a FALSE TRUE) (λx.λy. y) -> (λx.λy. y) FALSE TRUE -> TRUE
(takes in FALSE, applies FALSE to FALSE TRUE, returns TRUE)

AND

AND takes in two values and returns TRUE only if they are both TRUE:

λa.λb. a b FALSE
If a is TRUE, return the value of b (this will be TRUE if b is also TRUE). If a is FALSE, will immediately return FALSE.

e.g.

(λa.λb. a b FALSE) TRUE FALSE -> (TRUE) FALSE FALSE -> FALSE

(λa.λb. a b FALSE) (λx.λy. x) (λx.λy. y) -> (λx.λy. x) (λx.λy. y) FALSE-> (λx.λy. y) = FALSE
(takes in TRUE for a and FALSE for b, applies TRUE to FALSE FALSE, returns FALSE)

And:

(λa.λb. a b FALSE) TRUE TRUE-> (TRUE) TRUE FALSE -> TRUE

(λa.λb. a b FALSE) (λx.λy. x) (λx.λy. x) -> (λx.λy. x) (λx.λy. x) FALSE-> (λx.λy. x) = TRUE
(takes in TRUE for a and b, applies TRUE to TRUE FALSE, returns TRUE)

For the following operators I’ll just use the abstractions TRUE and FALSE as arguments.

NAND (NOT AND)

NAND takes two arguments and returns FALSE if both arguments are TRUE:

λa.λb. NOT (AND a b)
That is, (λa.λb. (a b FALSE) FALSE TRUE) a b – uses NOT to invert the output of AND.

OR

OR takes in two arguments and returns TRUE of either of them are true.

λa.λb. a TRUE b
If a is TRUE, returns TRUE. If a is FALSE, returns b.

e.g.

(λa.λb. a TRUE b) FALSE TRUE -> (FALSE) TRUE TRUE -> TRUE
(takes in FALSE for a and TRUE for b, applies FALSE to TRUE TRUE, returns TRUE)

NOR (NOT OR)

NOR takes in two arguments and returns TRUE only when both arguments are FALSE:

λa.λb. NOT (OR a b)
That is, (λa.λb. (a TRUE b) FALSE TRUE) a b – uses NOT to invert the output of OR.

XOR (eXclusive OR)

XOR takes two arguments and returns TRUE when one and only one argument is TRUE (when one is TRUE and the other is FALSE).

λa.λb. a (NOT B) b
If a is TRUE, return the opposite of b. If a is FALSE, return b.

XNOR (eXclusive NOR)

XNOR takes two arguments and returns TRUE when both of the arguments are the same (either both TRUE or both FALSE).

λa.λb. a b (NOT B)
If a is TRUE, return b. If a is FALSE, return the opposite of b.

Tune in next time…

… for a function that lasts forever – and the Y combinator.

I'd love to hear your thoughts and recommended resources...