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

• Казимиров, Алексей Сергеевич
• кандидат физико-математических наук
• 2007

Оглавление диссертации кандидат физико-математических наук Казимиров, Алексей Сергеевич

Введение

Глава 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. Разработаны и реализованы генетические алгоритмы минимизации полиномиальных представлений тотальных и частично заданных булевых функций

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

Список литературы диссертационного исследования кандидат физико-математических наук Казимиров, Алексей Сергеевич, 2007 год

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.