RUS
ENG
Полная версия
ЖУРНАЛЫ
// Журнал вычислительной математики и математической физики
// Архив
Ж. вычисл. матем. и матем. физ.,
1983
, том 23,
номер 3,
страницы
754–756
(Mi zvmmf4533)
Эта публикация цитируется в
1
статье
Научные сообщения
Нижняя оценка числа неравенств, представляющих монотонную булеву функцию от
$n$
переменных
Ю. А. Зуев
,
В. Н. Тришин
Москва
Аннотация:
Показывается, что существует монотонная булева функция от
$n$
переменных, для представления которой в виде системы линейных неравенств с
$n$
булевыми переменными требуется не менее
$$\binom{n}{[n/2]}n^{-1}$$
неравенств.
УДК:
519.7
MSC:
94C10
Поступила в редакцию:
24.03.1982
Исправленный вариант:
24.11.1982
Полный текст:
PDF файл (357 kB)
Список цитирования
Англоязычная версия:
USSR Computational Mathematics and Mathematical Physics, 1983,
23
:3,
155–156
Реферативные базы данных:
©
МИАН
, 2024