Bounds on the Number of Threshold Functions
- 1 June 1966
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Electronic Computers
- Vol. EC-15 (3) , 368-369
- https://doi.org/10.1109/pgec.1966.264494
Abstract
It has been conjectured [1] that the number Rn of threshold functions of n arguments has the limiting form: Limn→∞ log2 Rn/n2 = const. Bounds previously obtained [2], [3] show that such a constant would have to lie between ⅓ and one. In the present note this constant is shown to have a lower bound of ½.1 The result is extended to the number Rnm of threshold functions defined on m minterms of n arguments and suggests the more general form in the limit of large n, m/n. {logm/n Rnm/n} = const. with the same limits for the constant, providing that the minterms are spread out in a certain sense.Keywords
This publication has 3 references indexed in Scilit:
- Bounds on Threshold Gate RealizabilityIEEE Transactions on Electronic Computers, 1963
- Linear Decision Functions, with Application to Pattern RecognitionProceedings of the IRE, 1962
- Truth functions realizable by single threshold organsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1961