Lambda Calculus (Logic)

Lambda calculus is regarded as the most simplest programming language in the world. It serves as a basis for logic that powers applications in Computer Science.

Lambda calculus is made from three templates.

First

a

Second

(λ a .__)

Third

(____)

We can substitute any templates into any of the blanks in any template

In lambda calculus, everything is a function and can be applied on one another

In lambda calculus. $(λ a . a)$ is a function that takes in a to output a

(\overset{function + argument}{\overset{⏞}{λ a .}} \overset{output}{\overset{⏞}{a}})

def func(a):
	return a

to pass in an argument lets say b. we apply function $(λ a . a)$ on $b$ . Thus, passing $b$ as an input into the function, replacing all values of $a$ with $b$ .

((λ a . a) b) = b

func(b) # b

to pass more than one argument, lets say. Lets assume we have defined $+$

def func(a, b, c):
	return a+b+c

we have to define lambda for $a$ , $b$ and $c$

(λ a . (λ b . (λ c . a + b + c) 3) 2) 1

Going from outer to inner brackets. Replace all $a$ with $1$ , $b$ with $2$ and $c$ with $3$ .

(λ a . (λ b . (λ c . a + b + c) 3) 2) 1 \to λ b . (λ c . 1 + b + c) 3) 2 \to (λ c . 1 + 2 + c) 3 \to 1 + 2 + 3

we can express it as a short hand

λ a . λ b . λ c . (a + b + c)

Boolean Logic

True and False are selectors. True selects the first element while False selects the second.

True:

T := (λ x . λ y . x)

False

F := (λ x . λ y . y)

For example

(T a b) = a

And

(F a b) = b

NOT

NOT T = F
NOT F = T

NOT = λ x . (x F T)

Such that

\begin{aligned} NOT T & = (λ x . (x F T)) T \\ = (T F T) \\ = F \end{aligned}

And

\begin{aligned} NOT F & = λ x . (x F T) F \\ = (F F T) \\ = T \end{aligned}

AND

T AND T = T
T AND F = F
F AND T = F
F AND F = F

AND = λ x . λ y . (x y F)

OR

T OR T = T
T OR F = T
F OR T = T
F OR F = F

OR = λ x . λ y . (x T y)

NAND

T NAND T = F
T NAND F = T
F NAND T = T
F NAND F = T

NAND = λ x . λ y . (NOT (AND x y))

NOR

T NOR T = F
T NOR F = F
F NOR T = F
F NOR F = T

NOR = λ x . λ y . (NOT (OR x y))

From these gates, you can theoretically compute and create any function that a computer can do.

Numbers

A number is defined as

\begin{aligned} 1 & = f x \\ 2 & = f f x \\ 3 & = f f f x \\ ⋮ & = ⋮ \\ n & = λ f . λ x . (f^{n} x) \end{aligned}

It takes in a function $f$ and a value $x$ .

Thus

(n f x) = \overset{n times}{\overset{⏞}{f f \dots}} x

Let a successor be defined as

SUCC (n) = n + 1

Thus

SUCC = λ n . λ f . λ x . (f (n f x))

Thus addition is defined as

+ = λ m . λ n . λ f . (m SUCC n)

And multiplication is defined as

\times = λ m . λ n . λ f . λ x . m (n f) x