Boolean Operations

Building NOT

NOT should flip a boolean:

• NOT TRUE = FALSE
• NOT FALSE = TRUE

Since a Church boolean is a selector that chooses between two arguments, we can flip it by handing it two arguments in reverse order. Give the boolean FALSE first, then TRUE:

• TRUE selects the first argument $\to$ FALSE. Flipped.
• FALSE selects the second argument $\to$ TRUE. Flipped.

The boolean does the work. We just swap what it has to choose from.

NOT Definition

The formal definition of NOT is:

NOT = λb.b FALSE TRUE

It takes a boolean b and applies it to FALSE and TRUE (in that order). Since b is a selector:

• If b is TRUE: TRUE picks the first argument $\to$ FALSE
• If b is FALSE: FALSE picks the second argument $\to$ TRUE

No inspection, no comparison, no branching. The boolean selects from reversed choices. That is the entire mechanism.

NOT TRUE

NOT = λb.b FALSE TRUE

To compute NOT TRUE, apply the definition:

NOT TRUE = (λb.b FALSE TRUE) TRUE →β TRUE FALSE TRUE

Now TRUE selects the first of its two arguments:

TRUE FALSE TRUE → FALSE

NOT TRUE = FALSE. The boolean selected its own opposite.

Building AND

AND should return TRUE only when both inputs are TRUE:

Look at the pattern: when p is TRUE, the result is whatever q is. When p is FALSE, the result is FALSE regardless of q.

Since p is a selector, we can use it directly: let p choose between q (if true) and FALSE (if false). The result is p q FALSE.

AND Definition

The formal definition of AND is:

AND = λp.λq.p q FALSE

It takes two booleans and applies the first as a selector:

• If p is TRUE: TRUE picks the first argument $\to$ q
• If p is FALSE: FALSE picks the second argument $\to$ FALSE

When p is true, the result depends entirely on q. When p is false, the result is false regardless. This is AND: both must be true for the result to be true.

AND TRUE FALSE

AND = λp.λq.p q FALSE

To compute AND TRUE FALSE:

AND TRUE FALSE = (λp.λq.p q FALSE) TRUE FALSE →β (λq.TRUE q FALSE) FALSE →β TRUE FALSE FALSE

Now TRUE selects the first of its two arguments:

TRUE FALSE FALSE → FALSE

AND TRUE FALSE = FALSE. Correct: both must be true, but q is false.

Building OR

OR should return TRUE when at least one input is TRUE:

Look at the pattern: when p is TRUE, the result is TRUE regardless of q. When p is FALSE, the result is whatever q is.

This is the mirror image of AND. Let p choose between TRUE (if true) and q (if false). The result is p TRUE q.

OR Definition

The formal definition of OR is:

OR = λp.λq.p TRUE q

It takes two booleans and applies the first as a selector:

• If p is TRUE: TRUE picks the first argument $\to$ TRUE
• If p is FALSE: FALSE picks the second argument $\to$ q

When p is true, one true input is enough -- result is TRUE immediately. When p is false, the result depends on q. This is OR: at least one must be true.

OR FALSE TRUE

OR = λp.λq.p TRUE q

To compute OR FALSE TRUE:

OR FALSE TRUE = (λp.λq.p TRUE q) FALSE TRUE →β (λq.FALSE TRUE q) TRUE →β FALSE TRUE TRUE

Now FALSE selects the second of its two arguments:

FALSE TRUE TRUE → TRUE

OR FALSE TRUE = TRUE. Correct: at least one input (the second) is true.

All From Selectors

Review the three boolean operations:

• NOT = λb.b FALSE TRUE -- offer reversed choices
• AND = λp.λq.p q FALSE -- if p true, check q; if false, short-circuit
• OR = λp.λq.p TRUE q -- if p true, short-circuit; if false, check q

The pattern is the same every time: apply the boolean to the right pair of choices. No operation inspects, tests, or deconstructs a boolean. Each one simply hands the boolean two options and lets it select.

Church booleans are not passive data that operations examine. They are active selectors that perform the operation themselves.