О свойствах булевых функций с экстремальным числом простых импликант

О свойствах булевых функций с экстремальным числом простых импликант

Чухров И. П.
Дискретный анализ и исследование операций, 29, 1, 74-93 (2022)
Скачать статью

УДК 519.71 
DOI: 10.33048/daio.2022.29.725

Аннотация:

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

Литература:
  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.
Чухров Игорь Петрович
  1. Институт автоматизации проектирования РАН, 
    ул. 2-я Брестская, 19/18, 123056, Москва, Россия

E-mail: chip@icad.org.ru

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

Abstract:

The known lower bound for the maximum number of prime implicants (of maximal faces) of a Boolean function differs from the upper bound by $O(\surd n)$ times and is asymptotically attained on a symmetric belt function. To study the properties of extremal functions, subsets of functions are defined that have the minimum and maximum vertices of the maximum faces in the belts $n/3 \pm r_n$ and $2n/3 \pm r_n$, respectively. In this case, the fraction of the number of vertices in each layer is not less than $\epsilon_n$ and for any such vertex the fraction of the number of maximum faces of the maximum possible number is not less than $\epsilon_n$. Conditions are obtained for $\epsilon_n$ and $r_n$ under which a Boolean function from such a subset has the number of prime implicants equal to the maximum value asymptotically or in order of growth of the maximum value. 
Bibliogr. 10.

References:
  1. Yu. L. Vasil’ev and V. V. Glagolev, Metric properties of disjunctive normal forms, Discrete Mathematics and Mathematical Problems of Cybernetics, (Nauka, Moscow, 1974), pp. 99–148 [Russian].
     
  2. A. A. Sapozhenko and I. P. Chukhrov, Boolean function minimization in the class of disjunctive normal forms, Itogi Nauki Tekh., Ser. Teor. Veroyatnost., Mat. Statist., Teor. Kibern. 25, 68–116 (1987) [Russian] [J. Sov. Math. 46 (4), 2021–2052 (1989)].
     
  3. A. P. Vikulin, Estimation of the number of conjunctions in the complete DNF, Problems of Cybernetics, No. 29 (Nauka, Moscow, 1974), pp. 151–166 [Russian].
     
  4. A. K. Chandra and G. Markovsky, On the number of prime implicants, Discrete Math. 24, 7–11 (1978).
     
  5. I. P. Chukhrov, Connected boolean functions with a locally extremal number of prime implicants, Diskretn. Anal. Issled. Oper. 28 (1), 68–94 (2021) [Russian] J. Appl. Ind. Math. 15 (1), 17–38 (2021).
     
  6. G. P. Gavrilov and A. A. Sapozhenko, Tasks and Exercises in Discrete Mathematics, (Fizmatlit, Moscow, 2005) [Russian].
     
  7. A. A. Borovkov, Probability Theory, (Editorial URSS, Moscow, 1999) [Russian].
     
  8. I. P. Chukhrov, About the maximum cardinality of the shadow of an antichain, Diskretn. Mat. 1 (4), 78–85 (1989) [Russian].
     
  9. N. Alon and J. H. Spencer, The Probabilistic Method, (Wiley, Hoboken, NJ, 2000; BINOM. Lab. Znanii, Moscow, 2007 [Russian]).
     
  10. A. V. Kostochka, An upper bound of the cardinality of antichain boundary in the $n$-cube, Diskretn. Mat. 1 (4), 53–61 (1989) [Russian] [Discrete Math. Appl., 1 (3), 279–288 (1991)].