Существование и сложность представлений булевых функций формулами

• Автор: Перязев, Николай Алексеевич
• Шифр специальности: 01.01.09
• Научная степень: Докторская
• Год защиты: 1998
• Место защиты: Иркутск
• Количество страниц: 173 с.

Иркутский государственный университет
На правах рукописи
Перязев Николай Алексеевич
Существование и сложность представлений булевых функций формулами
01.01.09 - математическая кибернетика
Диссертация на соискание ученой степени доктора физико-математических наук
Иркутск
Оглавление
Введение
Глава I. Основные понятия и результаты
§1. Основные понятия и терминология теории булевых
функций
§2. Обзор результатов по формульным представлениям
булевых функций
Глава II. Бесповторные и слабоповторные булевы функции
§3. Критерии бесповтюрности булевых функций
§4. Нахождения представлений булевых функций беспо-
вторными формулами
§5. Описание слабоповторных булевых функций в бинарном базисе
Глава III. Полиномиальные разложения булевых функций
§6. Полиномиальные разложения общего вида
§7. Разложения булевых функций по образам однородных операторов
§8. Разложения булевых функций по образам неоднородных операторов
§9. Полиномиальные канонические формы булевых функций
Глава IV. Вопросы сложности представлений булевых
функций формулами
§10. Сложность представлений булевых функций формулами в немонолинейных базисах
§11. Сложность представлений булевых функций полиномиальными формами
Заключение
Список литературы
В следующей теореме показано, что функции Ьд(Вп) и Ьд(Зп) равны, а также найдена формула для их вычисления.
Теорема 16. [99, 103] Функция Шеннона для классов всех и всех симметричных функций во множестве п.к.п.ф. вычисляется так:
"о п+Г
Щвп)
Оценка из теоремы 16 распространяется и на более широкие классы полиномиальных форм.
Классы полиномиальных канонических форм, полученные применением однородных операторов с1р, рС (11 по функции многоместной конъюнкции обозначим ПР, РТ, ИТ, соответственно, Б О — объединение этих классов.
Теорема 17. [96, 110] Функция Шеннона для классов всех и всех симметричных функций во множествах ИР, РТ, ИТ, Б О полиномиальных конъюнктивных форм по однородно смешанным операторам совпадает и равна:
~2п+1
Эта теорема получена в нераздельном соавторстве с С.Ф. Винокуровым.
Существенным доводом для использования операторных полиномиальных форм является оценка сложности по функции Шеннона. Среди всех канонических форм полиномиаль-