Lower Bounds of the Number of Threshold Functions and a Maximum Weight

Abstract

A lower bound on the number of threshold functions and a lower bound on the maximum of minimum weights of a threshold element are derived from a recursively constructed family of threshold elements. All threshold functions of n variables are difficult to construct for a general value of n, but it is shown that a large number of them can be constructed recursively from threshold functions of fewer variables. Schemes of such generation and related proper ties are discussed. Threshold functions generated in this way are so numerous that they constitute a constructive proof of a good lower bound on the number of threshold functions. By a similar procedure, we can derive a lower bound on the maximum of minimum weights of a threshold element. In this paper, discussion is limited to self-dual threshold functions, but this does not sacrifice generality, because any threshold function can be derived from a self-dual threshold function by assigning 1 or 0 to a certain variable.