|
This article is cited in 5 scientific papers (total in 5 papers)
On the number of threshold functions
A. A. Irmatov
Abstract:
A Boolean function is called a threshold function if its truth domain is a part of the n-cube cut off by some hyperplane. The number of threshold functions of n variables P(2,n) was estimated in [1, 2, 3]. Obtaining the lower bounds is a problem of special difficulty. Using a result of [4], Yu. A. Zuev showed [3] that for sufficiently large n
P(2,n)>2n2(1−10/lnn).
In the present paper a new proof which gives a more precise lower bound of P(2,n) is proposed, namely, it is proved that for sufficiently large n
P(2,n)>2n2(1−7/lnn)P(2,[7(n−1)ln2ln(n−1)]).
Received: 02.07.1992
Citation:
A. A. Irmatov, “On the number of threshold functions”, Diskr. Mat., 5:3 (1993), 40–43; Discrete Math. Appl., 3:4 (1993), 429–432
Linking options:
https://www.mathnet.ru/eng/dm689 https://www.mathnet.ru/eng/dm/v5/i3/p40
|
Statistics & downloads: |
Abstract page: | 719 | Full-text PDF : | 263 | References: | 1 | First page: | 2 |
|