A Threshold Gate Feed-Forward Switching Net Algorithm

A general algorithm is presented for the efficient computation of feed-forward nets of general threshold gates which realize given bi-valued switching functions. A simplified version of the algorithm is presented for the case of symmetric threshold nets which realize symmetric switching functions. These algorithms produce near-minimal gate nets, and the results of a digital computer program for the general algorithm are presented to illustrate the degree of efficiency and minimality obtained in practice. Both algorithms are proved to give a minimal one-gate net if one exists for a given switching function; a necessary criterion is given for the symmetric algorithm to produce a minimal two-gate net if one exists; and two-gate minimality is also demonstrated for the general algorithm, for a certain class of two-gate switching functions. The case of partially defined switching functions is also treated