Subsection 2.8.1 How Many Boolean Operators Could There Be?
So far, we’ve introduced the following binary Boolean operators:
∧ (and)
∨ (or), by which we mean inclusive or
≡ (is equivalent to), also called if and only if or iff
→ (implies)
It’s clear why we’ve picked these. They correspond to natural notions about which we want to reason. But are they the only possible binary Boolean operators?
The answer is no. In fact, we’ve already mentioned, just in passing, another version of or. Are there still more useful operators? The answer is yes.
Let’s consider the truth tables that we’ve used to define our binary operators so far. They all look like this:
| p | q | p operator q |
|---|---|---|
| P | T | v1 |
| T | F | v2 |
| F | T | v3 |
| F | F | v4 |
Each of the values, v1 through v4, is either T or F.
Now let’s look at a single truth table that shows us the four final columns in the four tables that define our binary operators so far:
| p | q | p ∨ q | p → q | p ≡ q | p ∧ q |
|---|---|---|---|---|---|
| T | T | T | T | T | T |
| T | F | T | F | F | F |
| F | T | T | T | F | F |
| F | F | F | T | T | F |
If we think of each of those result columns as a list of values, we’ve got:
T, T, T, F,
T, F, T, T,
T, F, F, T,
T, F, F, F
Are those the only possible lists of four values of T and F? Clearly not. For example, we could have:
T, F, T, F,
F, T, T, T,
F, T, T, F,
and others
How many different four-item lists are there? Well, the first item can have one of two values (T or F). For each of them, there are two values for the second item. So there are four different two-element lists. For each of them, there are two values for the third item, so there are eight different three-element lists. Finally, the fourth item can have one of two values, so there are 16 different four-element lists.
Each of those lists could be a final column in a truth table that defines an operator. So, in principle, there could be 16 different binary Boolean operators. But not all of them are useful enough to bother defining.