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


 English version:
USSR Computational Mathematics and Mathematical Physics, 1983, 23:3, 155–156

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024