Two-level threshold minimization

In view of the main objective of designing more efficient electronic computers, logical designers, in recent years, have been much interested in realization of switching functions by networks of threshold gates instead of the classical "AND" and "OR" gates. Naturally, it is desirable to obtain a most economic network which consists of the least number of threshold gates. This gives rise to the problem of finding for a given switching function f a minimal decomposition of f with linearly separable component switching functions. Because of reliability considerations, the number of inputs to a threshold device cannot be too large, Thus, it is necessary to limit the number of variables of the component functions in the decompositions of f. This leads to the constrained minimization problem stated as follows: Let t denote a given small positive integer not less than 2. For an arbitrarily given switching function f, find a decomposition of f which consists of linearly separable component switching functions of not more than t variables. In this paper, an effective and mathematically rigorous finite process is presented for solving this problem. By the aid of a reduction theorem and the consideration of the total degree of repetition of a decomposition, the problem is solved by the iterated search for simple decompositions with respect to disjunctive or nondisjunctive partitions of the variables. Details and illustrative examples will appear in book form.