Minimization Over Boolean Graphs

This paper presents a systematic procedure for the design of gate-type combinational switching circuits without directed loops. Each such circuit (Boolean graph) is in correspondence with a sequence of decompositions of the Boolean function which it realizes. A general approach to functional decomposition is given and, in terms of a convenient positional representation, efficient tests for the detection of decompositions are derived. These results are employed in the development of an alphabetic search procedure for determining minimum-cost Boolean graphs which satisfy any given design specifications.