|
This article is cited in 4 scientific papers (total in 4 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)>2^{n^2(1-10/\ln n)}.
$$
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)>2^{n^2(1-7/\ln n)}P\biggl(2,\biggl[\frac{7(n-1)\ln 2}{\ln(n-1)}\biggr]\biggr).
$$
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
|
|