Applications of Boolean Algebra: Claude Shannon and Circuit Design

On virtually the same day in 1847, two major new works on logic were published by prominent British mathematicians: Formal Logic by Augustus De Morgan (1806–1871) and The Mathematical Analysis of Logic by George Boole (1815–1864). Both authors sought to stretch the boundaries of traditional logic by developing a general method for representing and manipulating logically valid inferences or, as DeMorgan explained in an 1847 letter to Boole, to develop ‘mechanical modes of making transitions, with a notation which represents our head work’ [18, p. 25 ]. In contrast to De Morgan, however, Boole took the significant step of explicitly adopting algebraic methods for this purpose. As De Morgan himself later proclaimed, “Mr. Boole’s generalization of the forms of logic is by far the boldest and most original . . . ” (as quoted in [13, p. 174]). Boole further developed his bold and original approach to logic in his 1854 publication An Investigation of the Laws of Thought1. In this work, Boole developed a system of symbols (×,+) representing operations on classes (or sets) which were symbolically represented by letters. In essence, his logical multiplication xy corresponded to today’s operation of set intersection, and his logical addition x + y to today’s operation of set union.2 Using these definitions, Boole then developed the laws of this ‘Algebra of Logic,’ many of which also held true in ‘standard algebra’. Other laws, however, differed substantially from those of standard algebra, such as the Idempotent Law3: x2 = x. As noted by Boole, the Idempotent Law holds in standard algebra only when x = 0 or x = 1. He further commented [4, p. 47] that for