Boolean Algebra

Boolean Algebra

In 1847 George Boole (1815–1864), an English mathematician, published one of the works that founded symbolic logic. His combination of ideas from classical logic and algebra resulted in what is called Boolean algebra.

Using variables and symbols, Boole designed a language for describing and manipulating logical statements and determining if they are true or not. The variables stand for statements that are either true or false. The symbols +, * and − represent and, or, and not and are equivalent to the symbols [.logicaland], [.logicalor], and − used in the truth tables in logic. Although truth tables use T and F (for true and false respectively) to indicate the state of the sentence, Boolean algebra uses 1 and 0.

The relationship between Boolean algebra, set algebra, logic, and binary arithmetic has given Boolean algebra a central role in the development of electronic digital computers. Besides its many applications in the design of computers, it forms the foundation of information theory.

Truth Tables

Boolean algebra is based on propositions, which are non-ambiguous sentences that can be either true or false. One can combine these propositions in a variety of ways by using the connectives and and or, or one can negate them by preceding them with not. The results of these operations on propositions are dictated by the rules of Boolean algebra. For example, if one says: "I will buy green mittens," then she is actually saying that she will buy mittens and those mittens will be green. Therefore the properties of "mittens" and "green" will have to be present in all her "hand-covering" purchases. This will exclude gloves and all non-green mittens. How does this work out using truth tables? Let A represent "mittens," B represent "green." Figure 1(a) shows how the statement "mittens and green" is represented using truth tables, while Figure 1(b) shows the same statement using Boolean algebra.

What the tables indicate is that if an item does not possess both the quality of being a mitten and the quality of being green, then it will be discarded. Only those that satisfy both qualities will be selected.

On the other hand, if one says: "I will buy gloves or mittens," then he is actually saying that he will buy mittens, or gloves, or some combination. This means that he will have a great assortment of "hand-covering" garments. Let A represent "mittens" and B represent "gloves." Figure 2(a) shows how the statement "mittens or gloves" is represented using truth tables, while Figure 2(b) shows the same statement using Boolean algebra.

What the tables indicate is that an item will be selected if it possesses both qualities of mitten and glove, or possesses only one quality, either glove or mitten. Only those that satisfy neither quality will be discarded—for example, all red socks.

One can also say: "I will buy something to cover my hands, but not mittens." Let A represent "mittens." Figure 3(a) shows how the statement "not mittens" is represented using truth tables, while Figure 3(b) shows the same statement using Boolean algebra.

The tables indicate that if an item is a mitten then its negation, –A, represents a non-mitten—for example, a glove or a sock.

Computer Design

Boolean algebra can be applied to the design and simplification of complex circuits present in computers because computer circuits are two-state devices: they can be either off or on. This corresponds to the general representation of Boolean algebra with two elements, 0 and 1. To show how this works, take a look at two simple circuits, "and," and "or," which correspond to the first two sets of tables presented earlier. These simple circuits consist of a power source—a battery connected by a wire to a destination—and a lamp with two switches that control the flow of electricity. The position of a switch either allows electricity to flow from the power source to the destination, or stops it. For example, if the switch is up, or open, then electricity does not flow, and this condition is represented by a 0. However, if the switch is down, or closed, the electricity will flow, and this is represented by 1.

Figure 4 shows the diagram of a two-switch series circuit, where electricity will flow from the source to the destination only if both switches are closed. This diagram represents the and condition of Boolean algebra.

A circuit where electricity flows whenever at least one of the switches is closed is known as a parallel circuit. This corresponds to the or condition of Boolean algebra. Figure 5 shows the diagram of a two-switch parallel circuit.

To represent the not condition, one must remember that in this system a switch has only two possible positions, open or closed. Its complement is a switch that will have the opposite position. For example, if switch A is open, its complement will be closed and vice versa. Logic designers can use these diagrams to plan complex computer circuits that will perform the needed functions for a specific machine.

Information Theory

Boolean algebra is used in information theory because almost all search engines allow someone to enter queries in the form of logical expressions. The operator and is used to narrow a query whereas or is used to broaden it. The operator not is used to exclude specific words from a query. For example, if one is looking for information about "privacy in computer environments," she could phrase her query as "computer and privacy," or "computer or privacy," or even "computer and privacy not mainframes." The amount of information received from each query will be different.

The first query will retrieve fewer documents because it will only select those that contain both terms. The second will retrieve many documents because it will select those that contain "computer," those that contain "privacy," and also those that contain both terms. The last query will retrieve documents that contain both "privacy" and "computer," while anything containing the term "mainframe" will be discarded.

When using search engines, one must realize that each one will access its database differently. Typically the same search performed in more than one database will not return the same result. To do a thorough search, one must become familiar with a few of the different search engines and understand their major features, such as Boolean logic and truncation. In addition, one must check the search engine's documentation often because it can change frequently.

see also Algorithms; Binary Number System; Boole, George; Decision Support Systems; Digital Logic Design.

Ida M. Flynn

Bibliography

McCullough, Robert N. Mathematics for Data Processing, 2nd ed. Englewood, CO: Morton Publishing Co., 2001.

Warring, Ronald H. Logic Made Easy. Summit, PA: TAB Books, Inc., 1985.

Whitesitt, J. Eldon. Boolean Algebra and Its Applications. New York: Dover Publications, Inc., 1995.