Дискретный анализ и исследование операций
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Архив
Импакт-фактор
Правила для авторов

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Дискретн. анализ и исслед. опер.:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Дискретный анализ и исследование операций, 2022, том 29, выпуск 1, страницы 74–93
DOI: https://doi.org/10.33048/daio.2022.29.725
(Mi da1294)
 

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

И. П. Чухров

Институт автоматизации проектирования РАН, ул. 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
Реферативные базы данных:
Тип публикации: Статья
УДК: 519.71
Образец цитирования: И. П. Чухров, “О свойствах булевых функций с экстремальным числом простых импликант”, Дискретн. анализ и исслед. опер., 29:1 (2022), 74–93
Цитирование в формате AMSBIB
\RBibitem{Chu22}
\by И.~П.~Чухров
\paper О свойствах булевых функций с~экстремальным числом простых импликант
\jour Дискретн. анализ и исслед. опер.
\yr 2022
\vol 29
\issue 1
\pages 74--93
\mathnet{http://mi.mathnet.ru/da1294}
\crossref{https://doi.org/10.33048/daio.2022.29.725}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=4412510}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/da1294
  • https://www.mathnet.ru/rus/da/v29/i1/p74
  • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Дискретный анализ и исследование операций
     
      Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2025