Applications of Boolean Algebra: Claude Shannon and Circuit Design

Figure 1. As a graduate student at MIT, Claude Shannon (1916-2001) applied symbolic logic to electrical circuit design. (Source: MacTutor History of Mathematics Archive)

Introduction

In 1938, the American mathematician and electrical engineer Claude E. Shannon (1916–2001) completed a master’s thesis in electrical engineering at the Massachusetts Institute of Technology. Vannever Bush (1890–1974), dean of engineering at MIT and inventor of an early mechanical computer called the ‘differential analyser machine,’ was sufficiently impressed by Shannon’s thesis to sponsor its publication in an engineering journal. This award-winning paper, “A Symbolic Analysis of Relay and Switching Circuits" [4], went on to revolutionize the study of switches and relays, which in turn form the circuitry behind the binary arithmetic of modern computers.

Inspired by an idea from his study of symbolic logic in an undergraduate philosophy course, Shannon described the general problem to be solved and his proposed approach to it as follows [4, p. 713]:

In the control and protective circuits of complex electrical systems it is frequently necessary to make intricate interconnections of relay contacts and switches. Examples of these circuits occur in automatic telephone exchanges, industrial motor-control equipment, and in almost any circuits designed to perform complex operations automatically. In this paper a mathematical analysis of certain of the properties of such networks will be made. ...

The method of attack on these problems may be described briefly as follows: any circuit is represented by a set of equations, the terms of the equations corresponding to the various relays and switches in the circuit. A calculus is developed for manipulating these equations by simple mathematical processes, most of which are similar to ordinary algebraic algorisms. This calculus is shown to be exactly analogous to the calculus of propositions used in the symbolic study of logic.

Figure 2. Ideas about logic that originated with George Boole (1815-1864) are useful in
electrical circuit design.
(Source: MacTutor Archive)

The “calculus of propositions used in the symbolic study of logic” referenced here by Shannon is more generally known today by the name ‘boolean algebra’ in recognition of the Victorian mathematician George Boole (1815–1864) whose own groundbreaking work on the study of logic in [1, 2] launched this important field of mathematics.

From the writings of the numerous individuals who contributed to the tale of boolean algebra’s birth and development as both an abstract mathematical structure and a powerful applied tool, we have created three primary source project modules appropriate for students in introductory or intermediate discrete mathematics courses:

• a project which develops elementary set theory through original source excerpts from Boole’s own writings and that of two of the earliest mathematicians to make modifications in Boole’s approach to logic, presented in the Convergence article, Origins of Boolean Algebra in the Logic of Classes: George Boole, John Venn and C. S. Peirce;
• a project which examines the structure of a boolean algebra as an abstract axiomatized structure, presented in the Convergence article, Boolean Algebra as an Abstract Structure: Edward V. Huntington and Axiomatization; and
• the present project, “Applications of Boolean Algebra: Claude Shannon and Circuit Design,” which explores the application of boolean algebra to the particular problem of circuit design. 


All three projects are part of a larger collection published in Convergence, and an entire introductory discrete mathematics course can be taught from a selection of projects in this collection. For additional projects, see Primary Historical Sources in the Classroom: Discrete Mathematics and Computer Science. 


Our project Applications of Boolean Algebra: Claude Shannon and Circuit Design is ready for students, and the Latex source is also available for instructors who may wish to modify the project for students. The comprehensive “Notes to the Instructor” presented next are also appended to the project itself.

Figure 3.  As a researcher at Bell Labs, Claude Shannon founded information theory. He later became a professor at MIT.
 (Sources: Convergence Portrait Gallery, MIT News)

Notes to the Instructor 


The project “Applications of Boolean Algebra: Claude Shannon and Circuit Design” is designed for an introductory or intermediate course in discrete or finite mathematics that considers boolean algebra from either a mathematical or computer science perspective. The project does assume some (very minimal) familiarity with the set operations of union and intersection. This pre-requisite material may be gained by completing the companion (Boole) project described below, through reading a standard textbook treatment of elementary set operations, or via a short class discussion/lecture. Although no other specific pre-requisite knowledge is necessary for any part of the project, Sections 3 and 4 do assume slightly higher levels of mathematical maturity on the part of the students, roughly commensurate with that of a student who has completed Calculus I (for Section 3) and Calculus II (for Section 4). 


Based on an award-winning paper by Claude Shannon, “A Symbolic Analysis of Relay and Switching Circuits” [4], this project begins with a concise overview of two historical antecedents to Shannon’s work. The first of these is George Boole’s original work on ‘the logic of classes,’ included in part to provide students with a connection to another concrete example of a boolean algebra on which they can draw; the second of these is Edward Huntington’s work on the axiomatization of boolean algebras, included in part to emphasize to students the relationship between abstract axiomatic structures and concrete models as examples of those structures. Section 2 of the project introduces and develops the use of boolean expressions to represent parallel and series circuits. Within the concrete context of the 2-valued boolean algebra associated with these circuits, the standard properties of a boolean algebra are developed in this section; specific project questions in this section also provide students with practice in using these identities to simplify and manipulate boolean expressions. In Section 3, the concept of a ‘disjunctive normal form’ for boolean expressions is introduced in the context of circuit design. Section 4 then explores a more sophisticated method for applying boolean algebra to the problem of simplifying complicated circuits.

Since many of the concepts in this project are developed through the exercises, instructors are advised to work through all exercises in advance in order to determine which, if any, she may wish to omit. To complete the project in its entirety requires approximately four 50-minute class periods. Section 4 could easily be omitted for those who wish to have students study only the more fundamental concepts of boolean algebra, or for use with students who do not yet have the necessary level of mathematical maturity for the later sections. Both sections 3 and 4 could also be omitted for similar reasons. Instructors who do elect to complete Section 4 are advised to have students also complete Section 3.

Two other projects on boolean algebra are available as companions to this project, either or both of which could also be used independently of this project. The first companion project Origins of Boolean Algebra in the Logic of Classes: George Boole, John Venn and C. S. Peirce, is suitable as a preliminary to either the Huntington project or to the Shannon project. Without explicitly introducing modern notation for operations on sets (until the concluding section), that project develops a modern understanding of these operations and their basic properties within the context of early efforts to develop a symbolic algebra for logic. By steadily increasing the level of abstraction, that project also lays the ground work for a more abstract discussion of boolean algebra as a discrete structure, and explores a variety of other mathematical themes, including the notion of an inverse operation, issues related to mathematical notation, and standards of rigor and proof.

The second companion project Boolean Algebra as an Abstract Structure: Edward V. Huntington and Axiomatization could be used either as a preliminary to or as a follow-up to the Shannon project on circuit design. That project explores the early axiomatization of boolean algebra as an abstract structure, based on Huntington’s 1904 paper “Sets of Independent Postulates for the Algebra of Logic” [3]. In addition to introducing the now standard axioms for the boolean algebra structure, the project illustrates how to use these postulates to prove some basic properties of boolean algebras. Specific project questions also provide students with practice in using symbolic notation, and encourage them to analyze the logical structure of quantified statements. The project also examines Huntington’s use of the two-valued Boolean algebra on \(K=\{0,1\}\) — first studied by George Boole in his work on the logic of classes — as a model to establish the independence and consistency of one of his postulate sets. The final section of the project discusses modern (undergraduate) notation and axioms for boolean algebras, and provides several practice exercises to reinforce the ideas developed in the earlier sections.

Implementation with students of any of these projects may be accomplished through individually assigned work, small group work and/or whole class discussion; a combination of these instructional strategies is recommended in order to take advantage of the variety of questions included in the project.

Download the project Applications of Boolean Algebra: Claude Shannon and Circuit Design as a pdf file ready for classroom use.

Download the modifiable Latex source file for this project.

For more projects, see Primary Historical Sources in the Classroom: Discrete Mathematics and Computer Science.

Bibliography

[1] Boole, G., Mathematical Analysis of Logic, MacMillan, Barclay & MacMillan, Cambridge, 1847. Republished by Open Court, La Salle, 1952.

[2] Boole, G., An Investigation of the Laws of Thought on Which are Founded the Mathematical Theories of Logic and Probabilities, Walton and Maberly, London, 1854. Republished by Dover Publications, New York, 1958.

[3] Huntington, E. V., Sets of Independent Postulates for the Algebra of Logic, Transactions of the American Mathematical Society, 5:3 (1904), 288-309.

[4] Shannon, C. E., A Symbolic Analysis of Relay and Switching Circuits, American Institute of Electrical Engineers Transactions, 57 (1938), 713-723. Reprinted in Claude Elwood Shannon: Collected Papers, N. J. A. Sloane and A. D. Wyner (editors), IEEE Press, New York, 1993, 471-495.

Acknowledgment

The development of curricular materials for discrete mathematics has been partially supported by the National Science Foundation's Course, Curriculum and Laboratory Improvement Program under grants DUE-0717752 and DUE-0715392 for which the authors are most appreciative. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the National Science Foundation.