|
О свойствах булевых функций с экстремальным числом простых импликант
И. П. Чухров Институт автоматизации проектирования РАН, ул. 2-я Брестская, 19/18, 123056, Москва, Россия
Аннотация:
Известная нижняя оценка максимального числа простых импликант (максимальных граней) булевой функции отличается от верхней оценки в $O(\sqrt{n})$ раз и асимптотически достигается на симметричной поясковой функции. Для изучения свойств экстремальных функций определены подмножества функций, которые имеют минимальные и максимальные вершины максимальных граней в поясах $n/3\pm {{r}_{n}}$ и $2n/3\pm {{r}_{n}}$ соответственно. При этом доля числа вершин в каждом слое не меньше ${{\varepsilon}_{n}}$ и для любой такой вершины доля числа максимальных граней от максимального возможного числа не меньше ${{\varepsilon}_{n}}.$ Для параметров ${{\varepsilon}_{n}}$ и ${{r}_{n}}$ получены условия, при которых число простых импликант функции из такого подмножества равно асимптотически или по порядку роста максимальному значению. Библиогр. 10.
Ключевые слова:
булева функция, простая импликанта, максимальная грань, число простых импликант, асимптотика, порядок роста.
Статья поступила: 08.09.2021 Переработанный вариант: 08.09.2021 Принята к публикации: 17.11.2021
Образец цитирования:
И. П. Чухров, “О свойствах булевых функций с экстремальным числом простых импликант”, Дискретн. анализ и исслед. опер., 29:1 (2022), 74–93
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/da1294 https://www.mathnet.ru/rus/da/v29/i1/p74
|
|