Salamis Tablet - Journal of Computer History

From Boole to Bits - Claude Shannon's Digital Revolution

Boolean logic, the brainchild of nineteenth century English mathematician and philosopher George Boole, is intrinsic to modern computing. Today, every programmer uses Boolean logic to shape the decision making flow of software, and every student of computer science is trained in the application of Boolean algebra to circuit design. However, when Boole published his landmark work, An Investigation of the Laws of Thought, in 1854, computer software and electronic circuits couldn't have been further from his mind. It would be more than 80 years later that Claude Shannon, at the time still a graduate student at MIT, would launch the digital age by making the connection between Boole's calculus of logic and electronic engineering.

Born in 1916, Shannon was the son of a businessman and a high school principal. Growing up in Gaylord, Michigan he demonstrated an early inclination for electronics and mechanical devices. He idolized Thomas Edison and spent his childhood absorbed with erector sets, radio controlled toys, and even built a wireless telegraph.

This playfulness and love of gadgetry would characterize Shannon throughout his life. Journalists and other visitors to Entropy House, the "mansion" outside of Boston, Massachusetts where he lived for much of his later life, couldn't help but comment on his room full of inventions, toys and musical instruments.

While an undergraduate at the University of Michigan, Shannon took a philosophy course which exposed him to Boole's work in symbolic logic. Boole's fundamental achievement was to develop a method of expressing the various premises, conditions and conclusions of formal logic in a purely mathematical framework.

In Boole's propositional calculus as presented in Laws of Thought, a statement such as "All men are mortal." becomes y = vx, while the more elaborate construction of "Wealth consists of things transferable, limited in supply, and either productive of pleasure or preventive of pain." is expressed as w = st{pr + p(1- r) + r(1 - p)}.

In the method of expressing a natural language statement as an equation, some words and phrases are expressed as symbolic variables such as "x" and "y," while other key words dictate the structure of the equation itself. Boole observed that words such as AND, OR, ALL, SOME or NONE and grammatical constructs such as IF...THEN... had a larger and universal meaning. Of particular import in this discussion were the word "AND" which Boole expressed as multiplication (xy) and the word "OR" which Boole expressed as addition (x+y)

Boole was now able to take his mathematical abstraction of propositions and develop a complete calculus in which any number of propositions could be combined, manipulated and simplified using standard rules of algebra.

There was an interesting caveat to Boole's calculus. In order for his algebraic methods to work correctly and universally, the propositions could only be assigned one of two values. A true or affirmative statement was assigned a value of "1" and a false or negative statement was assigned a value of "0" - Boole's algebra was binary.

One can only imagine how Boole's elegant algebra would have captured the imagination of Shannon, who not only had enjoyed his erector sets as a child but also delighted in mysteries, puzzles and codes.

After completing his studies at the University of Michigan, in 1936 Shannon began graduate work at the Massachusetts Institute of Technology (MIT). There he took a position as a laboratory assistant to Vannevar Bush where he was given responsibility for Bush's differential analyzer.

Developed at MIT between 1925-31, Bush's machine was one of the most advanced computers of its day. It used a combination of mechanical gears, wheels and electric servo motors to solve second-order differential equations with up to 18 variables. Its original purpose was to solve equations describing electrical networks. Shannon's responsibilities included assisting visiting scientists and engineers in setting up the computer to solve specific problems by rearranging the room-sized machine's mechanical linkages.

The control mechanism for the differential analyzer contained about 100 electromagnetic relays. Like the transistors in a modern microprocessor, the relays made up a complex switching network controlling the operation of the analyzer through various on and off settings. It was the control mechanism that captured Shannon's attention. In a 1987 interview for Omni Magazine with Anthony Liversidge, he recalled his work at MIT with the differential analyzer:

"The main machine was mechanical, with spinning discs and integrators, and there was a complicated control circuit with relays. I had to understand both and work on them. The relay part got me interested. I knew about symbolic logic and realized the Boolean algebra was just the thing to take care of relay and switching circuits. I got all the books I could on symbolic logic and Boolean algebra, started interplaying the two, and wrote this master's thesis."

Shannon wrote the thesis in 1937 and in 1938 published a paper titled A Symbolic Analysis of Relay and Switching Circuits based on the thesis. In his correlation between symbolic logic and switching circuits a closed switch with electricity flowing takes on the role of a positive statement with a value of 1, while an open switch is a negative statement with a value of 0. Applying Boolean concepts to more complex circuits, two switches wired in a parallel circuit form the equivalent of a Boolean OR relationship while two switches in series circuit constitute a Boolean AND.

Despite the complexity of the subject matter, Shannon's paper is reasonably accessible and even engaging. It is also remarkably complete. He cleanly sets out the analogues between the calculus of propositions and his new application of Boolean algebra to switching circuits, and provides a primer in the application of the method. Shannon even gives several complete examples of circuits including an electric combination lock and a binary adder.

Virtually overnight, Shannon's work transformed the practice of switching circuit design from a rudimentary art driven primarily by intuition and experimentation, to a structured process guided by precise, repeated steps. Using the Boolean-derived methodologies, engineers could now not only effectively design circuits that perform mathematical calculation, but circuits that execute elaborate conditional control functions as well. In the coming decade, these techniques would be put to use to build the first true modern computers.

Shannon would go on to tremendous success and renown. After earning a Ph.D. from MIT in 1940 he took a position at Bell Laboratories in 1941 where like so many other computing pioneers of his generation he became involved in various activities in support of the war effort. In 1948 he published a paper titled A Mathematical Theory of Communication which is considered to be the founding document in the field of information theory. In that and subsequent papers, Shannon introduced the world to the notion of information as a commodity which can be quantified (in bits) and studied. He developed theories and techniques in communications optimization and error correction that are essential components of modern computing.

Sources:

Slater, Robert., Portraits in Silicon, The MIT Press, Cambridge, Massachusetts, 1987. ISBN 0-262-19262-4.

Ifrah, Georges. The Universal History of Computing: From the Abacus to the Quantum Computer. John Wiley & Sons.,2001. ISBN 0-471-39671-0.

Shannon, C. E., A Symbolic Analysis of Relay and Switching Circuits AIEE Transactions. 57, 1938

Liversidge, Anthony., Interview: Father of the Electronic Information Age, Omni Magazine, Vol 9, No. 11, August 1987

Horgan, John., Claude, Shannon: Tinkerer, Prankster, and Father of Information Theory., IEEE Spectrum, April 1992

Waldrop, M. Mitchell., Claude Shannon: Reluctant Father of the Digital Age., www.technologyreview.com, July 1, 2001

Home