The Generation of Minimal Threshold Nets by an Integer Program
- 1 June 1964
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Electronic Computers
- Vol. EC-13 (3) , 299-302
- https://doi.org/10.1109/pgec.1964.263921
Abstract
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.Keywords
This publication has 4 references indexed in Scilit:
- Linearly separable switching functionsJournal of the Franklin Institute, 1961
- Theory of majority decision elementsJournal of the Franklin Institute, 1961
- Linear-Input LogicIEEE Transactions on Electronic Computers, 1961
- Truth functions realizable by single threshold organsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1961