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


 Англоязычная версия: USSR Computational Mathematics and Mathematical Physics, 1983, 23:3, 155–156

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


© МИАН, 2024