An application of linear programming to the minimization of Boolean functions

Abstract

A method is described for converting a boolean expression 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 number 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 restrictions Σjaijxj ≥ 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 advantageously reduced in size prior to the integer programming. This reduced matrix is obtainable fairly directly 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.