Introduction to Boolean Logic

A boolean value means a value can only take on one of two possibilities, commonly written as $⊥, ⊤$ or $0, 1$ or false,true.

A proposition is any expression which can be reduced to a boolean value. For example, the question of whether $3 = 3$ or $3 ≤ 4$ can be reduced to the boolean value true. When it’s clearer to do so, we might also prefer to write a proposition in plain English, such as by asking whether $3$ is a natural number.

Boolean logic is the study of labeling propositions, circuits, and other objects as either true or false, and then asking questions about all the things you’ve just labeled. In this cold way of thinking, true and false are merely names. To the mathematician, true might refer to whether a proposition is consistent with the rules they care about; to an engineer, true might refer to the state of a circuit or a bit of information. To these professions, logic is merely an accounting machine for manipulating information.

If we think about all the possible boolean functions which consume only one input, there will be $2^2 = 4$ possible functions. Additionally, for $2$-input boolean functions, there are $n = 4$ unique boolean pairs and thus $2^n = 16$ possible functions.

More generally, for boolean functions accepting $n$ inputs, there are $2^{2^n}$ possible boolean functions.

Of these, NOT, OR, AND, and XOR are the most well known and they’re widely implemented in programming languages

Note that NOT is a 1-input boolean function, but is listed here due to its popularity.

Logical NOT ($¬A$)

Logical NOT consumes only one input $A$ and it’s written as $¬A$.

NOT is useful for transforming a proposition to an opposing, contradictory one. For example, if $P(n)$ is the proposition that $n$ is natural, then $¬P(n)$ asks if $n$ isn’t natural.

Logical OR, AND, and XOR

• OR $(∨)$ asks if there exists a true input.
• AND $(∧)$ asks if all inputs are true, and is equivalent to multiplication.
• XOR $(⊕)$ asks if both its inputs are different, and is equivalent to addition.

Implication

Let $A$ and $B$ be propositions. There are times when knowing $A$ is true also means knowing $B$ is true. For example, knowing $x$ is a natural also means knowing $x$ is an integer, although the reverse isn’t always true.

Logical implication is a binary operator $𝗕 × 𝗕 → 𝗕$ represented by the relations table below.

One way of thinking about $A → B$ is as a discussion on what kinds of evidence we would accept for knowing that $B$ is true. If we have $A → B$ then we can use the truthiness of $A$ to prove $B$. Otherwise, we can just directly prove $B$ even if $A$ turns out to be false. Both are acceptable ways to prove $B$.

Implication $≠$ Causality

When we say $A$ implies $B$, this doesn’t mean that $A$ causes $B$. For example, let’s say that proposition $A$ asks if a light switch is turned on, and proposition $B$ asks if black holes exist

Since the proposition about black holes is always true, we then have enough to say that $A$ implies $B$, but that doesn’t mean we think $A$ causes $B$. Instead we say that whenever we observe $A$ we also observe $B$.

Universal Functions

NOR $(↓)$ and NAND $(↑)$ are notable because they’re the only functions that can individually rebuild all $16$ possible boolean functions.

• NOR can be written as $¬(A ∨ B)$.
• NAND can be written as $¬(A ∧ B)$.

De Morgan’s laws

The One Axiom

Let $a, b, c$ be booleans, and let $↑$ be the NAND function. All of boolean algebra can be summarized with a single axiom:

In 2002, Stephen Wolfram, and separately William McCune and colleagues, independently curated and published this axiom from among over a dozen competing aesthetic choices.

Boolean Field

XOR and AND individually form groups and together they form the smallest field with only two elements, written as $F_2$ or $GF(2)$. Finite fields are also known as Galois Fields, named after famed mathematician Évariste Galois.

Note the multiplicative group of a field excludes $0$ or else multiplication wouldn’t be invertible.

We can see that the functions are equivalent from the truth table below.

Logical Functions represented in $F_2$

Higher Order Boolean Logic

The collection of sixteen 2-arity functions closed over the booleans are altogether known as zeroeth order boolean logic.

First order boolean logic allows you to look over “many” boolean propositions and say whether none, some, or all of the propositions are true, and so people often say that first order logic “quantifies” over sets.

Second order boolean logic is somewhat controversial. While first order logic allows you to discuss some or all of the objects you care about, it cannot discuss all the relations your objects may have among each other.

So far with zero-order logic we’ve only been evaluating two boolean arguments at a time, but what if we wanted to evaluate many at a time? For example, let’s say I have a set below:

• Are all elements whole numbers? Yes.
• Are some elements bigger than $3$? Yes: $\{ 4, 5 \}$.
• Are no elements smaller than $0$? Yes.
• Is there a unique element smaller than $1$? Yes: $0$.

All $(∀)$ of the naturals

This statement reads “for all $x$ and $y$ from $ℕ$ we have $x + y = y + x$“.

Some $(∃)$ of the naturals

This reads as “there exists an $x$ and $y$ from $ℕ$ such that $x + y < 100$“.

None $(∄)$ of the naturals

The first statement can be read as “there exists no $x$ and $y$ from $ℕ$ such that $x + y = 0.5$”. The second statement can be read as “for all $x$ and $y$ from $ℕ$ we have $x + y ≠ 0.5$“.

Saying “never true” is equivalent to saying “always false”.

There is a unique $(∃!)$ natural

This statement can be read as “there exists a unique element $n$ from $ℕ$ such that $n + n = 0$“.