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 B.C.E.) 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

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 nineteenth-century mathematician Charles Dodgson (also known as Lewis Carroll):

The conclusion isn't obvious at all. (It's "Some obstinate persons are not philosophers." 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 nineteenth 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 to a world where the odds were certainly stacked against him. Because he was the son of a shoe-maker 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 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: Because the rational human brain uses logic to think, if we were to find a way in which logic can be represented by mathematics, we would also have a mathematical description of how the brain works. Of course, nowadays this view of the mind seems to us quite naive. (Either that or it's way ahead of its time.)

Boole invented a kind of algebra that looks and acts very much like conventional algebra. In conventional algebra, the operands (which are usually letters) stand for numbers, and the operators (most often + and x) indicate how these numbers are to be combined. Often we use conventional algebra to solve problems such as this: Anya has 3 pounds of tofu. Betty has twice as much tofu as Anya. Carmen has 5 pounds more tofu than Betty. Deirdre has three times the tofu that Carmen has. How much tofu does Deirdre have?

To solve this problem, we first convert the English to arithmetical statements, using four letters to stand for the pounds of tofu that each of the four women has:

We can combine these four statements into one statement by substitution and then finally perform the additions and multiplications:

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 operations:

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 ages of family members. It was Boole's genius to make algebra more abstract by divorcing it from concepts of number. In Boolean algebra (as Boole's algebra was eventually called), the operands refer not to numbers but instead to classes. A class is simply a group of things, 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 x are used to indicate addition and multiplication. In Boolean algebra, the same + and x 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 x 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 x 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 x T represents the class of all cats that are both female and tan. As in conventional algebra, we can write F x 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 U and ∩ are used for union and intersection instead of + and x. 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 x 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.

Two more symbols are necessary to complete Boolean algebra. These two symbols might look like numbers, but they're really not because they're sometimes 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 other symbol that we need is the 0, 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 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:

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 x M = M, because the class of all mortal things includes cats, dogs, and elm trees.

To say, "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 x M) we can substitute that into the second equation:

By the associative law, this is the same as

But we already know that (S x 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 x M) equaled 0, we'd conclude that Socrates wasn't mortal. If we found that (S x M) equaled M, the conclusion would have to be that Socrates was the only mortal thing and everything else was immortal!

Using Boolean algebra might seem like overkill for proving the obvious fact (particularly considering that Socrates proved himself mortal 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 forgo the concepts of union and intersection and instead switch to 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,

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. Without making a big fuss about it, I've subtly shifted to a somewhat different form of Boolean algebra. In this form of Boolean algebra, letters no longer refer to classes. Instead, the letters can now be assigned numbers. The catch is that they can be assigned only the number 0 or 1. The numeral 1 means Yes, True, this particular cat satisfies these criteria. 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 x means AND. (Sometimes in modern texts the symbols ^ and ν are used for AND and OR instead of x and +. But here's where the + and x signs perhaps make the most sense.)

When the x 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, similar to the way the addition and multiplication tables were shown in Chapter 8:

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. The OR operation can be summarized in another little table:

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 computers that work with binary numbers. 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:

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 on the next page.

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:

In the preceding chapter, we saw how binary digits, or bits, can represent information—everything from numbers to the direction of Roger Ebert's thumb. We were able to say that a 0 bit means "Ebert's thumb points down" and a 1 bit means "Ebert's thumb points up." A switch has two positions, so it can represent a bit. We can say that a 0 means "switch is open" and a 1 means "switch is closed." A lightbulb has two states; hence it too can represent a bit. We can say that a 0 means "lightbulb is not lit" and a 1 means "lightbulb is lit." Now we simply rewrite the table:

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:

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

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:

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:

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

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

which 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 x 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. ( 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 that they appear in the expression. Each x 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 Samuel Morse had demonstrated his telegraph in 1844—ten years before the publication of Boole's The Laws of Thought—and it would be simple to substitute a telegraph sounder for the lightbulb in the circuit shown above.

But nobody in the nineteenth century made the connection between the ANDs and ORs of Boolean algebra and the wiring of simple switches in series and in parallel. No mathematician, no electrician, no telegraph operator, nobody. Not even that icon of the computer revolution Charles Babbage (1792–1871), who had corresponded with Boole and knew his work, and who struggled for much of his life designing first a Difference Engine and then an Analytical Engine that a century later would be regarded as the precursors to modern computers. What might have helped Babbage, we know now, was the realization that perhaps instead of gears and levers to perform calculations, a computer might better be built out of telegraph relays.

Yes, telegraph relays.