On the Threshold Order of a Boolean Function
- 1 June 1966
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Electronic Computers
- Vol. EC-15 (3) , 369-372
- https://doi.org/10.1109/PGEC.1966.264495
Abstract
The notion of a threshold function is generalized to a Boolean function of threshold order r. Two characterizations of a Boolean function of threshold order r are presented, which are generalizations of the results of Kaplan and Winder and of Chow, for the case r = 1. Kaplan and Winder's characterization of a threshold function by means of Chebyshev approximation is generalized to a Boolean function of threshold order r. This results in classifying any Boolean function as a threshold function of some order r less than or equal to the number of variables. Chow's theorem on the ``equivalence'' between threshold functions and statistical recognition with independent distributions is generalized to the case of a Boolean function of threshold order r and of statistical recognition with a certain kind of dependence, called dependence of order r.Keywords
This publication has 6 references indexed in Scilit:
- Chebyshev Approximation and Threshold FunctionsIEEE Transactions on Electronic Computers, 1965
- Statistical Independence and Threshold FunctionsIEEE Transactions on Electronic Computers, 1965
- A Recognition Method Using Neighbor DependenceIRE Transactions on Electronic Computers, 1962
- Orthogonal Functions for the Logical Design of Switching CircuitsIRE Transactions on Electronic Computers, 1961
- On the classification of Boolean functionsIRE Transactions on Information Theory, 1959
- An optimum character recognition system using decision functionsIRE Transactions on Electronic Computers, 1957