Введение к работе
Актуальность темы. Булевы функции получили свое название в честь английского математика Джорджа Буля, который в своей монографии сформулировал алгебраическую систему логики Тем не менее, современное понятие булевой алгебры восходит к работам Джевонса и Пирса второй половины XIX века
Первоначально булевы функции рассматривались как логические формулы и явились действенным средством решения комбинаторных логических задач. Поэтому до середины XX века интерес к булевым функциям носил преимущественно теоретический характер Однако в 1938 г Клод Шеннон показал [10], как релейные схемы могут быть промоделированы с помощью булевых функций. В настоящее время булевы функции применяются при логическом проектировании цифровой и микропроцессорной техники, в теории кодирования и криптографии, а также в математическом моделировании
Еще в XIX веке стали изучать группу преобразований булевых функций, состоящую из операций двух видов перестановок переменных и замены переменных их отрицаниями Такую группу называют группой преобразований однотипности или группой Джевонса, а классы эквивалентности по группе Джевонса — типами булевых функций Джевонс изучал типы булевых функций применительно к проблемам индуктивной логики В качестве переменных выступали классы (понятия), а сами функции показывали объемные связи этих классов
В настоящее время задача построения классификаций булевых функций по различным группам преобразований имеет приложения в логическом синтезе, теории кодирования и других областях [4]
Во многих классах схем однотипные булевы функции реализуются физически одинаковыми схемами, а инвариантность булевых функций относительно различных преобразований существенно упрощает синтез соответствующих схем
Построение различных классификаций также интересно в связи с применением к следующим задачам вычисление возможных характеристик функций, выбор функций, обладающих наилучшими для конкретной ситуации параметрами, определение полных систем инвариантов функций для заданной группы преобразований
Кроме задачи построения полной классификации, состоящей в нахождении всех классов эквивалентности, часто решают задачу пе-
речисления
Задача перечисления заключается в определении числа классов эквивалентности без нахождения самих представителей Впервые задачу подсчета числа классов эквивалентности булевых функций поставил Пойа [7], он же вычислил значения при малых п для группы перестановок переменных и группы Джевонса Подход, разработанный Пойа, основывался на связи задачи перечисления с теорией представлений групп В [11] были найдены явные формулы для вычисления числа классов для этих групп в общем случае
Пойа разработал общий метод нахождения числа классов для случая, когда группа является подгруппой группы подстановок на множестве значений переменных В дальнейшем теория перечисления Пойа была обобщена в работах Де Брейна [2]
Каждая булева функция п переменных реализуется 23 ~2 различными полиномиальными представлениями Одним из критериев оценки этих представлений является их сложность Чем меньше сложность полинома, тем он предпочтительнее, так как меньшая сложность дает меньшие размеры и большую скорость работы электронных схем, построенных с использованием данного полинома Появление интереса непосредственно к полиномиальным представлениям булевых функций, как объектам исследования, связано с практическими приложениями после того, как в конце прошлого века в цифровой технике стали активно использоваться элементы типа "сложение по модулю 2" Тенденция развития электроники в направлении увеличения быстродействия, уменьшения энергоемкости и стоимости привела к необходимости повышения эффективности цифровой техники во время проектирования — на уровне представления схем булевыми функциями
Поэтому возникла задача минимизации — нахождения формул наименьшей сложности, представляющих данную булеву функцию Использование минимальных формул позволяет повысить эффективность электронных схем, реализующих данные функции, — уменьшить их размер и увеличить скорость работы без применения новых технологий При этом для большинства функций полиномиальные нормальные формы по сравнению с другими нормальными формами — дизъюнктивными и конъюнктивными — имеют более компактный размер [9] и обладают лучшей тестируемостью [5]
Исследование полиномиальных представлений ведется весьма интенсивно Рассматривается широкий спектр вопросов от исследо-
ваний сложности и нахождения минимальных форм до алгоритмов прямой реализации на микросхемах специального типа — программируемых логических матрицах [8]
В ряде работ [1, 3] был предложен и разработан операторный подход к исследованию булевых функций Переход к операторным формам позволил упростить работу с полиномиальными формами, а также обобщить и структурировать классы полиномиальных нормальных форм
Многие алгоритмы минимизации основаны на переборе функций меньшей размерности В этом случае большую роль играют группы преобразований, сохраняющих сложность функций, так как вместо всех функций обычно можно перебрать только представителей классов эквивалентности
Цели работы:
получить оценки на число классов относительно группы операторных преобразований булевых функций,
найти инварианты операторных преобразований,
построить алгоритмы минимизации булевых функций с использованием операторной эквивалентности
Основные результаты и научная новизна. Основные научные результаты диссертации следующие
получена замкнутая формула для числа S-классов булевых функций и асимптотическая оценка числа SP-классов булевых функций,
найдена полная система инвариантов для функций 5 переменных по SP-преобразованиям,
разработаны и реализованы генетические алгоритмы минимизации полиномиальных представлений тотальных и частично заданных булевых функций
Основные результаты диссертации являются новыми
Теоретическая и практическая ценность. Полученные результаты имеют теоретическое значение и могут найти применение в исследованиях по классификации булевых функций Результаты могут быть использованы при проектировании дискретных преобразователей информации.
Методы исследований. В диссертации используются методы линейной алгебры, комбинаторики и теории булевых функций
Апробация работы. Результаты диссертации докладывались на следующих конференциях международная конференция "Алгебра, логика и кибернетика"(Иркутск, 2004 г), VI международная конференция "Дискретные модели в теории управляющих систем" (Москва, 2004 г), V школа-семинар "Распределенные и кластерные вычисления" (Красноярск, 2005 г.); VII международная конференция "Дискретные модели в теории управляющих систем "(Москва, 2006 г); XVI международная школа-семинар "Синтез и сложность управляющих систем"(Санкт-Петербург, 2006 г); российская школа-семинар "Синтаксис и семантика логических систем "(Иркутск, 2006 г), V Сибирская научная школа-семинар с международным участием "Компьютерная безопасность и криптография" (Томск, 2006 г), межвузовская зональная конференция "Математика и проблемы ее преподавания в вузе" (Иркутск, 2007 г), международный российско-китайский семинар "Алгебра и логика "(Иркутск, 2007 г), международная конференция "Алгебра и ее приложения"(Красноярск, 2007 г)
Публикации. По теме диссертации опубликовано 16 научных работ [12]-[27], отражающих основное содержание диссертации, в том числе три работы в журналах, рекомендованных ВАК РФ
Структура и объем работы. Диссертация изложена на 90 страницах и состоит из введения, трех глав, заключения и списка литературы, содержащего 85 наименований, включая работы диссертанта
