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

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

Глава 1. Операторные преобразования булевых функций 22 '

§ 1. Специальная операторная форма булевых функций

§ 2. Операторные преобразования булевых функций

§ 3. Инварианты операторных преобразований

Глава 2. Преобразования операторных форм булевых функций с произведением в качестве базисной функции

§ 4. Представление Б-преобразований матрицами

§ 5. Число Б-классов булевых функций

§ 6. Асимптотическая оценка числа ЭР-классов

§ 7. Верхняя оценка сложности полиномиальных представлений

одного операторного класса

Глава 3. Алгоритмы поиска минимальных представлений булевых функций в классе ПНФ

§ 8. Алгоритм минимизации булевых функций шести переменных
§ 9. Генетический алгоритм минимизации тотальных булевых
функций
§ 10. Генетический алгоритм минимизации частично заданных
булевых функций
Заключение
Список литературы

Булевы функции получили свое название в честь английского математика Джорджа Буля, который в своей монографии сформулировал алгебраическую систему логики. Тем не менее, современное понятие булевой алгебры восходит к работам Джевонса и Пирса второй половины XIX века.
Первоначально булевы функции рассматривались как логические формулы и явились действенным средством решения комбинаторных логических задач. Поэтому до середины XX века интерес к булевым функциям носил преимущественно теоретический характер. Однако в 1938 г. Клод Шеннон показал [63], как релейные схемы могут быть промоделированы с помощью булевых функций. В настоящее время булевы функции применяются при логическом проектировании цифровой и микропроцессорной техники, в теории кодирования и криптографии, а также в математическом моделировании.
Еще в XIX веке стали изучать группу преобразований булевых функций, состоящую из операций двух видов: перестановок переменных и замены переменных их отрицаниями. Такую группу называют группой преобразований однотипности или группой Джевонса, а классы эквивалентности по группе Джевонса — типами булевых функций. Джевонс изучал типы булевых функций применительно к проблемам индуктивной логики. В качестве переменных выступали классы (понятия), а сами функции показывали объемные связи этих классов. Поскольку булевы функции одного типа совпадают с точностью до переименования переменных, то множество типов булевых функций п переменных характеризует многообразие законов взаимосвязи п понятий. Джевонс построил [13] таблицы типов для п = 2 и п = 3.
В дальнейшем типы булевых функций исследовались в работах Клиффорда [32], Шредера [62], Пойа [53], Поварова [22] и др.

В настоящее время задача построения классификаций булевых функций по различным группам преобразований имеет приложения в логическом синтезе, теории кодирования и других областях [19, 22].
Во многих классах схем однотипные булевы функции реализуются физически одинаковыми схемами, а инвариантность булевых функций относительно различных преобразований существенно упрощает синтез соответствующих схем. В Гарвардском каталоге [69] приведена таблица типов булевых функций четырех переменных и их реализаций электронными схемами. В [21] построены контактные реализации этих функций. При п > 4 использование для классификации преобразований однотипности нецелесообразно, так как число классов становится велико.
Кроме преобразований однотипности хорошо исследованными являются линейные и аффинные преобразования [24, 25, 26].
При п = 5 первая классификация была получена для группы аффинных преобразований с точностью до инвертирования функций в работе [30]. В этой же работе приведена система инвариантов, позволяющая различить почти все прототипы функций пяти переменных (классы эквивалентности но аффинной группе с точностью до линейной функции). Затем в работе [24] была построена полная классификация по аффинной группе для функций 5 переменных.
Для 6 переменных известны две классификации [26]: по группам Ьз и Аз. Для большего числа переменных задача построения полной классификации обычно не ставится, так как если мощность группы невелика, то получается большое число классов. Если же увеличивать группу преобразований, то классификация становится бедной и содержит малое число классов больших размеров.
Поэтому классификация строится для некоторого подмножества функций п переменных. В случае линейной и аффинной групп удобным является ограничение степени нелинейности функций. Классификация квадратичных форм получена в [34]. В [26] приведена классификация однородных кубических форм относительно группы аффинных преобразований при 6 < п < 8.

приводится к следующему виду:
(ЇМ®Л)0ІІП1
(0 |[п-1)
(0 |[п-1]
А Є І^-Ч А
А ][п—1]
= (М® А)ф1К
С использованием леммы 2 получаем, что • • • фп) =
&(г(<Р1)(р2...<Рп)-
В итоге для любого ц> € .?! имеет место равенство:
&{Ч>ЧЪ • • • <Рп) = &{г{(р0^2 . . . 4>п)-Используем лемму 7:
зЦ<рцр2 ...Уп) = ^(¥>2 ■ ■ ■ Ч>пГ{Ч>)).
Далее по индукции получаем цепочку равенств: аЬ{ч>ч>2 ...<рп)= ^((р2... <рпг(<р 1))
= ЗЦ(Р2<РЗ ■ ■ ■ фпГЫ) = 3%3 ■ • • ^пГ{(р1)г(^р2)) = ■ . •
= ... г((рп-0) = ... г(¥>„)).
Окончательное равенство принимает вид:
■■■<Рп) = ^№1) • • -г{(рп)).

Из леммы Бернсайда [27] и лемм 2-8 вытекает следующая теорема.
Теорема 4. Число 3-классов К${п) булевых функций п переменных выражается формулой

**<п) = & Е2т°п (<4"
1)2"
г,(2т+2(-1)т)
+ 2‘
|*(2т+2(-1)т)

► Возьмем преобразование