RUS  ENG
Полная версия
ЖУРНАЛЫ // Дискретная математика // Архив

Дискрет. матем., 1993, том 5, выпуск 3, страницы 40–43 (Mi dm689)

Эта публикация цитируется в 4 статьях

О числе пороговых функций

А. А. Ирматов


Аннотация: Булевская функция называется пороговой, если ее область истинности определяется частью $n$-мерного куба, отсекаемой некоторой гиперплоскостью. Число пороговых функций от $n$ переменных $P(2,n)$ оценено в работах [1, 2, 3]. Особую трудность вызывает получение нижних оценок. Ю. А. Зуев в работе [3], используя технический результат работы [4], установил, что для достаточно больших $n$ выполняется следующее неравенство
$$ P(2,n)>2^{n^2(1-10/\ln n)}. $$
В настоящей работе предлагается доказательство уточняющее нижнюю оценку, а именно, для достаточно больших $n$ имеет место следующее неравенство
$$ P(2,n)>2^{n^2(1-7/\ln n)}P\biggl(2,\biggl[\frac{7(n-1)\ln2}{\ln(n-1)}\biggr]\biggr). $$


Статья поступила: 02.07.1992


 Англоязычная версия: Discrete Mathematics and Applications, 1993, 3:4, 429–432

Реферативные базы данных:


© МИАН, 2024