Том 29, номер 1, 2022 г., Стр. 74-93

УДК 519.71
Чухров И. П.
О свойствах булевых функций с экстремальным числом простых импликант

Аннотация:
Известная нижняя оценка максимального числа простых импликант (максимальных граней) булевой функции отличается от верхней оценки в $O(\surd n)$ раз и асимптотически достигается на симметричной поясковой функции. Для изучения свойств экстремальных функций определены подмножества функций, которые имеют минимальные и максимальные вершины максимальных граней в поясах $n/3 \pm r_n$ и $2n/3 \pm r_n$ соответственно. При этом доля числа вершин в каждом слое не меньше $\epsilon_n$ и для любой такой вершины доля числа максимальных граней от максимального возможного числа не меньше $\epsilon_n$. Для параметров $\epsilon_n$ и $r_n$ получены условия, при которых число простых импликант функции из такого подмножества равно асимптотически или по порядку роста максимальному значению.
Библиогр. 10.

Ключевые слова: булева функция, простая импликанта, максимальная грань, число простых импликант, асимптотика, порядок роста.

DOI: 10.33048/daio.2022.29.725

Чухров Игорь Петрович ¹
1. Институт автоматизации проектирования РАН,
ул. 2-я Брестская, 19/18, 123056, Москва, Россия
е-mail: chip@icad.org.ru

Статья поступила 8 сентября 2021 г.
После доработки — 8 сентября 2021 г.
Принята к публикации 17 ноября 2021 г.

Литература

[1] Васильев Ю. Л., Глаголев В. В. Метрические свойства дизъюнктивных нормальных форм // Дискретная математика и математические вопросы кибернетики. Т. 1. М.: Наука, 1974. С. 99–148.

[2] Сапоженко А. А., Чухров И. П. Минимизация булевых функций в классе дизъюнктивных нормальных форм // Итоги науки и техники. Сер. Теория вероятностей.Мат. статистика. Теор. кибернетика. 1987. Т. 25. С. 68–116.

[3] Викулин А. П. Оценка числа конъюнкций в сокращённой д. н.ф. // Пробл. кибернетики. 1974. № 29. С. 151–166.

[4] Chandra A. K., Markovsky G. On the number of prime implicants // Discrete Math. 1978. Vol. 24. P. 7–11.

[5] Чухров И. П. Связные булевы функции с локально экстремальным числом простых импликант // Дискрет. анализ и исследование операций. 2021. Т. 28, № 1. С. 68–94.

[6] Гаврилов Г. П., Сапоженко А. А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2005. 416 с.

[7] Боровков А. А. Теория вероятностей. М.: Эдиториал УРСС, 1999. 472 с.
[8] Чухров И. П. О максимальной мощности тени антицепи // Дискрет. математика. 1989. Т. 1, № 4. С. 78–85.

[9] Алон Н., Спенсер Дж. Вероятностный метод. М.: Бином. Лаборатория знаний, 2007. 320 с.

[10] Косточка А. В. Верхняя оценка мощности границы антицепи в $n$-мерном кубе // Дискрет. математика. 1989. Т. 1, № 3. С. 53–61.