True or False: From George Boole to Every Computer

1 This section explains how an idea about logic from the 1800s became the way a computer makes a choice, and how a program asks questions that have only two possible answers.

George Boole's Algebra of Logic

2 George Boole was born in Lincoln, England, on November 2, 1815. His family could not pay for an expensive education, so he taught himself foreign languages and advanced mathematics from books. He never earned a university degree. Even so, in 1849 he became the first professor of mathematics at Queen's College in Cork, Ireland.

3 In 1854, Boole published a book called An Investigation of the Laws of Thought. In it, he wrote logic as a kind of algebra, so that a chain of reasoning could be worked out step by step, the way a student solves an equation. His symbols could take only two values, 1 and 0. Today, a value that can only be true or false is called a Boolean value, after him. Boole died in Ireland on December 8, 1864. For many years afterward, his algebra was studied mostly by mathematicians.

From Logic to Switches

4 In 1937, a student at the Massachusetts Institute of Technology named Claude Shannon wrote a master's thesis called "A Symbolic Analysis of Relay and Switching Circuits." A relay is a switch that electricity opens or closes, and the telephone systems of that time were built from many of them. Shannon showed that Boole's algebra could describe how such switches were connected and could be used to design the circuits. One writer later called it possibly the most important master's thesis of the century.

5 A switch has only two states, closed or open, in the same way that a Boolean value is only true or false, 1 or 0. By connecting switches in different ways, an engineer can build circuits that carry out the three operations and, or and not. According to the Computer History Museum, those three operations are enough to perform every logic function a digital computer needs. Figure 1 shows the path from Boole's book in 1854, to Shannon's switches in 1937, to the questions a program asks today.

Questions a Program Asks

6 A program makes a choice by asking a question whose answer is true or false. A comparison checks how two values relate, such as whether one number is less than another, and its answer is always a Boolean value. For example, 8 < 5 is false, because 8 is not less than 5, while 8 > 5 is true. In this class, comparisons are written with six signs: < for less than, > for greater than, ≤ for less than or equal to, ≥ for greater than or equal to, = for equal to and ≠ for not equal to. Java writes some of these signs with two characters, such as >= for ≥, but every comparison still answers true or false.

7 A logical operator joins Boolean values or changes one. The operator and is true only when both sides are true. The operator or is true when at least one side is true. The operator not flips true to false and false to true. A question such as "age ≥ 13 and age ≤ 19" uses two comparisons and one logical operator to ask whether a person is a teenager. For a person who is 22, the first comparison is true and the second is false, so the whole question is false.

8 A comparison can also use the remainder from the day before. A number is even when it divides by 2 with nothing left over. For that reason, the comparison "n rem 2 = 0" is true for every even number and false for every odd number. The steps below ask that question about 14 and about 9.

1show 14 rem 2 = 0
2show 9 rem 2 = 0

true
false

9 The comparison "n rem 2 ≠ 0" asks the opposite question, so it is true exactly when n is odd. Today's question asks how a computer could decide whether a number is even, and a comparison with a remainder is one answer to it. On today's bench, boxes hold Boolean values in the same way that they held numbers before, and a trace table records whether each box holds true or false after every line.

Summary

10 Boole wrote logic as an algebra of two values in 1854, and Shannon showed in 1937 that switches could carry out that algebra. A comparison asks a question whose answer is a Boolean value, true or false. A logical operator such as and, or or not joins or flips those answers. Every choice a program makes, such as deciding whether a number is even, comes down to a question of this kind.

Sources: O'Connor and Robertson, George Boole (MacTutor History of Mathematics, University of St Andrews); Burris, George Boole (Stanford Encyclopedia of Philosophy); Boole, An Investigation of the Laws of Thought (1854; Project Gutenberg); Computer History Museum, Revolution: Digital Logic; MIT News, MIT Professor Claude Shannon dies; was founder of digital communications (2001); MIT Libraries, DSpace record for Shannon's thesis; Oracle, The Java Tutorials: Equality, Relational, and Conditional Operators and Primitive Data Types.