The Generation of Minimal Threshold Nets by an Integer Program

This paper deals with the problem of generating a combinatorial network of threshold gates capable of evaluating a partially specified Boolean function. With the additional restriction that the network is to be cycle-free, the procedure described is designed to generate a network of minimum complexity in the sense that it is comprised of the smallest possible number of threshold elements. The essential result is a demonstration of the fact that the question of whether or not parameters exist such that a network of given complexity is capable of evaluating a given Boolean function is equivalent to the feasibility question for an associated integer program. In the case of feasibility the solution to the integer program contains the design of a minimum network realizing the given function.