|
Дискретная математика, 1993, том 5, выпуск 3, страницы 40–43
(Mi dm689)
|
|
|
|
Эта публикация цитируется в 4 научных статьях (всего в 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
Образец цитирования:
А. А. Ирматов, “О числе пороговых функций”, Дискрет. матем., 5:3 (1993), 40–43; Discrete Math. Appl., 3:4 (1993), 429–432
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/dm689 https://www.mathnet.ru/rus/dm/v5/i3/p40
|
Статистика просмотров: |
Страница аннотации: | 691 | PDF полного текста: | 254 | Первая страница: | 2 |
|