An application of linear programming to the minimization of boolean functions

Abstract

A method is described for converting a boolean exression to a disjunctive normal equivalent (two level OR-AND circuit) which is minimal under some criterion presented in advance. as for example, the number of clauses or the number of literals (equivalently, the nuber of OR's or the number of OR's and AND's together). The method employs the integer linear programming algorithm developed by R. E. Gomory and takes advantage of a new technique for obtaining the required integer matrix. From a boolean function φ, A = ||aij|| is defined by setting aij = 1 if prime implicant j covers canonical term i and aij = 0 otherwise. Then, for example, minimization of the expression: Σjxj, subject to the restrictions Σj aij xj ≥ 1 and xj a non-negative integer, is equivalent to obtaining a normal form for φ with a minimal number of clauses. In practice A can be advantageousl reduced in size prior to the integer programming. This reduced matrix is obtainable fairly directy from an expression for φ by a succession of simple operations. The method has been programmed for the IBM 704 and tested on several hundred problems. In speed and range of problems solvable, it compares favorably with minimization techniques presently in use.