George Boole and the Algebra of Logic

views updated

George Boole and the Algebra of Logic

Overview

Until the English mathematician George Boole (1815-1864) came along in the nineteenth century, logic was regarded as a branch of philosophy. By codifying it in algebraic form, Boole brought it into the realm of mathematics. His work formed the basis for the digital logic that drives today's computer and communications technologies.

Background

Logic deals with rules of correct reasoning. There are two types of logical arguments. Inductive reasoning generalizes from previous experience. Therefore it provides us with probabilities rather than certainties. Inductive reasoning is the basis of what we often call "common sense." For example, if you are eating a bunch of grapes, and every grape you have eaten so far is sweet, you expect the next one to be sweet as well. It probably will be, but there are no guarantees.

Deductive logic does not depend upon experience. Rather, it applies rules to determine whether a statement is valid based on the premises from which it is derived. It is important to note that "valid" does not necessarily mean "true." If the premises are true, and deductive logic is applied correctly, then the conclusion will be true. However, if any of the premises are false statements, then a perfectly valid chain of reasoning can lead to a nonsensical result.

Suppose you begin with the premise "All mammals are blue." Your second premise is "All cows are mammals." Therefore, you deduce that all cows are blue. This argument is valid given the premises you used. However, the first premise is false, so your conclusion is nonsense. Among computer programmers, this pitfall is expressed as "garbage in, garbage out."

A set of statements like the example just given, consisting of two premises and a conclusion, is called a syllogism. The ancient Greek philosopher Aristotle (384-322 b.c.) was among the first scholars to conduct a systematic study of the rules of deductive logic. His works on the subject are collected in a set of books called the Organon, or "instrument." The name is derived from the exploration of thought as the instrument by which knowledge is derived.

Aristotle was among the most influential thinkers of Western civilization. He planted logic firmly in the discipline of philosophy, and there it stayed for more than 2,000 years, until George Boole began looking for new applications for algebra.

Boole came from a background that did not augur well for him entering the mainstream of mathematics. First of all, he was English, at a time when the field was centered in Germany and France. Even in his native land, many would not look twice at him. England was a class-conscious society, and Boole was the son of a poor tradesman.

Boole was a youth of scholarly ambitions but limited economic prospects. By his mid-teens, after a few years in a mediocre working-class school and some tutoring in mathematics by his father, he found himself in need of a job to help support his family. Making the best of the situation, he became a schoolteacher, and he continued to educate himself in mathematics from books and periodicals. When he was 24 he began submitting papers to the Cambridge Mathematical Journal. The able editor of this publication, a Scotsman named D. F. Gregory, fortunately took an interest in the originality of Boole's work and overlooked the obscurity of the author.

Before he was 30 Boole was awarded a medal by the Royal Society for his contributions to the study of algebra. His work involved applying it to difficult problems in calculus and differential equations. Soon he realized it could be applied to logic as well. The algebraic symbols could be used to express logical operations and relationships.

In 1847 Boole published a pamphlet entitled "Mathematical Analysis of Logic." In it he first argued that logic should be considered a branch of mathematics rather than philosophy. On the strength of this work and his other publications, he was appointed to the faculty of Queen's College in Cork, Ireland, despite his lack of a university degree. He taught there for the rest of his life. Boole published a full exposition of his algebra of logic in 1854, in a book called An Investigation into the Laws of Thought, on which Are Founded the Mathematical Theories of Logic and Probabilities.

Impact

Boole's algebra of logic has had a profound influence on society, especially beginning with the computer revolution of the 1950s. All computers use Boolean operations to function. Since computers are at the heart of the world economy at the turn of the twenty-first century, the legacy of Boole's contributions is indeed enormous.

The symbolic method of logical inference that has come to be called Boolean algebra is based upon a two-valued, or binary scheme. The values may be expressed in many ways, such as true or false, one or zero, or on and off. It is this property that makes it so useful for implementing logic through electronic circuits. For example, "on" and "off" might be implemented as two different voltage levels in a circuit, or the presence or absence of current flow through a switch.

Boolean operations were once known mainly among the ranks of engineers and computer programmers. However, they have become more familiar to the general public as applied to searches in databases and on the Internet. While interfaces sometimes employ "natural language" and other mechanisms to assist users in constructing a search, the Boolean operations remain an efficient way to clearly express the desired action. When searching, these operations are applied to sets, or groups of objects or ideas.

The Boolean operation AND, for example, means that two or more conditions must be true. Suppose you are searching a used-car database for a blue Corvette. In order for a car to meet your criteria, both conditions must be met. Your search might read "color = blue AND model = Corvette."

The Boolean OR expresses a situation in which the criteria are met if any of the conditions are true. If you want a sports car, but would look at either Corvettes or Mustangs, you could enter a search such as "model = Corvette OR model = Mustang."

What would happen if you said "model = Corvette AND model = Mustang"? No car is both a Mustang and a Corvette, so you would get no car listings back. You have constructed a condition whose solution is the null set.

The OR operation will return objects in both sets referred to by its conditions. Often these conditions overlap. For example, suppose you are searching the library catalog for something to read. You enjoy reading science fiction. Two of your favorite authors are Jerry Pournelle and Larry Niven, who have collaborated on many books. You've read all their collaborations, though, and you'd like to know what else they've written. If you search for "Niven OR Pournelle," you will get all the books written by the two authors, including their collaborations. For the list you want, you might use the exclusive or, or NOR operation. This would give you books that are in the "Niven" set or the "Pournelle" set, but not those that are in both.

The not-and or NAND operation is the opposite of AND. It returns those items that meet neither condition. Finally, the NOT operator can be used alone, to express the set of objects that does not meet a given condition. It is called a unary operator because it refers to a single condition. The AND, OR, NAND, and NOR are binary operators because they refer to the relationship between two conditions.

In digital electronics the Boolean operators are implemented using logic gates, which are often etched onto integrated circuit chips. These process signals in accordance with their function. For example, the unary NOT gate has one input and one output. If the input is "0," the output is "1," and vice versa. The binary operations are implemented using logic gates with two inputs and one output. An OR gate has a "1" on the output if either input is "1." An AND gate requires both inputs to be "1" in order to have an output of "1."

These simple logic gates are used to design digital circuits of many kinds, found in devices ranging from coffeepots and calculators to theater-quality audio and video systems and the most powerful computers. Many of these devices would have been beyond Boole's wildest imaginings, but they owe their existence to the logical algebra he devised.

SHERRI CHASIN CALVO