Logic with Switches

What is truth? Aristotle thought that logic had something to do with it. The collection of his teachings known as the Organon (which dates from the fourth century BCE) is the earliest extensive writing on the subject of logic. To the ancient Greeks, logic was a means of analyzing language in the search for truth and thus was considered a form of philosophy. The basis of Aristotle’s logic was the syllogism. The most famous syllogism (which isn’t actually found in the works of Aristotle) is

All men are mortal;

Socrates is a man;

Hence, Socrates is mortal.

In a syllogism, two premises are assumed to be correct, and from these a conclusion is deduced.

The mortality of Socrates might seem straightforward enough, but there are many varieties of syllogisms. For example, consider the following two premises, proposed by the 19th-century mathematician Charles Dodgson (also known as Lewis Carroll):

All philosophers are logical;

An illogical man is always obstinate.

The conclusion—Some obstinate persons are not philosophers—isn’t obvious at all. Notice the unexpected and disturbing appearance of the word some.

For over two thousand years, mathematicians wrestled with Aristotle’s logic, attempting to corral it using mathematical symbols and operators. Prior to the 19th century, the only person to come close was Gottfried Wilhelm von Leibniz (1648–1716), who dabbled with logic early in life but then went on to other interests (such as independently inventing calculus at the same time as Isaac Newton).

And then came George Boole.

George Boole was born in England in 1815 into a world where the odds were certainly stacked against him. Because he was the son of a shoemaker and a former maid, Britain’s rigid class structure would normally have prevented Boole from achieving anything much different from his ancestors. But aided by an inquisitive mind and his helpful father (who had strong interests in science, mathematics, and literature), young George gave himself the type of education that was normally the privilege of upper-class boys; his studies included Latin, Greek, and mathematics. As a result of his early papers on mathematics, in 1849 Boole was appointed the first Professor of Mathematics at Queen’s College, Cork, in Ireland.

Several mathematicians in the mid-1800s had been working on a mathematical definition of logic (most notably Augustus De Morgan), but it was Boole who had the real conceptual breakthrough, first in the short book The Mathematical Analysis of Logic, Being an Essay Towards a Calculus of Deductive Reasoning (1847) and then in a much longer and more ambitious text, An Investigation of the Laws of Thought on Which Are Founded the Mathematical Theories of Logic and Probabilities (1854), more conveniently referred to as The Laws of Thought. Boole died in 1864, at the age of 49, after hurrying to class in the rain and contracting pneumonia.

The title of Boole’s 1854 book suggests an ambitious motivation: Boole believed that the human brain uses logic to think, so if we were to find a way to represent logic with mathematics, we would also have a mathematical description of how the brain works. But Boole’s mathematics can be studied without necessarily buying in to his neuropsychology.

Boole invented a whole different kind of algebra that was eventually called Boolean algebra to distinguish it from conventional algebra.

In conventional algebra, letters are often used to stand for numbers. These are called operands, and they are combined in various ways with operators, most often + and ×. For example:

When we do conventional algebra, we follow certain rules. These rules have probably become so ingrained in our practice that we no longer think of them as rules and might even forget their names. But rules indeed underlie all the workings of any form of mathematics.

The first rule is that addition and multiplication are commutative. That means we can switch around the symbols on each side of the operators:

By contrast, subtraction and division are not commutative.

Addition and multiplication are also associative, that is

And finally, multiplication is said to be distributive over addition:

Another characteristic of conventional algebra is that it always deals with numbers, such as pounds of tofu or numbers of ducks or distances that a train travels or the seconds of a day.

It was Boole’s genius to make algebra more abstract by divorcing it from concepts of number. In Boolean algebra, the operands refer not to numbers but instead to classes. A class is simply a group of things, similar to what in later times came to be known as a set.

Let’s talk about cats. Cats can be either male or female. For convenience, we can use the letter M to refer to the class of male cats and F to refer to the class of female cats. Keep in mind that these two symbols do not represent numbers of cats. The number of male and female cats can change by the minute as new cats are born and old cats (regrettably) pass away. The letters stand for classes of cats—cats with specific characteristics. Instead of referring to male cats, we can just say “M.”

We can also use other letters to represent the color of the cats. For example, T can refer to the class of tan cats, B can be the class of black cats, W the class of white cats, and O the class of cats of all “other” colors—all cats not in the class T, B, or W.

Finally (at least as far as this example goes), cats can be either neutered or unneutered. Let’s use the letter N to refer to the class of neutered cats and U for the class of unneutered cats.

In conventional (numeric) algebra, the operators + and × are used to indicate addition and multiplication. In Boolean algebra, the same + and × symbols are used, and here’s where things might get confusing. Everybody knows how to add and multiply numbers in conventional algebra, but how do we add and multiply classes?

Well, we don’t actually add and multiply in Boolean algebra. Instead, the + and × symbols mean something else entirely.

The + symbol in Boolean algebra means a union of two classes. A union of two classes is everything in the first class combined with everything in the second class. For example, B + W represents the class of all cats that are either black or white.

The × symbol in Boolean algebra means an intersection of two classes. An intersection of two classes is everything that is in both the first class and the second class. For example, F × T represents the class of all cats that are both female and tan. As in conventional algebra, we can write F × T as F·T or simply FT (which is what Boole preferred). You can think of the two letters as two adjectives strung together: “female tan” cats.

To avoid confusion between conventional algebra and Boolean algebra, sometimes the symbols ∪ and ∩ are used for union and intersection instead of + and ×. But part of Boole’s liberating influence on mathematics was to make the use of familiar operators more abstract, so I’ve decided to stick with his decision not to introduce new symbols into his algebra.

The commutative, associative, and distributive rules all hold for Boolean algebra. What’s more, in Boolean algebra the + operator is distributive over the × operator. This isn’t true of conventional algebra:

The union of white cats and black female cats is the same as the intersection of two unions: the union of white cats and black cats, and the union of white cats and female cats. This is somewhat difficult to grasp, but it works.

Three more symbols are necessary to complete Boolean algebra. Two of these symbols might look like numbers, but they’re really not because they’re treated a little differently than numbers. The symbol 1 in Boolean algebra means “the universe”—that is, everything we’re talking about. In this example, the symbol 1 means “the class of all cats.” Thus,

This means that the union of male cats and female cats is the class of all cats. Similarly, the union of tan cats and black cats and white cats and other colored cats is also the class of all cats:

And you achieve the class of all cats this way, too:

The 1 symbol can be used with a minus sign to indicate the universe excluding something. For example,

is the class of all cats except the male cats. The universe excluding all male cats is the same as the class of female cats:

The third symbol that we need is the 0 (zero), and in Boolean algebra the 0 means an empty class—a class of nothing. The empty class results when we take an intersection of two mutually exclusive classes—for example, cats that are both male and female:

Notice that the 1 and 0 symbols sometimes work the same way in Boolean algebra as in conventional algebra. For example, the intersection of all cats and female cats is the class of female cats:

The intersection of no cats and female cats is the class of no cats:

The union of no cats and all female cats is the class of female cats:

But sometimes the result doesn’t look the same as in conventional algebra. For example, the union of all cats and female cats is the class of all cats:

This doesn’t make much sense in conventional algebra.

Because F is the class of all female cats, and (1 − F) is the class of all cats that aren’t female, the union of these two classes is 1:

And the intersection of the two classes is 0:

Historically, this formulation represents an important concept in logic: It’s called the law of contradiction, and it indicates that something can’t be both itself and the opposite of itself.

Where Boolean algebra really looks different from conventional algebra is in a statement like this:

The statement makes perfect sense in Boolean algebra: The intersection of female cats and female cats is still the class of female cats. But it sure wouldn’t look quite right if F referred to a number. Boole considered

to be the single statement that differentiates his algebra from conventional algebra. Another Boolean statement that looks funny in terms of conventional algebra is this:

The union of female cats and female cats is still the class of female cats.

Boolean algebra provides a mathematical method for solving the syllogisms of Aristotle. Let’s look at the first two-thirds of that famous syllogism again, but now using gender-neutral language:

All persons are mortal;

Socrates is a person.

We’ll use P to represent the class of all persons, M to represent the class of mortal things, and S to represent the class of Socrates. What does it mean to say that “all persons are mortal”? It means that the intersection of the class of all persons and the class of all mortal things is the class of all persons:

It would be wrong to say that P × M = M, because the class of all mortal things includes cats, dogs, and elm trees.

Saying, “Socrates is a person” means that the intersection of the class containing Socrates (a very small class) and the class of all persons (a much larger class) is the class containing Socrates:

Because we know from the first equation that P equals (P × M), we can substitute that into the second equation:

By the associative law, this is the same as

But we already know that (S × P) equals S, so we can simplify by using this substitution:

And now we’re finished. This formula tells us that the intersection of Socrates and the class of all mortal things is S, which means that Socrates is mortal. If we found instead that (S × M) equaled 0, we’d conclude that Socrates wasn’t mortal. If we found that (S × M) equaled M, the conclusion would have to be that all mortals were Socrates!

Using Boolean algebra might seem like overkill for proving this obvious fact (particularly considering that Socrates demonstrated his mortality 2400 years ago), but Boolean algebra can also be used to determine whether something satisfies a certain set of criteria.

Perhaps one day you walk into a pet shop and say to the salesperson, “I want a male cat, neutered, either white or tan; or a female cat, neutered, any color but white; or I’ll take any cat you have as long as it’s black.” And the salesperson says to you, “So you want a cat from the class of cats represented by the following expression:

Right?” And you say, “Yes! Exactly!”

In verifying that the salesperson is correct, you might want to represent the concepts of union and intersection using the words OR and AND. I’m capitalizing these words because the words normally represent concepts in English, but they can also represent operations in Boolean algebra. When you form a union of two classes, you’re actually accepting things from the first class OR the second class. And when you form an intersection, you’re accepting only those things in both the first class AND the second class. In addition, you can use the word NOT wherever you see a 1 followed by a minus sign. In summary,

• + (a union) can also mean OR.

• × (an intersection) can also mean AND.

• 1 − (the universe without something) means NOT.

So the expression can also be written like this:

This is very nearly what you said. Notice how the parentheses clarify your intentions. You want a cat from one of three classes:

With this formula written down, the salesperson can perform something called a Boolean test. This involves another variation of Boolean algebra, where the letters refer to properties or characteristics or attributes of cats, and they can be assigned the numbers 0 or 1. The numeral 1 means Yes, True, this particular cat satisfies these criteria, while the numeral 0 means No, False, this cat doesn’t satisfy these criteria.

First the salesperson brings out an unneutered tan male. Here’s the expression of acceptable cats:

And here’s how it looks with 0s and 1s substituted:

Notice that the only symbols assigned 1s are M and T because the cat is male and tan.

What we must do now is simplify this expression. If it simplifies to 1, the cat satisfies your criteria; if it simplifies to 0, the cat doesn’t. While we’re simplifying the expression, keep in mind that we’re not really adding and multiplying, although generally we can pretend that we are. Most of the same rules apply when + means OR and × means AND. (Sometimes in modern texts the symbols ∧ and ∨ are used for AND and OR instead of × and +. But here’s where the + and × signs perhaps ease the job, because the rules are similar to conventional algebra.)

When the × sign means AND, the possible results are

In other words, the result is 1 only if both the left operand AND the right operand are 1. This operation works exactly the same way as regular multiplication, and it can be summarized in a little table. The operation is shown in the upper-left corner, and the possible combinations of operators are shown in the top row and the left column:

AND	0	1
0	0	0
1	0	1

When the + sign means OR, the possible results are

The result is 1 if either the left operand OR the right operand is 1. This operation produces results very similar to those of regular addition, except that in this case 1 + 1 equals 1. (If a cat is tan or if a cat is tan means that it’s tan.) The OR operation can be summarized in another little table:

OR	0	1
0	0	1
1	1	1

We’re ready to use these tables to calculate the result of the expression

The result 0 means No, False, this kitty won’t do.

Next the salesperson brings out a neutered white female. The original expression was

Substitute the 0s and 1s again:

And simplify it:

And another poor kitten must be rejected.

Next the salesperson brings out a neutered gray female. (Gray qualifies as an “other” color—not white or black or tan.) Here’s the expression:

Now simplify it:

The final result 1 means Yes, True, a kitten has found a home. (And it was the cutest one too!)

Later that evening, when the kitten is curled up sleeping in your lap, you wonder whether you could have wired some switches and a lightbulb to help you determine whether particular kittens satisfied your criteria. (Yes, you are a strange kid.) Little do you realize that you’re about to make a crucial conceptual breakthrough. You’re about to perform some experiments that will unite the algebra of George Boole with electrical circuitry and thus make possible the design and construction of digital computers. But don’t let that intimidate you.

To begin your experiment, you connect a lightbulb and battery as you would normally, but you use two switches instead of one:

The world icon in the outer margin indicates that an interactive version of the circuit is available on the website CodeHiddenLanguage.com.

Switches connected in this way—one right after the other—are said to be wired in series. If you close the left switch, nothing happens:

Similarly, if you leave the left switch open and close the right switch, nothing happens. The lightbulb lights up only if both the left switch and the right switch are closed, as shown here:

The key word here is and. Both the left switch and the right switch must be closed for the current to flow through the circuit.

This circuit is performing a little exercise in logic. In effect, the lightbulb is answering the question “Are both switches closed?” We can summarize the workings of this circuit in the following table:

Left Switch	Right Switch	Lightbulb
Open	Open	Not lit
Open	Closed	Not lit
Closed	Open	Not lit
Closed	Closed	Lit

If you think of the switches and the lightbulb as Boolean operators, then these states can be assigned numbers of 0 and 1. A 0 can mean “switch is open” and a 1 can mean “switch is closed.” A lightbulb has two states; a 0 can mean “lightbulb is not lit” and a 1 can mean “lightbulb is lit.” Now let’s simply rewrite the table:

Left Switch	Right Switch	Lightbulb
0	0	0
0	1	0
1	0	0
1	1	1

Notice that if we swap the left switch and the right switch, the results are the same. We really don’t have to identify which switch is which. So the table can be rewritten to resemble the AND and OR tables that were shown earlier:

Switches in Series	0	1
0	0	0
1	0	1

And indeed, this is the same as the AND table. Check it out:

AND	0	1
0	0	0
1	0	1

This simple circuit is actually performing an AND operation in Boolean algebra.

Now try connecting the two switches a little differently:

These switches are said to be connected in parallel. The difference between this and the preceding connection is that this lightbulb will light if you close the top switch:

or close the bottom switch:

or close both switches:

The lightbulb lights if the top switch or the bottom switch is closed. The key word here is or.

Again, the circuit is performing an exercise in logic. The lightbulb answers the question “Is either switch closed?” The following table summarizes how this circuit works:

Left Switch	Right Switch	Lightbulb
Open	Open	Not lit
Open	Closed	Lit
Closed	Open	Lit
Closed	Closed	Lit

Again, using 0 to mean an open switch or an unlit lightbulb and 1 to mean a closed switch or a lit lightbulb, this table can be rewritten this way:

Left Switch	Right Switch	Lightbulb
0	0	0
0	1	1
1	0	1
1	1	1

Again, it doesn’t matter if the two switches are swapped, so the table can also be rewritten like this:

Switches in Parallel	0	1
0	0	1
1	1	1

And you’ve already guessed that this is the same as the Boolean OR:

OR	0	1
0	0	1
1	1	1

This means that two switches in parallel are performing the equivalent of a Boolean OR operation.

When you originally entered the pet shop, you told the salesperson, “I want a male cat, neutered, either white or tan; or a female cat, neutered, any color but white; or I’ll take any cat you have as long as it’s black,” and the salesperson developed this expression:

Now that you know that two switches wired in series perform a logical AND (which is represented by a × sign) and two switches in parallel perform a logical OR (which is represented by the + sign), you can wire up eight switches like so:

Each switch in this circuit is labeled with a letter—the same letters as in the Boolean expression. W means NOT W and is an alternative way to write 1 − W. Indeed, if you go through the wiring diagram from left to right starting at the top and moving from top to bottom, you’ll encounter the letters in the same order in which they appear in the expression. Each × sign in the expression corresponds to a point in the circuit where two switches (or groups of switches) are connected in series. Each + sign in the expression corresponds to a place in the circuit where two switches (or groups of switches) are connected in parallel.

As you’ll recall, the salesperson first brought out an unneutered tan male. Close the appropriate switches:

Although the M, T, and NOT W switches are closed, we don’t have a complete circuit to light up the lightbulb. Next the salesperson brought out a neutered white female:

Again, the right switches aren’t closed to complete a circuit. But finally, the salesperson brought out a neutered gray female:

And that’s enough to complete the circuit, light up the lightbulb, and indicate that the kitten satisfies all your criteria.

George Boole never wired such a circuit. He never had the thrill of seeing a Boolean expression realized in switches, wires, and lightbulbs. One obstacle, of course, was that the incandescent lightbulb wasn’t invented until 15 years after Boole’s death. But the telegraph had been invented ten years before the publication of Boole’s The Laws of Thought, and an important part of the telegraph system was a simple device that could perform operations of logic with much more agility than mere switches could.