Операторные преобразования и минимизация полиномиальных представлений булевых функций тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

На правах рукописи Казимиров Алексей Сергеевич

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

01.01 09 — дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Красноярск — 2007

Работа выполнена на кафедре математической информатики Иркутского государственного педагогического университета

Научный руководитель:

доктор физико-математических наук, профессор Винокуров Сергей Федорович

Официальные оппоненты:

доктор физико-математических наук, профессор Нужин Яков Нифантьевич, кандидат физико-математических наук, доцент Кузнецов Александр Алексеевич

Ведущая организация:

Институт математики им С.Л Соболева СО РАН

Защита состоится 18 октября 2007 г. в 14 часов на заседании диссертационного совета К 212.099 06 в Сибирском федеральном университете по адресу 660074, г Красноярск, ул Киренского, 26

С диссертацией можно ознакомиться в библиотеке Сибирского федерального университета (г Красноярск, ул. Киренского, 26)

Автореферат разослан 17 сентября 2007 г

Ученый секретарь диссертационного совета

К В Сафонов

Общая характеристика работы

Актуальность темы. Булевы функции получили свое название в честь английского математика Джорджа Буля, который в своей монографии сформулировал алгебраическую систему логики Тем не менее, современное понятие булевой алгебры восходит к работам Джевонса и Пирса второй половины XIX века

Первоначально булевы функции рассматривались как логические формулы и явились действенным средством решения комбинаторных логических задач. Поэтому до середины XX века интерес к булевым функциям носил преимущественно теоретический характер Однако в 1938 г Клод Шеннон показал [10], как релейные схемы могут быть промоделированы с помощью булевых функций. В настоящее время булевы функции применяются при логическом проектировании цифровой и микропроцессорной техники, в теории кодирования и криптографии, а также в математическом моделировании

Еще в XIX веке стали изучать группу преобразований булевых функций, состоящую из операций двух видов перестановок переменных и замены переменных их отрицаниями Такую группу называют группой преобразований однотипности или группой Джевонса, а классы эквивалентности по группе Джевонса — типами булевых функций Джевонс изучал типы булевых функций применительно к проблемам индуктивной логики В качестве переменных выступали классы (понятия), а сами функции показывали объемные связи этих классов

В настоящее время задача построения классификаций булевых функций по различным группам преобразований имеет приложения в логическом синтезе, теории кодирования и других областях [4]

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

Построение различных классификаций также интересно в связи с применением к следующим задачам вычисление возможных характеристик функций, выбор функций, обладающих наилучшими для конкретной ситуации параметрами, определение полных систем инвариантов функций для заданной группы преобразований

Кроме задачи построения полной классификации, состоящей в нахождении всех классов эквивалентности, часто решают задачу пе-

речисления

Задача перечисления заключается в определении числа классов эквивалентности без нахождения самих представителей Впервые задачу подсчета числа классов эквивалентности булевых функций поставил Пойа [7], он же вычислил значения при малых п для группы перестановок переменных и группы Джевонса Подход, разработанный Пойа, основывался на связи задачи перечисления с теорией представлений групп В [11] были найдены явные формулы для вычисления числа классов для этих групп в общем случае

Пойа разработал общий метод нахождения числа классов для случая, когда группа является подгруппой группы подстановок на множестве значений переменных В дальнейшем теория перечисления Пойа была обобщена в работах Де Брейна [2]

Каждая булева функция п переменных реализуется 23 ~2 различными полиномиальными представлениями Одним из критериев оценки этих представлений является их сложность Чем меньше сложность полинома, тем он предпочтительнее, так как меньшая сложность дает меньшие размеры и большую скорость работы электронных схем, построенных с использованием данного полинома Появление интереса непосредственно к полиномиальным представлениям булевых функций, как объектам исследования, связано с практическими приложениями после того, как в конце прошлого века в цифровой технике стали активно использоваться элементы типа "сложение по модулю 2" Тенденция развития электроники в направлении увеличения быстродействия, уменьшения энергоемкости и стоимости привела к необходимости повышения эффективности цифровой техники во время проектирования — на уровне представления схем булевыми функциями

Поэтому возникла задача минимизации — нахождения формул наименьшей сложности, представляющих данную булеву функцию Использование минимальных формул позволяет повысить эффективность электронных схем, реализующих данные функции, — уменьшить их размер и увеличить скорость работы без применения новых технологий При этом для большинства функций полиномиальные нормальные формы по сравнению с другими нормальными формами — дизъюнктивными и конъюнктивными — имеют более компактный размер [9] и обладают лучшей тестируемостью [5]

Исследование полиномиальных представлений ведется весьма интенсивно Рассматривается широкий спектр вопросов от исследо-

ваний сложности и нахождения минимальных форм до алгоритмов прямой реализации на микросхемах специального типа — программируемых логических матрицах [8]

В ряде работ [1, 3] был предложен и разработан операторный подход к исследованию булевых функций Переход к операторным формам позволил упростить работу с полиномиальными формами, а также обобщить и структурировать классы полиномиальных нормальных форм

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

Цели работы:

• получить оценки на число классов относительно группы операторных преобразований булевых функций,

• найти инварианты операторных преобразований,

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

Основные результаты и научная новизна. Основные научные результаты диссертации следующие

• получена замкнутая формула для числа Б-классов булевых функций и асимптотическая оценка числа ЭР-классов булевых функций,

• найдена полная система инвариантов для функций 5 переменных по БР-преобразованиям,

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

Основные результаты диссертации являются новыми

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

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

Апробация работы. Результаты диссертации докладывались на следующих конференциях международная конференция "Алгебра, логика и кибернетика"(Иркутск, 2004 г), VI международная конференция "Дискретные модели в теории управляющих систем" (Москва, 2004 г), V школа-семинар "Распределенные и кластерные вычисления" (Красноярск, 2005 г.); VII международная конференция "Дискретные модели в теории управляющих систем "(Москва, 2006 г); XVI международная школа-семинар "Синтез и сложность управляющих систем "(Санкт-Петербург, 2006 г); российская школа-семинар "Синтаксис и семантика логических систем "(Иркутск, 2006 г), V Сибирская научная школа-семинар с международным участием "Компьютерная безопасность и криптография" (Томск, 2006 г), межвузовская зональная конференция "Математика и проблемы ее преподавания в вузе" (Иркутск, 2007 г), международный российско-китайский семинар "Алгебра и логика "(Иркутск, 2007 г), международная конференция "Алгебра и ее приложения"(Красноярск, 2007 г)

Публикации. По теме диссертации опубликовано 16 научных работ [12]—[27], отражающих основное содержание диссертации, в том числе три работы в журналах, рекомендованных ВАК РФ

Структура и объем работы. Диссертация изложена на 90 страницах и состоит из введения, трех глав, заключения и списка литературы, содержащего 85 наименований, включая работы диссертанта

Содержание работы

Во введении дается обоснование актуальности темы исследований Определяются основные понятия и терминология, принятая при изложении результатов

Для дальнейшего изложения нам потребуются следующие обозначения и определения

Будем использовать запись х для обозначения вектора переменных (#1, ,хп), а а — для обозначения вектора констант ац, ,ап

Степень определим следующим образом

а _( х> если ск = 1, ^ х, если а = О

Если в записи функции отсутствуют переменные, то предполагается, что ее переменными являются , ,хп

Степень функции / обозначим через й?ед(/)

Через йеЬ{М) обозначим определитель матрицы М, а ее ранг — через гапк(М)

Кронекерово произведение матриц будем обозначать символом 0 Введем следующее обозначение для кронекеровой степени матрицы

А-

А® А® ®А = А[п^ --„-'

П

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

Нулевая остаточная

/а:,(®1> 1&П—1) =/(я-1! ! ®г—1) 0> т-^п—1)

Единичная остаточная

> ^п—1) ? > Хг—1, 1, Хг,

Производная функции / по переменной хг определяется следующим образом

Полиномиальной нормальной формой (ПНФ) функции / называется ее представление в виде суммы по модулю 2

f(x ь ,хп)=К1@ ® К,

(1)

в которое в качестве слагаемых входят произведения Кг — ■ г^, где г3 = хъ или г3 = для некоторой переменной Хь, причем переменная может входить в произведение не более одного раза. В сумму может входить Кг, не содержащее ни одной переменной Такое Кг считается равным 1

Сложность представления (1) функции /(хг, - , хп) определяется как й — число слагаемых

Сложность !■(/) функции /(ж1, ,хп) определяется как сложность представления этой функции с минимальным числом слагаемых

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

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

Булева функция, заданная на некотором подмножестве всех двоичных наборов, называется частично заданной

Рассмотрим класс операторов на множестве булевых функций п переменных, которые удобно представить последовательностями ах ап, где аг £ {с1, е,р}, а число п называется размерностью оператора

Действие оператора а = ах . ап на функцию $(х) определяется по правилу а(/(£)) = где /0(г) = /(х) и

Цп) - тах £(/)

если а» = е, ,хп), если аг = р, если аг = с1

Представление функции / в виде

в

в котором а1, , as — операторы размерности п, называется операторной формой функции /, построенной по функции h

Пусть S — полная группа подстановок на множестве {d, е,р}.

о Í (йеЛ Л^Л fdeP\ /dep\ Л1ер\\

1 \dep/' Upe/ \Ved/ {eáp/ \epdj' \pde) )

S-преобразованием y> операторов размерности n назовем последовательность tpi ifin, где tpi G S Преобразование ip действует на оператор а = ai ап следующим образом <р(а) — <Pi(a.i) срп(ап)

Действие S-преобразований распространяется на множество функций SP-преобразование определяется как композиция S-преобразо-вания и перестановки символов операторов

Отображение г из множества Fn в некоторое множество X, удовлетворяющее соотношению

»(*>(/)) = »(/)

для всех / £ Fn и д € G, называется инвариантом группы G

Инвариант г группы G называется полным, если из совпадений значений i(f) и г(/') следует, что функции / и /' являются (^эквивалентными

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

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

Теорема 1. Специальная операторная форма по фиксированной функции h является каноническим представлением

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

Предложение 1. Пусть имеется S-преобразование <р и две операторные формы функции f(x) — и Фг Тогда две функции gi — (р(Фi) f(&2); полученные S-преобразованием этих оператор-

ных форм, равны

Доказывается, что множества S- и SP-преобразований составляют группы

Предложение 3. Группа SP(n) содержит 6™ п' преобразований

»

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

Теорема 2. Для любых двух базисных функций к\{х) и Л,г(:г) число -классов совпадает с числом -классов

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

В третьем параграфе исследуются инварианты операторных преобразований

Вторая глава посвящена операторным преобразованиям по фиксированной базисной функции — произведению Этот специальный случай позволяет получить оценки на число классов и по теореме 2 распространить их на любую базисную функцию

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

Теорема 3. Действие любого Б-преобразования <р = <р\ 1рп на функцию /(х), где / представляется вектором, представимо в виде <£>(/) = Л.(<р) /, при этом А(ир) — матрица размерности 2п х 2п, которая получается следующим образом

1 При п — 1 имеет место соответствие

2 Прип > 1 матрица А{ф) равна кронекерову произведению (®) соответствующих матриц

Следующие свойства матриц преобразований используются для подсчета числа классов

А(<р) = А((рг) <Э ®А(<рп)

Предложение 5.— единичная матрица размерности 2п х 2П и имеют место следующие равенства

дд[п] Н __ дд[п] _ ^jW ^[п] ^[тг] _

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

Теорема 4. Число S-классов Кд{п) булевых функций п переменных выражается формулой

Ksin) = ТС*п Г(4~ - 1)2«^ +

г=0 ^ '

В шестом параграфе получена асимптотическая оценка числа SP-классов

Теорема 5. Для Invn — числа инвариантных относительно группы SPn функций выполняется неравенство

Invn< 6n n' 232"""2

Следствие. Для числа SP-классов Кдр{п) имеет место следующая асимптотическая оценка.

Ksp(n) „

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

Теорема 6. L(7) < 28

Следствие. L(n) < ^2™ при п> 7

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

В параграфе 8 приводится алгоритм точной минимизации функций шести переменных, основой которого послужил алгоритм из [6] Этот алгоритм позволил ускорить до 30 раз работу базового алгоритма для функций, имеющих низкую и среднюю сложность

В параграфах 9 и 10 описываются генетические алгоритмы минимизации тотальных и частично заданных функций Построенные алгоритмы реализованы на языке С++ в последовательном и параллельном вариантах Тестовые запуски для предположительно самых сложных функций 7 и 8 переменных показали работоспособность алгоритмов

Библиографический список

[1] Винокуров С Ф Полиномиальные операторные разложения и канонические формы булевых функций / С Ф Винокуров — Иркутск: Из-во Иркутского ун-та. — 1992 — 26 с

[2] Де Брейн НДж Теория перечисления Пойа / НДж Де Брейн // Прикладная комбинаторная математика Под ред Э Беккенбаха — М Мир, 1968 — С 61-106

[3] Избранные вопросы теории булевых функций Монография / А С Балюк, С Ф Винокуров, А И Гайдуков и др , Под ред С.Ф. Винокурова, Н А Перязева — М Физматлит, 2001 — 192 с

[4] Логачев О А Булевы функции в теории кодирования и крип-тологии / О. А Логачев, А А Сальников, В В Ященко — М МЦНМО, 2004 - 470 с

[5] Fujiwara Н Logic Testing and Design for Testability / H Fujiwara // Computer System Series, MIT Press, 1986

[6] Gaidukov A Algorithm to derive minimum ESOPs for 6-variable functions / A Gaidukov // Proceedings of the 5th International Workshop on Boolean Problems 2002, Freiberg, Germany, Sept 1920, 2002 - pp. 141-148.

[7] Polia G Sur les types des propositions composees / G Polia //J Symb Logic. - 1937 — 5 - pp 98-103

[8] Sasao T On the complexity of mod-2 sum PLA's / T Sasao, P Besslich // IEEE Trans on Comput — 1990 — V 39, No 2 — P 262-266

[9] Sasao T Representation of Discrete Functions / T Sasao Kluwer Academic Publishers, May 1996

[10] Shannon С The Symbolic Analysis of Relay and Switching Circuits / С Shannon // Trans Am Inst Electrical Eng 38, 1938 - P 713

[11] Slepian D. On the number of symmetry types of Boolean functions of n variables / D Slepian // Canad J Math — 1953 — V 5 — №2 -pp 185-193

Работы автора по теме диссертации

[12] Казимиров А С Верхняя оценка сложности булевых функций в классе ПНФ / СФ Винокуров, АС Казимиров // Algebra and Model Theory 4 — Novisibirsk. Novosibirsk State Technical University, 2003 - P 160-165

[13] Казимиров А С Алгоритм частичной минимизации булевых функций в классе ПНФ /АС Казимиров // Алгебра, логика и кибернетика Материалы Международной конференции — Иркутск, ГОУ ВПО "Иркутский государственный педагогический университет 2004 — С 151-152

[14] Казимиров А С Некоторые свойства специальной операторной формы булевых функций / С Ф Винокуров, А С Казимиров // Дискретные модели в теории управляющих систем Труды VI Международной конференции — М. Издательский отдел Факультета ВМиК МГУ, 2004. - С. 19-21

[15] Казимиров А С О сложности булевых функций в классе ПНФ / С Ф Винокуров, А С Казимиров // Вестник Иркутского университета Специальный выпуск Материалы ежегодной научно-теоретической конференции молодых ученых — Иркутск Ир-кут ун-т, 2004 — С 78-79

[16] Казимиров АС О числе ОР-классов булевых функций / С Ф Винокуров, А С Казимиров // Проблемы теоретической кибернетики Тезисы докладов XIV Международной конференции - М МГУ, 2005 - С 29

[17] Казимиров А С Параллельный генетический алгоритм приближенной минимизации булевых функций /АС Казимиров, JI В. Рябец // Распределенные и кластерные вычисления Пятая школа-семинар в рамках международной конференции "Параллельные вычислительные технологии" (РаСТ-2005). — Красноярск Институт вычислительного моделирования СО РАН, 2005 - С 44-48

[18] Казимиров А.С Оценка числа классов LP-эквивалентности булевых функций / А.С Казимиров // Вестник Бурятского университета Математика и информатика — Улан-Удэ Бурятский государственный ун-т, 2005 —Серия 13 — Выпуск 2 — С 17-22

[19] Казимиров А С Генетические алгоритмы в задачах минимизации булевых функций /АС Казимиров // Технологии Microsoft в теории и практике программирования. Тез докл — Новосибирск, 2006 — С 182-184

[20] Казимиров А С Исследование полиномиальных представлений одной последовательности булевых функций /АС Казимиров / / Дискретные модели в теории управляющих систем VII Международная конференция, Покровское, 4-6 марта 2006 г Труды - М МАКС Пресс, 2006 - С 139-141.

[21] Казимиров А С Число классов булевых функций, порожденных операторными отображениями /АС Казимиров // Материалы XVI Международной школы-семинара "Синтез и сложность управляющих систем— М Изд-во механико-математического факультета МГУ, 2006 — С. 44-48

[22] Казимиров АС О числе SP-классов булевых функций / А.С Казимиров / / Синтаксис и семантика логических систем Материалы российской школы-семинара — Иркутск, Издательство ГОУ ВПО "Иркутский государственный педагогический университет 2006 — С 45-49

[23] Казимиров А С Параллельные генетические алгоритмы в задачах минимизации булевых функций / С Ф Винокуров, А С Казимиров // Вестник ТГУ Приложение — 2006 — № 17 — С 226-230

[24] Казимиров А С. Генетический алгоритм минимизации частично заданных булевых функций / А.С Казимиров // Вестник Бурятского университета Математика и информатика — Улан-Удэ Изд-во Бурятского госуниверситета, 2006. — Серия 13 — Выпуск 3. — С. 28-32

[25] Казимиров А С Алгоритм нахождения полиномиальных представлений частично заданных функций большой размерности / А С Казимиров // Математика и проблемы ее преподавания в вузе Труды III межвузовской конференции, посвященной памяти профессора Б А Бельтюкова — Иркутск Изд-во Иркут. гос пед ун-та, 2007 — С 125-126

[26] Казимиров А С Генетический алгоритм нахождения полиномиальных представлений частично заданных булевых функций / А.С Казимиров // Алгебра и логика Материалы международного российско-китайского семинара — Иркутск Издательство Иркут. гос пед. ун-та, 2007 — С 65-67

[27] Казимиров А С. Группы операторных преобразований булевых функций / А.С Казимиров // Международная конференция "Алгебра и ее приложения" Тезисы докладов. — Красноярск, 2007 - С 64-65

Редакционно-издательский отдел -государственного образовательного учреждения высшего профессионального образования Иркутского государственного педагогического университета 664003, Иркутск, ул Н Набережная, 6

Формат бумаги 60x84 1/16 Объем 1,0 п л Тираж 100 экз

Отпечатано на RISO в ООП факультета МФИ ИГПУ

Введение

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

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

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

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

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

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

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

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

§ 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 переменных.

Для б переменных известны две классификации [26]: по группам L3 и A3. Для большего числа переменных задача построения полной классификации обычно не ставится, так как если мощность группы невелика, то получается большое число классов. Если же увеличивать группу преобразований, то классификация становится бедной и содержит малое число классов больших размеров.

Поэтому классификация строится для некоторого подмножества функций п переменных. В случае линейной и аффинной групп удобным является ограничение степени нелинейности функций. Классификация квадратичных форм получена в [34]. В [26] приведена классификация однородных кубических форм относительно группы аффинных преобразований при 6 < п < 8.

Еще более сложной является проблема классификации систем булевых функций. Такая классификация по линейной и аффинной группам рассмотрена в работе [31].

Построение различных классификаций представляет большой практический интерес, поскольку при наличии классификации появляется возможность решать следующие задачи: вычисление возможных характеристик функций; выбор функций, обладающих наилучшими для конкретной ситуации параметрами; определение полных систем инвариантов функций для заданной группы преобразований.

Для дальнейшего изложения нам потребуются следующие обозначения и определения.

Будем использовать запись х для обозначения вектора переменных (xi, .,хп), а а — для обозначения вектора констант at,ап.

Степень определим следующим образом:

Г ж, если а = 1,

Ха — Л х, если а = 0.

Если в записи функции отсутствуют переменные, то предполагается, что ее переменными являются х\,.,хп.

Степень функции / обозначим через deg(f).

Через det(M) обозначим определитель матрицы М, а через гапк(М) — ее ранг.

Кронекерово произведение матриц будем обозначать символом <g>. Введем следующее обозначение для кронекеровой степени матрицы А:

А® А®. 0 А = А[п\ п

Остаточными подфункциями функции / по переменной Xi называются функции размерности на единицу меньше, полученные подстановкой констант вместо переменной

Нулевая остаточная: fxifa Ь • • • 1 %n-l) = Ь • • •) ^г'-li 0) • • • j ^n-l)'

Единичная остаточная: fXi(xh • • •; 1) = /(^1) • • • j Щ—ь • • • i i)

Производная функции / по переменной ж* определяется следующим образом: f'x.(x 1,., = /°(ягь. ,zni) ф /j.^i,. ,x„i).

Полиномиальной нормальной формой (ПНФ) функции / называется ее представление в виде суммы по модулю 2: f{xh.,xn) = K1®.®Ks, (1) в которое в качестве слагаемых входят произведения К{ = z\-. .-Zkv где Zj = Xt или Zj = xt для некоторой переменной xt, причем переменная может входить в произведение не более одного раза. В сумму может входить Кг, не содержащее ни одной переменной. Такое К{ считается равным 1. Произведения вида Ki называются элементарными конъюнкциями.

Для функции / представление (1) не единственно. Поэтому естественно рассмотреть сложность представления (1) функции f(x\,., хп) как s — число слагаемых.

Сложность L(f) функции f(x 1, .,хп) определяется как сложность представления этой функции, имеющего минимальное число слагаемых.

Сложность L(n) класса Fn всех булевых функций от п переменных определяется так:

L(n) — maxL(f) ftFn

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

Булева функция, заданная на некотором подмножестве всех двоичных наборов, называется частично заданной. При векторной записи таких функций используется символ '*' для обозначения наборов, на которых они не заданы. Такие наборы будем называть неопределенностями.

Пусть, например, функция / принимает значение 1 на наборах {(0,1,0), (0,1,1), (1,0,1)} и 0 на наборах {(0,0,1), (1,1,1)}. Тогда вектор, представляющий данную функцию, имеет вид / = (*011 * 1 * 0).

В ряде работ [3-8,10,29,39] был предложен и разработан операторный подход к исследованию булевых функций. Переход к операторным формам позволил упростить работу с полиномиальными формами, а также обобщить и структурировать классы полиномиальных нормальных форм.

Рассмотрим класс операторов на множестве булевых функций п переменных, которые удобно представить последовательностями ai. ап, где сц е {d, е,р}, а число п называется размерностью оператора.

Действие оператора a = ai. ап на функцию f(x) определяется по правилу: a(f(x)) = /„(:г), где /0(:г) = f{x) и

Например, оператор dpep действует следующим образом на конъюнкцию и дизъюнкцию четырех переменных: dpep(£i V х2 V xs V Х4) = (х\ V х2 V х$ V х$Х1 = х2 V ж3 V х±\ dpep(^i • х2 • хз • Х4) = Х2-хз-Представление функции / в виде в котором а1,., а5 — операторы размерности п, называется операторной формой функции /, построенной по функции h.

Сложность операторной формы определяется аналогично сложности ПНФ как число слагаемых.

Через М(Ф) будем обозначать множество операторов, входящих в операторную форму Ф. s г) = 5>'(Л),

Пусть S — полная группа подстановок на множестве {d, е,р}: Г /dep\ f dep\ /dep\ /dep\ f dep\ /dep\ 1 X Uep/ \dре/ \ped/ Up/ W/ U*/ J '

S-преобразованием ip операторов размерности n назовем последовательность . где ipi G 5. Преобразование (p действует на оператор а = ai. а„ следующим образом: </?(a) = <£i(ai). ipn(an).

Действие S-преобразований распространяется на множество функций. SP-преобразование определяется как композиция S-преобразования и перестановки символов в операторах.

Введем следующие обозначения для групп преобразований: Р — группа перестановок переменных, задает преобразование д{х) = f{xilt.,xin);

N — группа инвертирования переменных, задает преобразование g(x) = f(xa\.,xa«), ^ G {0,1};

PN — группа Джевонса, задает преобразование g(x) = f(x%,

L — группа линейных преобразований д(х) = f{Mx), an G {0,1}, det(M) ф 0;

А — группа аффинных преобразований д{х) = f{Mx®b), det{M)^ 0;

Li — группы обобщенных линейных преобразований д{х) = f(Mx) 0 h{x), det(M) ф 0, deg{h) < г;

А,- — группы обобщенных аффинных преобразований д(х) = f(Mx е Ь) Ф h(x), det(M) ф 0, deg(h) < i.

Отображение г из множества Fn в некоторое множество X, удовлетворяющее соотношению iW)) = Kf) для всех / G Fn и ip G G, называется инвариантом группы G.

Инвариант г группы G называется полным, если из совпадений значений i(f) и i(f') следует, что функции / и /' являются G-эквивалент-ными.

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

Можно заметить, что преобразования Р, N, PN, L и А сохраняют количество единиц в векторном представлении функции, более точно эти преобразования являются подстановками на множестве значений переменных [19]. Еще одним инвариантом по этим группам является степень нелинейности функции.

На диаграмме приведено сравнение по включению операторных преобразований (групп S и SP) с наиболее известными преобразованиями (включение — снизу вверх).

Рис. 1. Диаграмма включения групп преобразований

Преобразования Р, N, PN, S и SP сохраняют сложность операторной формы, в частности — сложность полиномиального представления. Все функции, попадающие в один класс эквивалентности относительно любой из этих групп, имеют одинаковую сложность (сложность как число слагаемых в операторной форме). Однако преобразования S и SP не только не являются подстановками на множестве значений переменных, но даже не сохраняют число единиц функции.

На следующей таблице представлены значения числа классов эквивалентности булевых функций для описанных групп преобразований [40, 41, 43, 44, 49, 65].

Таблица 1 п 1 2 3 4 5

N 3 7 46 4336 134 • 106

Р 4 12 80 3984 37 • 106

PN 3 6 22 402 1,2-10®

L 4 8 20 92 2744

Lo 2 4 10 46 1372

Li 1 2 3 14 176

А 3 5 10 32 382

А0 2 3 6 18 206

Ai 1 2 3 8 48

S 2 3 8 112 561432

SP 2 3 6 30 6936

Кроме задачи построения полной классификации, состоящей в нахождении всех классов эквивалентности, часто решают задачу перечисления.

Задача перечисления заключается в определении числа классов эквивалентности без нахождения самих представителей. Впервые задачу подсчета числа классов эквивалентности булевых функций поставил Пойа [53], он же вычислил значения при малых п для группы перестановок переменных и группы Джевонса. Подход, разработанный Пойа, оснои вывался на связи задачи перечисления с теорией представлений групп. В [65] были найдены явные формулы для вычисления числа классов для этих групп в общем случае.

Пойа [52] разработал общий метод нахождения числа классов для случая, когда группа является подгруппой группы подстановок на множестве переменных. В дальнейшем теория перечисления Пойа была обобщена в работах Де Брёйна [11, 33].

Для применения этой теории необходимо найти цикловые индексы соответствующих групп преобразований. В [28] найден цикловой индекс группы N, в [42] получены формулы для цикловых индексов групп Р и PN, в [41] - для L и А.

Теорема Пойа. Для числа классов Kg т-значпых функций по группе преобразований G — подгруппе группы подстановок на множестве значений аргументов — выполняется соотношение где Pq — цикловой индекс группы G.

Существенную часть теории Пойа составляет следующее утверждение, называемое леммой Бернсайда. Данная лемма, в отличие от теоремы Пойа, не требует, чтобы преобразования являлись подстановками на множестве наборов, а потому может быть применена для операторных преобразований.

Лемма Бернсайда [27]. Для числа классов Kg, порожденных группой G, выполняется соотношение:

Если для почти всех функций от п переменных при п —> сю группа инерции тривиальна, то говорят, что для группы преобразований имеет место эффект Шеннона. Это свойство позволяет получать асимптотические оценка числа Kg классов эквивалентности функций по группе G

Kg = PG(m,m, .,m) где st((p) = \{f : </?(/) = /}|. вида

В [18] это свойство доказано в общем виде для групп, действующих на множестве аргументов функций, а в [12] оно обобщено на группы Д-.

Каждая булева функция п переменных реализуется 23"-2" различными полиномиальными представлениями. Одним из критериев оценки этих представлений является их сложность. Чем меньше сложность полинома, тем он предпочтительнее, так как меньшая сложность дает меньшие размеры и большую скорость работы электронных схем, построенных с использованием данного полинома. Появление интереса непосредственно к полиномиальным представлениям булевых функций, как объектам исследования, связано с практическими приложениями после того, как в конце прошлого века в цифровой технике стали активно использоваться элементы типа "сложение по модулю 2". Тенденция развития электроники в направлении увеличения быстродействия, уменьшения энергоемкости и стоимости привела к необходимости повышения эффективности цифровой техники во время проектирования — на уровне представления схем булевыми функциями.

Поэтому возникла задача минимизации — нахождения формул наименьшей сложности, представляющих данную булеву функцию. Использование минимальных формул позволяет повысить эффективность электронных схем, реализующих данные функции, — уменьшить их размер и увеличить скорость работы без применения новых технологий. При этом для большинства функций полиномиальные нормальные формы по сравнению с другими нормальными формами — дизъюнктивными и конъюнктивными — имеют более компактный размер [61] и обладают лучшей тестируемостью [37, 46, 55].

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

Первые результаты по представлениям булевых функций в виде полиномов были опубликованы Жегалкиным в работах 1928 и 1929 годов [14, 15]. В них впервые в явном виде была введена и исследована каноническая форма, названная впоследствии полиномом Жегалкина.

Эта форма имеет следующий вид: f(xh., хп) = а0 Ф aiXi 0 а2х2 Ф . Ф апхп ф a^Xi • х2 ф . . . ф Otn-\nXn-1 • Хп ф . . . ф Oi\„.nX\ • . ' хп, где а; £ {0,1}.

Работа носила чисто теоретический характер и не получила широкого распространения. Полиномы Жегалкина были переоткрыты через четверть века в связи с развитием теории кодирования.

К середине пятидесятых годов широкое практическое применение получила теория кодирования. Исследования кодов привели к созданию в 1953 году класса линейных кодов, основанных на полиноме Жегалкина. Маллером [51] были введены полиномиальные канонические формы, явившиеся теоретической основой для создания таких кодов, а Ридом [56] был разработан эффективный алгоритм декодирования. Коды получили название кодов Рида-Маллера, а вместе с кодами введенные формы стали называться формами Рида-Маллера. Формы Рида-Маллера расширяют класс полиномов Жегалкина, допуская вхождения переменной с отрицанием: f(x 1, .,хп) = а0 ф aixl1 ф а2х22 ф . ф апхапп 0 а12х^х22 © .

• • • Ф а(п-1)пХп-1 Хп ф • • • ф • • • • • > где aij, Gi G {0,1}, вектор (crj,., ап) называется вектором поляризации. Другое название таких представлений — поляризованные полиномы Жегалкина.

Другое направление обобщения полиномов Рида-Маллера может быть представлено в виде: f(x 1,., хп) = а0 Ф а\Х\ Ф а2х2 Ф . Ф апхп ф «12^1^2 Ф . • 0 C¥jj—\nXn—\Xn 0 . . . 0 OL\.'nX\ ' • • • ' где коэффициенты щ 6 {0,1}, Х{ может быть либо Х{, либо щ ив разных слагаемых может быть разным.

Исследование полиномиальных представлений ведется весьма интенсивно. Рассматривается широкий спектр вопросов: от исследований сложности и нахождения мииимальных форм до алгоритмов прямой реализации на микросхемах специального типа — программируемых логических матрицах [9, 60].

Для сложности представлений булевых функций полиномиальными нормальными формами в течение долгого времени не существовало хороших оценок. Были известны только верхние оценки, носящие вычислительный характер, которые имели вид

L(n) < к • 2П, где к — некоторый множитель, который постепенно уменьшался с к = | до к = щ [47], и только недавно была получена оценка с неконстантой к [17]:

Цп)<21°9гП + 1- 2". п

Однако эта оценка является достаточно грубой для сравнительно небольших п.

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

Оказалось, что самыми сложными в поляризованных полиномах Жегалкина, кронекеровых и псевдокронекеровых формах являются функции, однотипные с функцией pn(xi,., хп):

ГО, если а\. .ап = 3 к, рп[аъ.,ап) = ^ 1, иначе, где ац.ап — число, записанное в двоичном виде.

Для всех полиномиальных представлений известны следующие нижняя [36] и верхняя [17] оценки:

2" <ОД<2"(21°^ + 2> п log2 3 п

Однако задача нахождения самой сложной функции остается открытой. И даже неизвестны сложности функций рп. Для рп известна [1] следующая оценка:

Jf <

Простая верхняя оценка получается из следующего неравенства:

L(pn) < Щрп-2)

С помощью вычислительной техники найдены Ь(р$) = 9 и L(pg) = 15 [47].

В [38] был предложен алгоритм минимизации булевых функций в классе ПНФ, использующий библиотеки функций с заранее просчитанными сложностями. Данный алгоритм позволяет находить минимальную ПНФ любой функции шести переменных. В качестве библиотеки представителей в этом алгоритме использовалась библиотека функций 5 переменных, построенная на основе всех представителей классов N-эквивалентности от 4 переменных. С помощью этого алгоритма были найдены все самые сложные функции шести переменных и было показано, что L(6) = 15.

В [67, 68] приводится алгоритм приближенной минимизации, дающий точный минимум для функций пяти переменных. Данный алгоритм исходит из специальной нормальной формы булевых функций, которая является каноническим представлением. На основе данного алгоритма в [23] предложен алгоритм, с помощью которого было получено полиномиальное представление для p-j сложности 24.

В [45] предложен алгоритм минимизации тотальных функций шести и семи переменных сложности не более 16, основанный на ограниченном переборе функций меньшей размерности.

Многие алгоритмы основаны на последовательном применении эвристических правил преобразований — разложений-сверток — к изначальному полиному, представляющему данную функцию [50, 59, 66]. В таких алгоритмах обычно выбирается полная система преобразований, те есть набор преобразований, которые позволяют из любой полиномиальной формы булевой функции получить любую другую. Тогда основной задачей алгоритма становится выбор последовательности применения преобразований. Однако все эти алгоритмы не гарантируют минимальность и могут быть применены только к функциям 5 переменных и небольшой части функций 6 и более переменных.

В [64] предложен алгоритм минимизации, основанный на применении к функции трех разложений: разложения Шеннона f(x) = Xifx{ © Xifxi> и двух разложений вида m = flexj^

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

Также существует множество алгоритмов [35, 57, 58], ориентированных на определенные классы полиномиальных форм. Среди них стоит отметить алгоритм [2], позволяющий получить точный минимум в кро-некеровых формах для функций, имеющих до 16 переменных.

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

Диссертация состоит из введения, трех глав, разбитых на 10 параграфов, заключения и списка литературы.

Заключение

На защиту выносятся следующие результаты.

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

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

3. Найдена полная система инвариантов для функций 5 переменных но SP-иреобразованиям

4. Разработаны и реализованы генетические алгоритмы минимизации полиномиальных представлений тотальных и частично заданных булевых функций

Выражаю благодарность своему научному руководителю С.Ф. Винокурову за всестороннюю поддержку во время работы над диссертацией, а также всем участникам семинара "Теория булевых функций", который проходит при Иркутском государственном педагогическом университете.

1. Винокуров С.Ф. Алгоритм точной минимизации булевых функций в классе кронекеровых форм / С.Ф. Винокуров, Л.В. Рябец // Алгебра и теория моделей 4. — Новосибирск, 2003. — С. 148-159.

2. Винокуров С.Ф. Полиномиальная декомпозиция булевых функций по образам однородных операторов от невырожденных функций / С.Ф. Винокуров, Н.А. Перязев // Изв. вузов. Матем. — 1996. — № 1. С. 17-21.

3. Винокуров С.Ф. Полиномиальные операторные разложения и канонические формы булевых функций / С.Ф. Винокуров. — Иркутск: Из-во Иркутского ун-та. — 1992. — 26 с.

4. Винокуров С.Ф. Полиномиальные разложения булевых функций по образам неоднородных операторов / С.Ф. Винокуров, Н.А. Перязев // Кибернетика и системный анализ. — 2000. — № 4. — С. 40-55.

5. Винокуров С.Ф. Представление булевых функций полиномиальными формами / С.Ф. Винокуров, Н.А. Перязев // Кибернетика и системный анализ. 1992. - № 3. - С. 175-179.

6. Винокуров С.Ф. Смешанные операторы в булевых функциях и их свойства / С.Ф. Винокуров // Иркутский Университет. Серия: Дискретная математика и информатика. — Иркутск, 2000. — Вып. 12. — 36 с.

7. Винокуров С.Ф. Система автоматического синтеза частичных конечных автоматов на программируемых логических матрицах с памятью / С.Ф. Винокуров, Ю.В. Манцивода, Н.А. Перязев // Вычислительные системы, 146. — Новосибирск, 1992. — С. 142-143.

8. Винокуров С.Ф. Специальная операторная форма булевых функций и некоторые ее приложения / С.Ф. Винокуров // Международная школа-семинар "Синтез и сложность управляющих систем". — Новосибирск. Изд-во Института математики. — 2004. — С. 26-29.

9. И. Де Брейн Н.Дж. Теория перечисления Пойа / Н.Дж, Де Брейи // Прикладная комбинаторная математика. Под. ред. Э. Беккенбаха. — М.: Мир, 1968. С. 61-106.

10. Денев И. О числе классов эквивалентности булевых функций относительно некоторых групп преобразований / И. Денев, В. Тончев // Матем. и матем. образование. Научн. съобщ. на 9-та практ. конф. на съюза на мат. в Българии, 1980, София. — 1980. — С. 41-43.

11. Джевонс С. Основы науки / С. Джевонс. СПб., 1881.

12. Жегалкин И.И. Арифметизация символической логики / И.И. Же-галкин // Мат. сборник. 1928. - Т. 35. - С. 311-373.

13. Жегалкин И.И. Арифметизация символической логики / И.И. Жегалкин // Мат. сборник. 1929. - Т. 36. - С. 305-338.

14. Избранные вопросы теории булевых функций: Монография / А.С. Балюк, С.Ф. Винокуров, А.И. Гайдуков и др.; Под ред. С.Ф. Винокурова, Н.А. Перязева. — М.: Физматлит, 2001. — 192 с.

15. Кириченко К.Д. Верхняя оценка сложности полиномиальных нормальных форм булевых функций / К.Д. Кириченко // Дискретная математика. 2005. - Т. 17, № 3. - С. 80-88.

16. Клосс Б.М. О классификации функций многозначной логики / Б.М. Клосс, Э.Н. Нечиропук // Проблемы кибернетики. — М.: Физ-матгиз, 1963. Вып. 9 - С. 27-36.

17. Логачев О.А. Булевы функции в теории кодирования и криптоло-гии / О.А. Логачев, А.А. Сальников, В.В. Ященко М.: МЦНМО, 2004. - 470 с.

18. Поваров Г.Н. Исследование контактных схем с минимальным числом контактов / Г.Н. Поваров. Диссертация. ИАТ АН СССР, 1954.

19. Поваров Г.Н. О групповой инвариантности булевых функций / Г.Н. Поваров // Применение логики в науке и технике. — М.: АН СССР, 1961. С. 263-340.

20. Рябец Л.В. Нахождение минимальных полиномов булевых функций с использованием специальной операторной формы / Л.В. Рябец // Технологии Microsoft в теории и практике программирования. — Новосибирск, 2006. С. 215-217.

21. Страздинь И.Э. Аффинная классификация булевых функций пяти переменных / И.Э. Страздинь // Автоматика и вычислительная техника. 1975. № 1. С. 1-9.

22. Черемушкин А.В. Линейная и аффинная классификация дискретных функций (обзор публикаций) / А.В. Черемушкин // Математические вопросы кибернетики, 2005. — С. 261-280.

23. Applied combinatorial mathematics / Е.Е. Beckenbach. New York, London, Sydney: John Wiley & Sons, Inc., 1964.

24. Ashenhurst R.L. The application of counting techniques / R.L. Ashen-hurst // Proceedings of the Association for Computing Machinery, Pitsburg Meeting. — 1952. — pp. 293-305.

25. Balyuk A. Classes of Operator Forms / A. Balyuk, S. Vinokurov // 5th International Workshop on Boolean Problems. — Freiberg, Germany, 2002. — P. 217-224.

26. Berlekamp E.R. Weight Distributions of the Cosets of the (32; 6) Reed-Muller Code / E.R. Berlekamp, L.R. Welch // IEEE Trans. Inform. Theory. — January 1972. — IT-18. — No. 1. — pp. 33-50.

27. Dixon L.E. Linear groups with exposition Galois field theory / L.E. Dixon — Leipzig, 1901.

28. Drechsler R. Fast OFDD-based minimization of fixed polarity Reed-Muller expressions / R. Drechsler, M. Theobald, B. Becker // IEEE Trans. Comput., Vol. C-45, No. 11, Nov. 1996. — pp. 1294-1299.

29. Even S. On minimal modulo 2 sums of products for switching function / S. Even, I. Kohavi, A. Paz // IEEE Trans. Elect. Comput. — 1967. — P. 671-674.

30. Fujiwara H. Logic Testing and Design for Testability / H. Fujiwara. Computer System Series, MIT Press, 1986.

31. Gaidukov A. Algorithm to derive minimum ESOPs for 6-variable functions / A. Gaidukov // Proceedings of the 5th International Workshop on Boolean Problems 2002, Freiberg, Germany, Sept. 19-20, 2002. — pp. 141-148.

32. Gaidukov A.I. Operator polynomial expansions of Boolean functions / A.I. Gaidukov, S.F. Vinokurov // 4th International Workshop on Boolean Problems. — Freiberg, Germany, 2000. — P. 63-68.

33. Harrison M.A. Counting Theorems and Their Applications to Classification of Switching Functions / M.A. Harrison // Recent Development in Switching Theory. New York, 1971.

34. Harrison M.A. On the classification of Boolean functions by the general linear and affine groups / M.A. Harrison //J. Soc. for Indust. and Appl. Math. — 1964. — v. 12. — No. 2. pp. 285-299.

35. Harrison M.A. On the number of classes of invertible Boolean functions / M.A. Harrison //J. Soc. for Indust. and Appl. Math. — 1963. — v. 10. — No. 1. — pp. 25-28.

36. Harrison M.A. On the number of transitivity sets of Boolean functions / M.A. Harrison //J. Soc. for Indust. and Appl. Math. — 1963. — v. 11. — No. 3. pp. 806-828.

37. Harrison M. A. The number of equivalence classes of Boolean functions under groups containing negation / M.A. Harrison // IEEE Trans. Electr. Comput. — 1963. — v. 12. — No. 5. pp. 559-561.

38. Hirayama T. Minimizing AND-EXOR Expressions of Some Benchmark Functions / T. Hirayama, T. Sato, Y. Nishitani // 6th International Symposium on Representations and Methodology of Future Computing Technology (RM), Trier, Germany, 2003. — pp. 69-76.

39. Kalay U. A Minimal Universal Test Set for Self Test of EXOR-Sum-Of-Products Circuits / U. Kalay, M. Perkowski, D. Hall // IEEE Trans. Сотр. Vol. 49, No. 3, March 1999. — pp. 267-276.

40. Koda N. An Upper Bound on the Number of Products in Minimum ESOPs / N. Koda, T. Sasao // Workshop in Application of the Reed-Muller Expansion in Circuit Design. Japan, 1995. — pp. 94-101.

41. Koda N. LP equivalence class of logic functions / N. Koda, T. Sasao // IFIP 10.5 Workshop on Application of the Reed-Muller expansion in Circuit Design, Sept. 1993. — pp. 99-106.

42. Maiorana J.A. A Classification of the Cosets of the Reed-Muller code R(l,6) / J.A. Maiorana // Mathematics and Computation. — July 1991. — Vol. 57 — No. 195. — pp. 403-414.

43. Muller D.E. Application of Boolean algebra to switching circuit design and error detection / D.E. Muller //IRE Trans. Electron. Comput. — 1954. — V.3, N. 3. — pp. 6-12.

44. Polia G. Kombinatorische Anzahlbestimmungen fiir Gruppen, Graphen, und chemische Verbindungen / G. Polia // Acta Math. — 1937. — 68. — pp. 145-253.

45. Polia G. Sur les types des propositions composees / G. Polia //J. Symb. Logic. — 1937. — 5. — pp. 98-103.

46. Practical Handbook of Genetic Algorithms: Complex Coding Systems: Volume III. Editor Chambers L. — Boca Raton, FL: CRC Press, 1999.

47. Pradhan D.K. Fault-Tolerant Computing. Theory and Techniques / D.K. Pradhan. Vol. I, Prentice-Hall, 1987.

48. Reed I.S. A class of multiply-error-correcting codes and decoding scheme / I.S. Reed // IRE Trans. Inform. Theory. — 1954. — V. 4, N. 9. — pp. 38-49.

49. Sarabi A. Fast exact and quasiminimal minimization of highly testable fixed polarity AND/XOR canonical networks / A. Sarabi, M.A. Perkowski // Proc. Design Automation Conference, June 1992. — pp. 30-35.

50. Sasao T. Exact minimization of FPRMs using multi-terminal EXOR TDDs / T. Sasao, F. Izuhara // T. Sasao and M. Fujita, eds., Representations of Discrete Functions, Kluwer Academic Publishers, 1996.

51. Sasao T. On the complexity of mod-2 sum PLA's / T. Sasao, P. Besslich // IEEE Trans, on Comput. — 1990. — V. 39, No. 2. — pp. 262-266.

52. Sasao T. Representation of Discrete Functions / T. Sasao. Kluwer Academic Publishers, May 1996.

53. Schroder E. Vorlesungen iiber die Algebra der Logik / E. Schroder. Bd. 1, Anhang 6, S. 647-683.

54. Shannon C. The Symbolic Analysis of Relay and Switching Circuits / C. Shannon. Trans. Am. Inst. Electrical Eng. 38, 1938. — P. 713.

55. Slepian D. On the number of symmetry types of Boolean functions of n variables / D. Slepian // Canad. J. Math. — 1953. — V. 5. — No. 2. — pp. 185-193.

56. Song N. Minimization of exclusive sum-of- products expressions for multiple-valued input, incompletely specified functions / N. Song, M.A. Perkowski // IEEE Trans. Comput.-Aided Des. Integrated Circuits к Syst., vol. 15, no. 4, 1996. — pp. 385-395.

57. Steinbach B. On SNF Optimization: A functional Comparison of Methods / B. Steinbach, V. Yanchurin, M. Lukac // 6th International Symposium on Representations and Methodology of Future Computing Technology (RM), Trier, Germany, 2003. — pp. 11-18.

58. Steinbach B. SNF: A Special Normal Form for ESOP / B. Steinbach, A. Mishchenko // Proceedings of the 5th International Workshop on Application of the Reed-Muller Expansion in Circuit Design RM2001, Mississippi State University, USA, 2001. — pp. 66-81.

59. Synthesis of electronic computing and control circuits. Cambridge, Mass., Harvard Univ. Press, 1951.

60. Казимиров А.С. Верхняя оценка сложности булевых функций в классе ПНФ / С.Ф. Винокуров, А.С. Казимиров // Algebra and Model

61. Theory 4. — Novisibirsk. Novosibirsk State Technical University, 2003. — P. 160-165.

62. Казимиров А.С. О числе ОР-классов булевых функций / С.Ф. Винокуров, А.С. Казимиров // Проблемы теоретической кибернетики: Тезисы докладов XIV Международной конференции. — М.: МГУ, 2005. С. 29.

63. Казимиров А.С. Оценка числа классов LP-эквивалентности булевых функций / А.С. Казимиров // Вестник Бурятского университета:

64. Математика и информатика. — Улан-Удэ: Бурятский государственный ун-т, 2005. Серия 13. - Выпуск 2. - С. 17-22.

65. Казимиров А.С. Генетические алгоритмы в задачах минимизации булевых функций / А.С. Казимиров // Технологии Microsoft в теории и практике программирования: Тез. докл. — Новосибирск, 2006. С. 182-184.

66. Казимиров А.С. О числе SP-классов булевых функций / А.С. Казимиров // Синтаксис и семантика логических систем: Материалы российской школы-семинара. — Иркутск, Издательство ГОУ ВПО "Иркутский государственный педагогический университет2006. — С. 45-49.

67. Казимиров А.С. Параллельные генетические алгоритмы в задачах минимизации булевых функций / С.Ф. Винокуров, А.С. Казимиров // Вестник ТГУ. Приложение. 2006. - № 17. - С. 226-230.

68. Казимиров А.С. Генетический алгоритм минимизации частично заданных булевых функций / А.С. Казимиров // Вестник Бурятского университета: Математика и информатика. — Улан-Удэ: Изд-во Бурятского госуниверситета, 2006. — Серия 13. — Выпуск 3. — С. 28-32.

69. Казимиров А.С. Группы операторных преобразований булевых функций / А.С. Казимиров // Международная конференция "Алгебра и ее приложения": Тезисы докладов. — Красноярск, 2007. — С. 64-65.