3

I'm struggling to learn lambda Calculus.

I think what might really help is to see the simplest functions that you can create in lambda calculus and how they might be combined to make more complex functions.

For instance I know about the Identity function.

λ x . x  

and the not operator, but it feels like I don't understand how to use the building blocks of lambda calculus to make more complex functions yet.

So I'm asking, if you could, to show me some of the simplest lambda functions and how they combine to create more complex functions.

paradoxlabs
  • 41

1 Answers1

4

The easiest place to start is probably with the representations of truth values and logical operators in the lambda calculus.

By convention, the truth values TRUE and FALSE are represented as follows:

$\text{TRUE } \equiv \lambda x.\lambda y.x$

$\text{FALSE } \equiv \lambda x.\lambda y.y$

In other words, $\text{TRUE}$ and $\text{FALSE}$ are actually functions that each take two arguments. $\text{TRUE}$ always returns its first argument and $\text{FALSE}$ always returns its second argument.

If we think about the logical operator $\text{NOT}$, then $\text{NOT}$ takes a single argument and returns $\text{TRUE}$ if its input is $\text{FALSE}$ and vice versa. So we can represent $\text{NOT}$ as follows:

$\text{NOT } \equiv \lambda x.x \text{ FALSE} \space \text{TRUE}$

If $x$ is $\text{TRUE}$ then $\text{NOT}$ will return the first item from $\text{ FALSE} \space \text{TRUE}$ which is $\text{FALSE}$ - and vice versa if $x$ is $\text{FALSE}$.

If we think about the logical operator $\text{OR}$ then we want a function that takes two arguments. It returns its first argument if its first argument is $\text{TRUE}$ and it returns its second argument if its first argument is $\text{FALSE}$. We can represent this as follows:

$\text{OR } \equiv \lambda x.\lambda y.x \space x \space y$

Using similar reasoning we can represent other logical operators as follows:

$\text{AND } \equiv \lambda x.\lambda y.x \space y \space x$

$\text{XOR } \equiv \lambda x.\lambda y.x \space (\text{NOT } \space y) \space y$

$\text{IFTHEN } \equiv \lambda x.\lambda y.x \space y \space (\text{NOT } \space x)$

$\text{IFF } \equiv \lambda x.\lambda y.x \space y \space (\text{NOT } \space y)$

The Wikipedia article https://en.wikipedia.org/wiki/Lambda_calculus is a good place to start if you want to take things further.

gandalf61
  • 15,326