Heuristic switching expression simplification
Melvin A. Breuer · 1968
One very profitable application of computer aided design is in the design and construction of digitial computers. 1 A classical problem in computer design is that associated with the simplification of Boolean switching expressions. Numerous algorithms exist for solving this problem, such as the Karnaugh or Veitch graph method, the Quine—McCluskey technique, the cubical complex approach of Roth,2 or the recently published procedure of Svoboda.3 In general, the classical minimization procedure consists first of generating all the canonical terms of a function, secondly of generating all of the prime implicants, and finally of selecting a minimal cover which consists of some subset of the set of prime implicants. For some techniques, these first two steps can be partially eliminated as illustrated by repeatedly applying the #-algorithm of Roth. The resulting solution usually represents a minimal diode or minimal gate two-level AND-OR or NAND representation of the given function.