RUS
ENG
Full version
JOURNALS
// Zhurnal Vychislitel'noi Matematiki i Matematicheskoi Fiziki
// Archive
Zh. Vychisl. Mat. Mat. Fiz.,
1983
Volume 23,
Number 3,
Pages
754–756
(Mi zvmmf4533)
This article is cited in
1
paper
Scientific communications
Lower bound for the number of inequalities representing a monotone Boolean function of
$n$
variables
Yu. A. Zuev
,
V. N. Trishin
Moscow
Abstract:
It is shown that there is a monotonic Boolean function whose representation by a system of linear inequalities with
$n$
Boolean variables requires not less than
$$\binom{n}{[n/2]}n^{-1}$$
inequalities.
UDC:
519.7
MSC:
94C10
Received:
24.03.1982
Revised:
24.11.1982
Fulltext:
PDF file (357 kB)
Cited by
English version:
USSR Computational Mathematics and Mathematical Physics, 1983,
23
:3,
155–156
Bibliographic databases:
©
Steklov Math. Inst. of RAS
, 2024