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

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

Оглавление
Введение
Глава I. Основные определения и краткий обзор результатов
§1. Основные определения и обозначения
§2. Обзор результатов по полиномиальным представлениям булевых функций
Глава II. Операторы в булевых функциях и их свойства
§3. Свойства операторов и операторных пучков
§4. Два критерия существования базисных пучков
§5. Специальные классы базисных пучков
Глава III. Разложения булевых функций по операторным
пучкам и невырожденным системам функций
§6. Разложения булевых функций по собственным образам операторного пучка
§7. Операторные разложения по образам нечетных
функций
§8. Бинарные термы в разложениях
§9. Разложения по невырожденным системам функций
Глава IV. Операторные канонические формы
§10. Общий вид операторных полиномиальных форм
§11. Классы операторных форм
§12. Иерархия классов операторных форм
§13. Канонические формы с операторами других типов

Глава V. Сложность представлений и методы нахождения операторных полиномиальных форм
§14. Сложность операторных форм
§15. Методы нахождения полиномиальных представлений
§16. Компьютерные реализации алгоритмов
Заключение
Список литературы

Введение
В конце XIX - начале XX веков исследования по булевым функциям были связаны с применением к логике и основаниям математики. При этом булевы функции рассматривались как логические формулы над связками конъюнкции, дизъюнкции, импликации, отрицания и эквивалентности. Для становления исследований по булевым функциям как самостоятельной теории существенным явилось открытие новых приложений к описанию релейно-контактных схем и помехоустойчивому кодированию.
В настоящее время булевы функции используются при логическом проектировании дискретных преобразователей информации (синтез, диагностика схем различного рода), в теории кодирования и криптографии, в теоретическом программировании и математическом моделировании.
В теории булевых функций исследования, связанные с представлениями функций различными формами, интенсивно развиваются. Имеется большое количество работ по этому направлению, в частности [6, 20, 27, 28, 29, 47, 48, 52, 101, 109].
Первые результаты по представлениям булевых функций в виде полиномов были опубликованы в 1928 году в работах И.И.Жегалкина [17, 18]. Эти исследования были связаны с решением проблемы арифметизации логических рассуждений и не получили распространения в кругах, далеких от логики. И только с развитием теории кодирования в 50-е годы были
w{ t) = hase. Тогда по определению оператора:
t = as(t'f(x)),
где (t/) = к — 1, (t')s = e и (t/),- = ti для остальных і ф s.
По индукции имеем:
a5(t7(5)) = а5(а!д(у) hh{z))
= as(a'-д{у)) b~zh(z) = щд(у) h~zh{z).
Случай bÆ ф е. очевидно, полностью аналогичен рассмотренному.

Свойство операторов, сформулированное в предложении
2.3, дает возможность разбивать в некотором смысле сложные операторы на более простые.
Предложение 2.4. Для любых операторов а и Ь, для любых функций f{x) и д(х) имеет место равенство: dx (af{x) Ъд(х) 0 ад(х) b/(!)) = 0.
Доказательсво будем вести индукцией по k = w(а) + гу(Ь). Базис индукции при к = 0:
d* (f(x) д(х) 0 g (F) f(x)) = Ç (/( f) g(f) 0 #(r) /(r)) = 0,

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