Representation of Switching Circuits by Binary-Decision Programs

In his 1938 paper,1 Shannon showed how relay switching circuits can be represented by the language of symbolic logic and designed and manipulated according to the rules of Boolean algebra. This far-reaching step provided an algebraic language for a systematic treatment of switching and logical design problems and provided a root system from which new art can grow and flourish. We may want to know, however, if there might not be other ways of representing switching functions and circuits, and to compare such representations with the algebraic representation of Shannon. In this paper we will give a new representation of switching circuits, and will call this representation a "binary-decision program." Binary-decision programs, as the reader will see, are not algebraic in nature. They are, therefore, less easily manipulated. A switching circuit may be simplified not by simplifying its binary-decision program, but by essentially finding for it a better binary-decision program. A good binary-decision program generally means one which is well-knit and makes efficient use of subroutines; it is good in the sense then that a computer program is good. Binary-decision programs do not seek out series-parallel circuits, but are more suited for representing circuits with a large number of transfers. In these respects, binary decision programs therefore differ very greatly from the usual Boolean representation. 985