Том 28, номер 1, 2021 г., Стр. 68-96

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

Аннотация:
Известная нижняя оценка максимального числа простых импликант булевой функции (длины сокращённой ДНФ) отличается от верхней оценки в $\Theta(\sqrt{n})$ раз и асимптотически достигается на симметричной поясковой функции, имеющей ширину пояса $n/3$. Для изучения свойств связных булевых функций с большим числом простых импликант вводится понятие локально экстремальной в некоторой окрестности функции по числу простых импликант. Получены оценки изменения числа простых импликант при изменении значений поясковой функции в некоторой $d$-окрестности. Доказано, что поясковая функция, для которой ширина пояса и номер нижнего слоя единичных вершин асимптотически равны $n/3$, локально экстремальна в некоторой окрестности для $d \le \Theta(n)$, а для $d \ge 2^{\Theta(n)}$ — нет. Аналогичное утверждение справедливо для функций, имеющих простые импликанты разного ранга. Свойство локальной экстремальности сохраняется после применения к булевой функции преобразования, сохраняющего расстояние между вершинами единичного куба.
Библиогр. 10.

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

DOI: 10.33048/daio.2021.28.699

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

Статья поступила 23 августа 2020 г.
Принята к публикации 28 октября 2020 г

Литература

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

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

[3] Гаджиев М. М. Максимальная длина сокращённой д. н. ф. для булевых функций пяти и шести переменных // Дискретный анализ. Вып. 18. Новосибирск: Ин-т математики СО АН СССР, 1971. С. 3–24.

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

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

[6] Андреев А. Е. К проблеме минимизации дизъюнктивных нормальных форм // Докл. АН СССР. 1984. Т. 274, № 2. С. 265–269.

[7] Kettle N., King A., Strzemecki T. Widening ROBDDs with prime implicants // Tools and Algorithms for the Construction and Analysis of Systems. Proc. 12th Int. Conf. (Vienna, Austria, Mar. 25–Apr. 2, 2006) Heidelberg: Springer, 2006. P. 105–119. (Lect. Notes Comput. Sci.; Vol. 3920).

[8] Sloan R. H., Sz¨orenyi B., Turan G. On $k$-term DNF with the largest number of prime implicants // SIAM J. Discrete Math. 2008. Vol. 21, No. 4. P. 987–998.

[9] Talebanfard N. On the structure and the number of prime implicants of 2-CNFs // Discrete Appl. Math. 2016. Vol. 200. P. 1–4.

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