Booleans and Operators

The Origins of Truth and Falsehood

Imagine a world where every question has only two possible answers:
Yes or No,
On or Off,
True or False.
This is the essence of Boolean logic. It’s the digital foundation that powers everything from light switches to quantum computers.

But where did it all begin?

Back in the 19th century, an English mathematician named George Boole asked a simple but revolutionary question:
"Can logic be treated as an algebra?"

His answer? A resounding Yes! He developed a system where logic could be expressed using symbols, operations, and rules—just like arithmetic. Fast forward to today, and every computer, smartphone, and digital device runs on his ideas. Without Boolean logic, there would be no circuits, no programming, no internet!

True and False in Lambda Calculus

In programming and mathematics, we often need a way to represent truth and falsehood. Enter lambda calculus, a system that distills computation to its purest form — functions and transformations.

In lambda calculus, we define Boolean values as functions:

• True ($\mathbb{T}$) → λx.λy.x (Choose the first argument)
• False ($\mathbb{F}$) → λx.λy.y (Choose the second argument)

At first glance, this might strange... But it's all about interpretation. You can think of it this way:

Imagine you're ordering coffee. You tell the barista:
"If I want sugar, give me sugar; otherwise, give me salt."

Here, you're picking between two options. In lambda calculus, 𝕋 always picks the first option (sugar), while 𝔽 picks the second (salt). Truth and falsehood are just choices!

So, basically, you can define $\mathbb{T}$ and $\mathbb{F}$ as you wish, but the most common way is to use the above definitions.

Boolean Operators

Now that we have True and False, how do we combine them to form logical expressions? Simple: with Boolean operators.

1. NOT (Negation)

Just flips the value:

• ¬ (Negation)
  $\mathrm{\neg }(\mathbb{T})=\mathbb{F}$,
  $\mathrm{\neg }(\mathbb{F})=\mathbb{T}$

• In imperative languages:

 def not(x: Boolean): Boolean =
   if (x) false
   else true

So, basically, if x is True, return False; otherwise, return True.

• In lambda calculus:

 λx.x 𝔽 𝕋

Try it out!

2. AND (Conjunction)

Only True if both inputs are True:

• ∧ (Conjunction)
  $\mathbb{T}\wedge \mathbb{T}=\mathbb{T}$,
  $\mathbb{T}\wedge \mathbb{F}=\mathbb{F}$,
  $\mathbb{F}\wedge \mathbb{T}=\mathbb{F}$,
  $\mathbb{F}\wedge \mathbb{F}=\mathbb{F}$

• In imperative languages:

 def and(x: Boolean, y: Boolean): Boolean =
   if (x) y
   else false

• In lambda calculus:

 λx.λy.x y 𝔽

Try it out!

3. OR (Disjunction)

True if at least one input is True:

• ∨ (Disjunction)
  $\mathbb{T}\vee \mathbb{T}=\mathbb{T}$,
  $\mathbb{T}\vee \mathbb{F}=\mathbb{T}$,
  $\mathbb{F}\vee \mathbb{T}=\mathbb{T}$,
  $\mathbb{F}\vee \mathbb{F}=\mathbb{F}$

• In imperative languages:

 def or(x: Boolean, y: Boolean): Boolean =
   if (x) true
   else y

• In lambda calculus:

  λx.λy.x 𝕋 y

Try it out!

Logical Constructions

So, basically, we already have declared such logical constructions as NOT, AND, and OR, using imperative approaches and lambda calculus. So, we can use these constructions to build more complex logical expressions.

Thus, if-then-else constructions can be built like this:

• In imperative languages:

 def ifThenElse(cond: Boolean, thenBranch: Whatever, elseBranch: Whatever): Whatever =
   if (cond) thenBranch
   else elseBranch

• In lambda calculus:

Pair in Lambda Calculus

Now that we've built Boolean logic in lambda calculus, let's step into something equally powerful: Pairs.

Imagine you have two values that you want to bundle together and pass around as a single unit. In most programming languages, we have tuples, structs, or objects for this. But in lambda calculus, we don't have built-in data structures—we have to build everything from functions!

Defining a Pair

A pair is simply a function that, when given a selector, returns either the first or the second element.

PAIR ≡ λx.λy.λs. s x y

• x is the first element.
• y is the second element.
• s is the selector function that decides which one to return.

Think of a pair like a vending machine:

• You insert a coin (the selector function).
• The machine gives you either the first or second item, depending on your choice.

Selecting Values from a Pair

To retrieve values from a pair, we define two functions:

1. First (FST)

Returns the first element of the pair:

FST ≡ λp. p 𝕋

2. Second (SND)

Returns the second element of the pair:

SND ≡ λp. p 𝔽

Try It Out!

Let's create a pair (5, 10) and extract its values.

Step 1: Define the Pair

PAIR 5 10
→ λs. s 5 10

Step 2: Apply FST

FST (PAIR 5 10)
→ (λp. p 𝕋) (λs. s 5 10)
→ (λs. s 5 10) 𝕋
→ 𝕋 5 10
→ 5

✅ Success! We got the first element!

Step 3: Apply SND

SND (PAIR 5 10)
→ (λp. p 𝔽) (λs. s 5 10)
→ (λs. s 5 10) 𝔽
→ 𝔽 5 10
→ 10

✅ It works! We retrieved the second element!

Why Are Pairs Important?

Pairs unlock many possibilities in lambda calculus. Once we have pairs, we can:

1. Define numbers and arithmetic operations...
2. Store multiple values together (like a two-element array).
3. Build complex data structures (lists, trees, dictionaries).
4. Create coordinate systems (like (x, y) points in geometry).
5. Represent key-value pairs (important for maps and tables).

Just like Boolean logic was a stepping stone to decision-making, pairs are a stepping stone to structured data. And with structured data, we can construct entire programming languages!