Bounds on the Number of Threshold Functions
David R. Smith · IEEE Transactions on Electronic Computers · 1966
It has been conjectured [1] that the number Rnof threshold functions of n arguments has the limiting form: Limn→∞log2Rn/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 ½.1The result is extended to the number Rnmof threshold functions defined on m minterms of n arguments and suggests the more general form in the limit of large n, m/n. {logm/nRnm/n} = const. with the same limits for the constant, providing that the minterms are spread out in a certain sense.