An Algorithm for Determining Minimal Representations of a Logic Function

For each logic function, or Boolean algebraic expression, there corresponds an appropriate computer circuit. However, the minimization of the appearances of the Boolean variables does not necessarily lead to the most economical circuit. A general approach to the problem therefore requires the development of techniques for the simple and rapid generation of a variety of near-minimal forms. This paper describes such a method for constructing the minimal representations of a logic function given as a truthtable or in one of its canonical forms. The minimal representations achieved are either sums of products, or products of sums, such that no term contains superfluous variables and such that no term is superfluous. The utility of the method lies in the conciseness of notation, which permits the handling of a large number of variables and simplifies the process for machine computation.