Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 23 (1983) no. 3, pp. 754-756
Citer cet article
Yu. A. Zuev; V. N. Trishin. Lower bound for the number of inequalities representing a monotone Boolean function of $n$ variables. Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 23 (1983) no. 3, pp. 754-756. http://geodesic.mathdoc.fr/item/ZVMMF_1983_23_3_a25/
@article{ZVMMF_1983_23_3_a25,
author = {Yu. A. Zuev and V. N. Trishin},
title = {Lower bound for the number of inequalities representing a monotone {Boolean} function of $n$~variables},
journal = {\v{Z}urnal vy\v{c}islitelʹnoj matematiki i matemati\v{c}eskoj fiziki},
pages = {754--756},
year = {1983},
volume = {23},
number = {3},
language = {ru},
url = {http://geodesic.mathdoc.fr/item/ZVMMF_1983_23_3_a25/}
}
TY - JOUR
AU - Yu. A. Zuev
AU - V. N. Trishin
TI - Lower bound for the number of inequalities representing a monotone Boolean function of $n$ variables
JO - Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
PY - 1983
SP - 754
EP - 756
VL - 23
IS - 3
UR - http://geodesic.mathdoc.fr/item/ZVMMF_1983_23_3_a25/
LA - ru
ID - ZVMMF_1983_23_3_a25
ER -
%0 Journal Article
%A Yu. A. Zuev
%A V. N. Trishin
%T Lower bound for the number of inequalities representing a monotone Boolean function of $n$ variables
%J Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
%D 1983
%P 754-756
%V 23
%N 3
%U http://geodesic.mathdoc.fr/item/ZVMMF_1983_23_3_a25/
%G ru
%F ZVMMF_1983_23_3_a25
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.
