Anything that thinks logically
can be fooled by something else
that thinks at least as logically as it does.
~Douglas Adams

This is the second post in a multi-part series explaining how computers work. A computer is a thinking machine, a device which applies logic to any problem we ask it to. However, computers don’t know how to do this automatically. We have to teach them. And to teach them, we need a language of logic.

Last time, we introduced one such language of logic, Boolean algebra. This time, we learn how to make composite statements in Boole’s system.

This post will depend heavily on the preceding one, so if you didn’t read last week’s post, check it out here.

Let’s pick up where we left off. We’d just written out the truth tables for not, and, or, and if-then.

More Complex Statements

We can use the truth tables we’ve written out to construct statements of arbitrary complexity. All we have to do is combine them!

For example, we noticed earlier that the truth table for the word or is a bit outside of the colloquial use. The reason was that if both statements A and B are true, then the statement A or B is also true. It would be much more intuitive if the statement A or B was true if A was true or B was true, but false if both A and B were true. This would certainly describe a coin flip better!

The word for this operation is called xor, meaning exclusive or. Like and, or, not, and if-then, it has a truth table. We could simply define xor‘s truth table to have the properties we want, but instead, let’s try to get it by combining other truth tables.If we want to compute A xor B, we know we’ll need A or B and A and B—so let’s tabulate those first, all together in the same table:

All I’ve done for now is copied the truth tables for A and B and A or B onto a single table, then left some additional columns suggestively blank.

Since xor means we want one and only one input to be true–that is, we want either A or B to be true, but not both—let’s first write out what happens when we negate A and B. To do this, we look at its true/false values, found in the third column. On every row where we see a True in that column, we write a False in the fifth column (the first blank column). Likewise, every time we see a False in the third column, we write a True in the fifth column. The results are tabulated below. I added parentheses to Not (A and B) to emphasize that we’re negating the combined statement A and B, not just negating A.

We’re almost there! To finish, let’s calculate what (A or B) and (Not (A and B)) is, since that “compound operation” fully describes what we mean when we say xor. To do this, we use the and truth table from before. But instead of starting all the way back at the A and B columns, like we did before, we use the truth results we tabulated in the A or B and Not (A and B) columns of our new truth table:

Let’s look at the last column. Now that looks like an intuitive “xor” statement! If A and B are both true, then the statement A xor B—which is the same as (A or B) and not (A and B)—is false. If either A or B is true and the other input is false, A xor B is true. And if both A and B are false, A xor B is false. Perfect!

It turns out that we only need not and and or or to construct any other composite statement. Even the if A then B causality statement we introduced before can be written as a combination of the more elementary words: if A, then B is the same as not (A and not B). Try it out for yourself and see!

Truth Arithmetic

Earlier, I mentioned that we often use the numbers 1 and 0 for the values true and false respectively. Let’s try that now. In fact, let’s take it one step further and assign some familiar symbols to the words and and xor. Let’s make and a multiplication sign (x) and xor a plus sign (+).

This allows us to write out statements as equations whose right-hand sides tell us the true/false value of their left-hand sides. For example, true xor false becomes 0 + 1, and since 0 + 1 = 1, this means that true xor false is true. For another example, we can write true and false as 0 x 1 = 0, or false. If we concede that 1 + 1 = 0, then we can do this arithmetic with every combination of true and false. We only have to remember that when we negate, we replace every zero with a one and every one with a zero.

This is why binary is famously written as ones and zeroes!

Logic and Mathematics

A lot has happened in mathematics since Boole first described his language of logic. Mathematicians have carefully rebuilt the entire field from the solid foundation of these simple logical ideas. It’s not an exaggeration to say that all of mathematics is an intricate application of this kind of logic.

The way I like to think about it, mathematics is a way for us to keep ourselves honest. It’s a careful set of rules and a language to go with them, made so that when we think carefully about something, we know we’ll get the right answer. And it all starts with Boolean logic.

…Well, sort of. It doesn’t have to be this way. Boole chose to use two values of truth: true and false. But mathematicians have since discovered that we can do just as well with three truth values: true, false, and sort of. Or infinite truth values ranging from completely true to completely false. Thinking in this way is much harder, of course, so most people don’t. But it is possible. If there is an alien counterpart to Boole on an alien world somewhere, maybe those aliens think in terms of “yes,” “no,” and “sort of.”

Next time I’ll explain how we implement Boole’s logic electronically to build a computer.

Related Reading

After my previous post, many people suggested some excellent resources. Here they are.

• +Jean-Baptiste Queru has an absolutely wonderful post on how dizzyingly complicated computers are. You can find it here.
• +Kevin Clift found this video of implementing logic with strings and pulleys.
• Kevin Clift also found a textbook on Boolean Logic by Lewis Carroll, of Alice fame. You can find it here.
• +Olafur Jens Sigurdsson pointed me to this absolutely amazing MIT course that walks the student through the creation of a simple computer, from the hardware to the operating system to the program.
• Boolean logic is the topic of many first-year college computer science and mathematics courses around the world. If you’re interested in learning it at a deeper level, here’s an online course you can take.
• A good place to start is Wikipedia’s page on Boolean logic.
• Some math bloggers have attempted to describe Boolean logic with more depth. I particularly like professional math tutor John M.’s article. You can find it here.

You May Also Enjoy

If you liked this post, you might enjoy my other posts on mathematics:

• George Boole and the Language of Logic, Part 1, the first part of my series on computers.
• Taming Infinity, wherein I describe how mathematicians deal with the infinite.
• Panning For Primes, wherein I describe the Sieve of Eratosthenes, one way to generate prime numbers.
• Between Being and Non-Being, wherein I describe imaginary numbers.
• Throwing Darts for Pi, wherein I describe how you can approximate pi using darts.