Boolean Reasoning and Informed Search in the Minimization of Logic Circuits.

摘要

The minimization of logic circuits has been an important area of research for more than a half century. The approaches taken in this field, however, have for the most part been ad hoc. Boolean techniques have been employed to manipulate formulas, but not to perform symbolic reasoning. Boolean equations are employed principally as icons; they are never solved. The first objective of this dissertation is to apply Boolean reasoning systematically and uniformly to the minimization problem. Boolean reasoning entails the reduction of systems of Boolean equations to a single equation; the single equation is an abstraction, independent of the form of the original equations, upon which a variety of reasoning operations may be performed. The second objective is to apply informed search, which has arisen from research in Artificial Intelligence, to the minimization problem. A circuit specification is reduced to a single equivalent equation called a 1-normal form. It is shown that forming a particular solution for the equation corresponds to deriving a design.