While studying logic, I have encountered a variety of boolean operators: functions that take in a number of booleans, each either

or

and output a single boolean. For example, the “and” operator, which is often notated with the symbol

takes in two booleans and outputs

only when both inputs are

We can illustrate how this operator acts by writing a truth table, which has a row for each combination of inputs, named

and

and shows the output for those inputs.

The number of inputs an operator takes is called its arity, and it doesn’t have to be two. For example, the “not” operator has an arity of one, so it is called unary:

Also, the “falsum” operator has an arity of zero, so it is called nullary:

There are even operators with higher arity, such as the conditional operator with an arity of three, which is called ternary:

The focus of this blog post will be on operators with arity two, or binary operators. As well as the “and” operator we saw above, most systems of logic include the “or”, “implies”, and “equivalent” operators:

These are all very standard, though some authors prefer to use double arrows such as

and

instead of the single arrows I am using. There are also some binary operators with less standardised notation. First is the “exclusive or” operator, which I have seen notated as

and

For now, let’s use

:

Second, is the “nand” operator, which I have seen notated as

and

For now, let’s use

:

Lastly, is the “nor” operator, which I have seen notated as

and

For now, let’s use

:

And that’s all for operators I’ve seen when studying logic. But it feels like there must be some missing: we’ve found seven binary operators, and seven is such a strange number for something involving booleans. Since a binary operator has four possible input combinations, and for each of those it can output one of two booleans, there should be

binary operators. Two of these are essentially nullary operators, because they output the same thing regardless of their inputs, and four of these are essentially unary operators, because they ignore one input and just output either the other input or its negation. That leaves a total of ten binary operators, so where are the three we haven’t found?

Zachtronics released a game as a part of Last Call BBS called ChipWizard Professional. In this game, you are tasked with constructing fake electronic circuits, with one of the key tools being transistors made out of two types of silicon, N-Type and P-Type. I wanted to analyse what these transistors did, as boolean operators. One type of transistor, called NPN, was easy to model: applying charge to the P terminal connects the two N terminals, and if we take one of those N terminals as one input and the P terminal as the other input, then the transistor acts exactly like the “and” operator. The other one, called PNP, was more difficult: applying charge to the N terminal disconnects the two P terminals, so if we take one of those P terminals as one input and the N terminal as the other input, then we get the following operator:

You may notice, this is not equal to any of the binary operators we’ve looked at so far. The one it is most similar to is the “implies” operator: this is the negation of it. For that reason, I called it “nimplies”, and gave it the symbol

With this, there are only two missing symbols, and those can be found through symmetry. With most of the interesting binary operators, swapping the order of the inputs doesn’t change the output:

For two of our operators,

and

we can flip the order, giving us the final operators,

and

:

So now we have a complete list of all ten binary operators.

I didn’t find this very satisfying, so the ten binary operators sat in my mind as I worked on other projects relating to them. The two nullary operators,

and

have such a nice symmetry.

is really the same as

or

is really the same as

as almost everyone agrees that

is the standard order for booleans. And isn’t it nice that we have that symmetry for

and

which is kind of echoed in

and

Also,

is so clunky to write, and doesn’t always typeset nicely, and how do you even type it with just keyboard characters?

What followed was a satisfying realisation. Suppose we build all ten binary operators using only wedges and arrows. See,

is sometimes used to write “nand”, and

is sometimes used to write “nor”. Also, if

is the same as

then

is the same as

which is just

another wedge just like

and

This hints at a possible rule: negating the output of a boolean operator turns arrows into wedges pointing the same direction, and vice versa.

and

are negations of each other,

and

are negations of each other, and

and

are negations of each other. Extending this rule, we get the obvious pair of

and

but also the non-obvious pair of

and

which I often write as

omitting the space. Note that in some programming languages,

is a way of writing

beautifully tying this all together.

Then one night, I came up with this diagram:

This diagram is a Hasse diagram, as a lower operator connected by a line to a higher operator means the lower operator implies the higher operator. For example, if

is true, then all three operators it connects to that are above it are also true:

and

It is also symmetric in a few different ways. The first is that if you rotate the entire diagram 180 degrees, each symbol moves to where its negation was. As well as negating the output, we can negate the inputs, such as turning

into

which is equal to

as flipping this diagram horizontally negates the inputs. Lastly, we could negate both the inputs and output, giving us what is called the dual operator, which in this diagram is found by flipping the diagram vertically.

So I finally have a satisfying grip on the binary operators, now I can do some actual logic with them. But that will have to wait for another time.