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

• Перязев, Николай Алексеевич
• доктор физико-математических наук
• 1998

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

Оглавление

Введение

Глава I. Основные понятия и результаты

§1. Основные понятия и терминология теории булевых

функций

§2. Обзор результатов по формульным представлениям

булевых функций

Глава II. Бесповторные и слабоповторные булевы функции

§3. Критерии бесповторности булевых функций

§4. Нахождения представлений булевых функций бесповторными формулами

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

Глава III. Полиномиальные разложения булевых функций

§6. Полиномиальные разложения общего вида

§7. Разложения булевых функций по образам однородных операторов

§8. Разложения булевых функций по образам неоднородных операторов

§9. Полиномиальные канонические формы булевых функций

Глава IV. Вопросы сложности представлений булевых

функций формулами

§10. Сложность представлений булевых функций формулами в немонолинейных базисах

§11. Сложность представлений булевых функций полиномиальными формами

Заключение

Список литературы

Введение диссертации (часть автореферата) на тему «Существование и сложность представлений булевых функций формулами»

Введение

Изучение теорий функциональных систем образуют одно из главных направлений в математике. Теория конечно-значных функций наряду с теорией графов является универсальным аппаратом описания конечных моделей в дискретной математике и математической кибернетике. Изучение таких функциональных систем связано с именами целого ряда выдающихся математиков. Среди них Дж. Буль, Г. Фреге, А. Пирс, М. Шеффер, П.С. Порецкий, Е. Пост, К. Шеннон, И.И. Жегал-кин, А.И. Мальцев, В.М. Глушков, A.B. Кузнецов, C.B. Яблонский, О.Б. Jlyпанов.

Особая роль в теории конечнозначных функциональных систем отводится булевым функциям. Отметим, что булевы функции, в зависимости от применения, называют также функциями алгебры логики (при использовании в логических системах), переключательными или двоичными функциями (при использовании в технических приложениях). Название булевы функции связано с именем английского математика Дж. Буля. В 1854 г. Дж. Буль в связи со своими исследованиями по математической логике ввел класс математических структур, впоследствие названный в его честь булевыми алгебрами. В 1879 г. немецкий математик Г. Фреге в исследованиях по основаниям математики вводит в рассмотрение функцию — понятие, в сущности, совпадающее с современным понятием булевой функции.

В дальнейшем применение теории булевых функций в логике было значительно развито. Булевы функции приобрели фундаментальное значение для оснований математики, однако долго оставались практически невостребованными в части математических приложений. Только открытие в середине XX века приложений к техническим проблемам стимулировало внимание к теории булевых функций. В работах К. Шеннона [80] и В.И. Шестакова [57] была впервые продемонстрирована плодотворность идеи применения развитого ранее в рамках математической логики аппарата теории булевых функций к проблемам синтеза релейно-контактных схем. Функционирование самой сложной современной компьютерной техники поддается описанию средствами теории булевых функций. Поэтому общепризнано, что булевы функции являются основным аппаратом для изучения дискретных преобразователей информации. Для современного уровня развития цивилизации характерным является переработка громадного объема информации, что тесно связано с развитием компьютерной техники. В свою очередь развитие компьютерной техники зависит от уровня разработки математических моделей дискретных преобразователей информации. При этом повышается роль математических моделей для обработки, хранения, передачи и тестирования информации. В связи с этим теория булевых функций нашла применение не только в логических системах и при синтезе различного рода схем, но и в диагностике и контроле

схем, в теории кодирования, в теории конечных автоматов, в теории игр, в языках программирования и даже для математического моделирования природных процессов.

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

При этом отметим следующие фундаментальные проблемы:

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

2. Нахождение множества функций Л или формул специально заданного вида Ф таких, что любые булевы функции из некоторого множества К представляются формулами над Я или формулами вида Ф, при этом если такая формула в определенном смысле единственна, то такие формулы называются каноническими формами для класса К.

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

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

В 20 — 40-х годах Э. Посту удалось описать все порожденные с помощью суперпозиции классы булевых функций — замкнутые классы функций. Краткое изложение этого результата было опубликовано в [74], при этом детальное изложение появилось значительно позже [75]. Полное упрощенное изложение содержится в книге [62], которая оказала большое влияние на развитие теории булевых функций. В дальнейшем доказательство результата Э. Поста было еще упрощено. В связи с этим отметим книгу [32].

Среди представлений булевых функций формулами специального вида хорошо известны разложение Шеннона, двойственное к разложению Шеннона, разложение, получаемое из разложения Шеннона заменой дизъюнкции на сложение по модулю два, разложение Акерса, а также канонические формы: совершенные дизъюнктивная и конъюнктивная нормальные формы, совершенная полиномиальная нормальная форма, поляризованные полиномы Жегалкина и другие [1, 12, 32, 33, 59, 60].

Разработке алгоритмов нахождения формульных представлений булевых функций посвящено довольно много исследований. Отметим только публикации обзорного характера [1, 12, 13, 33, 60, 42].

Из результатов по оценки сложности формульных пред-

ставлений отметим полученное О.Б. Лупановым [27, 28] асимптотическое выражение для функции Шеннона, которая используется для оценки сложности, а также общепринятое мнение, что получение нижних оценок сложности конкретных функций является трудной и до настоящего времени недостаточно разработанной проблемой теории булевых функций [29, 38, 44, 55].

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

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

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

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

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

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

По первой проблеме:

— описан в терминах остаточных функций класс булевых функций бесповторных в бинарном базисе;

— описан в терминах обобщенной однотипности класс булевых функций слабоповторных в бинарном базисе.

По второй проблеме:

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

По третьей проблеме:

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

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

По четвертой проблеме:

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

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

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

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

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

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

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

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

По результатам, изложенным в диссертации, имеется 27 публикаций [85-111]. Результаты докладывались на международных конференциях по алгебре, дискретной математике, математической и прикладной логике, теоретической и технической кибернетике, в том числе было сделано несколько пленарных докладов (конференция по прикладной логике, Новосибирск, 1992; конференция по математической логике, Казань, 1992; 4-й семинар по дискретной математике и ее при-

ложениям, Москва, 1993; школа-семинар "Дискретные модели в теории управляющих систем", Москва, 1993; X конференция по проблемам теоретической кибернетики, Саратов, 1993; III конференция по алгебре, Красноярск, 1993; школа-семинар " Сложность и синтез управляющих систем", Минск, 1993; конференция, посвященная 1000 заседанию семинара "Алгебра и логика", Новосибирск, 1994; школа-семинар "Сложность и синтез управляющих систем", Н.Повгород, 1994; конференция " Нестандартная логика и логические аспекты информатики", Канадзава (Япония), 1994; конференция по прикладной логике, Иркутск, 1995; конференция "Нестандартные логики и логика в программировании", Иркутск, 1995; школа-семинар "Сложность и синтез управляющих систем", Минск, 1995; конференция " Автоматизация проектирования дискретных систем", Минск, 1995; конференция по проблемам теоретической кибернетики, Ульяновск, 1996; конференция по приложениям разложения Рида-Маллера в синтезе схем, Оксфорд (Великобритания), 1997; конференция "Мальцевские чтения", Новосибирск, 1997).

Были сделаны доклады в ведущих научных центрах: Московский государственный университет (механико-математический факультет и факультет вычислительной математики и кибернетики), Институт математики СО РАН (г. Новосибирск), Институт кибернетики им. В.М.Глушкова (г. Киев), Институт технической кибернетики (г. Минск), Ин-

ститут математики с вычислительным центром (г. Кишинев), Иркутский государственный университет.

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

Заключение диссертации по теме «Дискретная математика и математическая кибернетика», Перязев, Николай Алексеевич

Заключение

Выделим основные результаты диссертации.

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

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

3. Разработан операторный подход к заданию полиномиальных разложений, на основе которого получены полиномиальные разложения по различным операторам;

4. Введен широкий класс полиномиальных канонических форм и найдены формулы для вычисления коэффициентов представлений булевых функций этими формами;

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

6. Получено значение функции Шеннона для множеств всех и всех симметрических булевых функций в классе полиномиальных конъюнктивных поляризованных форм;

7. Получена точная нижняя оценка функции Шеннона для множества симметрических булевых функций в классе полиномиальных конъюнктивных нормальных форм.

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

Список литературы

[1] Дискретная математика и математические вопросы кибернетики/ Под ред. Яблонского C.B. и Лупанова О.Б.-М: Наука, 1974.- Tl.- 312 с.

[2] Авгуль Л.Б. Супрун В.П. Обобщенные полиномиальные разложения симметрических булевых функций// Кибернетика.- 1991.- № 1- С. 122-125.

[3] Авсаркисян Г.С. Обобщенные полиномиальные формы булевых функций и синтез многовыходных логических схем// Автоматика и Телемеханика.- 1983.- № 11.- С. 111-119.

[4] Авсаркисян Г.С. Представление булевых функций суммой по модулю 2 импликацией аргументов / / Автоматика и вычислительная техника.- 1977.- №1.- С. 8-11.

[5] Авсаркисян Г.С. Брайловский Г.С. Представление логических функций в виде полиномов Жегалкина// Автоматика и вычислительная техника.- 1975.- № 6.- С. 6-10.

[6] Алексанян A.A. Реализация булевых функций дизъюнкциями произведений линейных форм// ДАН СССР.-1989.- Т. 304, № 4.- С. 781-784.

[7] Андреев А.Е. Об одном методе получения более чем квадратичных эффективных нижних оценок сложности тг-схем// Вестн. МГУ. Сер. 1. Матем. Мех.- 1987.- № 1-С. 70-73.

[8] Артюхов B.JL, Копейкин Г.А., Шалыто A.A. Настраиваемые модули для управляющих логических устройств.-Ленинград: Энергоиздат, 1981.- 166 с.

[9] Бохманн Д., Постхоф X. Двоичные динамические системы.- М: Энергоатомиздат, 1986.- 401 с.

[10] Винокуров С.Ф. Некоторые оценки сложности булевых функций в классе полиномов по неоднородным операторам // Синтез и сложность управляющих систем. Материалы VI межгосударственной школы-семинара. -Минск, 1995.- С. 4-5.

[11] Гаврилов Г.П. Функциональные системы дискретной математики.- М: Изд-во Московского ун-та, 1985.- 40 с.

[12] Глушков В.И. Введение в кибернетику.- Киев: Изд-во АН УССР, 1964.- 324 с.

[13] Глушков P.M., Капитонова Ю.В., Мищенко А.Т. Логическое проектирование дискретных устройств.- Киев: На-укова думка, 1987.- 264 с.

[14] Гурвич В.А. О бесповторных булевых функциях// Успехи математ. наук.- 1977.- 32, №1- С. 183-184.

[15] Гурвич В.А. Критерий бесповторности функций алгебры логики// ДАН СССР.- 1991.- 318, №3.- С. 532-537.

[16] Зуев Ю.А. Пороговые функции и пороговые представления булевых функций// Математические вопросы кибернетики.- 1994.- №5.- С. 5-61.

[17] Касим-Заде О.М. О сложности параметрических представлений функций алгебры логики// Проблемы теоретической кибернетики. Тезисы докладов XI Международной конференции.- М.: Изд. центр РГГУ, 1996.- С. 86-88.

[18] Касим-Заде О.М. Об одной метрической характеристике неявных и параметрических представлений булевых функций// Математические вопросы кибернетики.-1996.- №1- С. 133-188.

[19] Корсуков A.B. Разложение булевых функций с оператором векторная производная// В кн. Алгебра, логика и приложения.- Иркутск, 1994.- С. 116-124.

[20] Кричевский P.E. Сложность контактных схем, реализующих одну функцию алгебры логики// ДАН СССР.-1963.- Т. 149, № 4.- С. 784-787.

[21] Кричевский P.E. О реализации функций суперпозициями// Проблемы кибернетики.- 1959.- Вып. 2.- С. 123— 138.

[22] Кузнецов A.B. О бесповторных контактных схемах и бесповторных суперпозициях функций алгебры логики// Труды математ. института им. В.А.Стеклова.- 1958.- Т. 51- С. 186-225.

[23] Кузнецов С.Е., Нигматуллин Н.Р. О сложности реализации некоторых симметрических функций формулами глубины 3 в базисе {&, V, —}// В сб. Вероятностные методы и кибернетика.- Изд-во Казанского ун-та, 1985.- Вып. 21.-С.36-54.

[24] Кузнецов Ю.В., Шкарин С.А. Коды Рида-Маллера (обзор публикаций) // Математические вопросы кибернетики.-1996.- №1- С. 5-50.

[25] Лупанов О.Б. Об одном подходе к синтезу управляющих систем- принципе локального кодирования// Проблемы кибернетики. Вып. 14.- М.: Наука, 1965.- С. 31-110.

[26] Лупанов О.Б. О влиянии глубины формул на их сложность// Кибернетика.- 1970.- № 2.- С. 46-49.

[27] Лупанов О.Б. О сложности реализаций функций алгебры логики формулами// Проблемы кибернетики. Вып. 3. гиз, 1963.- С. 61-80.

[28] Лупанов О.Б. Асимптотическая оценка сложности управляющих систем.- М.: Из-во МГУ, 1984.- 137 с.

[29] Лупанов О.Б. О методах получения оценок сложности и вычисления индивидуальных функций// Дискретный анализ. Вып. 25.- Новосибирск, 1974. - С. 3-18.

[30] Малышев В.А. Класс "почти всех" функций с нелинейной сложностью при реализации П-схемами// Проблемы кибернетики. Вып. 19.- М.: Наука, 1967. - С. 299-306.

[31] Марченков С.С. О равномерном id-разложении булевых функций// Дискретная математика.- 1990.- Т. 2, № 3-С. 29-41.

[32] Марченков С.С., Угольников А.Б. Замкнутые классы булевых функций.- М: Ин-т прикл математики АН, 1990.147 с.

[33] Мачикенас Э.К., Супрун В.П. О полиномиальном разложении булевых функций// Изд-во Белорусской АН, физмат. лит-ра, Минск.- 1988.- 31 с.

[34] Мучник Б.А. Оценка сложности реализаций линейной функции формулами в некоторых базисах// Кибернетика.- 1970.- № 4.- С. 29-38.

[35] Нечипорук Э.И. Об одной булевской функции// ДАН СССР.- 1966.- 169, № 4.- С. 765-766.

[36] Нигматуллин Р.Г. Нижние оценки сложности и сложность универсальных схем.- Казань: Изд-во КГУ, 1980.112 с.

[37] Нигматуллин Р.Г. Сложность булевых функций.- Изд-во Казанского ун-та, 1983.- 208 с.

[38] Нигматуллин Р.Г. Сложность булевых функций.- М.: Наука, 1991.- 240 с.

[39] Поваров Г.Н. О функциональной разделимости булевых функций// ДАН СССР.- 1954.- Т. 94, № 5.- С. 801-803.

[40] Поваров Г.Н. Математико-логическое исследование синтеза контактных схем с одним входом и к выходами// Логические исследования. Изд-во АН СССР.- 1959.- С.379-405.

[41] Риордан Дж. Введение в комбинаторный анализ.- М.: Изд-во иностр. литературы, 1963.- 287 с.

[42] Сапоженко A.A., Чухров И.П. Минимизация булевых функций в классе дизъюнктивных нормальных форм// ВИНИТИ. Итоги науки и техники. Теоретическая кибернетика.- 1987.- Вып. 25.- С. 68-116.

[43] Стеценко В.А. Об одном необходимом признаке для пред-максимальных базисов в Р2Ц ДАН СССР.- 1990.- Т. 315. - С. 1304-1307.

[44] Стеценко В.А. О предплохих базисах в Р2// Математ. вопросы кибернетики. Вып.4.- 1992.- С. 139-177.

[45] Субботовская Б. А. О реализации линейных функций формулами в базисе V,&,-// ДАН СССР.- 1961.- Т. 136, № 3.- С. 553-555.

[46] Субботовская Б.А. О сравнении базисов при реализации функций алгебры логики формулами// ДАН СССР.-1963.- Т. 149, № 4.- С. 784-787.

[47] Супрун В.П. Об одном методе полиномиального разложения булевых функций// Кибернетика.- 1989.- № 5.-С. 122-124.

[48] Супрун В.П. Сложность булевых функций в классе канонических поляризованных полиномов / / Дискретная математика.- 1993.- Т. 5, Вып.2.- С.111-115.

[49] Тошич Ж. Полиномиальные представления булевых функций и их минимизация// Известия АН СССР. Техн. кибернетика.- 1967.- № 3.- С. 141-143.

[50] Угольников А.Б. Синтез схем и формул в неполных базисах// ДАН СССР.- 1979.- Т. 249, № 1.- С. 60-63.

[51] Угольников А.Б. О глубине и полиномиальной эквивалентности формул для замкнутых классов двузначной логики// Математические заметки.- 1987.- Т.42, № 4.- С. 603-611.

[52] Храпченко В.М. О сложности реализации линейной функции в классе П-схем// Математические заметки.- 1971.-Т.9, № 1.- С.35-40.

[53] Храпченко В.М. О сложности реализации симметрических функций формулами // Математические заметки.-1972.- Т. 11, № 1.- С. 109-120.

[54] Храпченко В.М. О сложности реализации симметрических функций алгебры логики формулами в конечных базисах// Проблемы кибернетики. Вып. 31.- 1976, - С. 231-234.

[55] Храпченко В.М. Нижние оценки сложности схем из функциональных элементов (обзор) // Кибернетический сбор-

ник. Новая серия. Вып. 21- М: Мир, 1984. - С. 3-54.

[56] Шеннон К.Э. Работы по теории информации и кибернетике- М: ИЛ., 1963.- 829с.

[57] Шестаков В.И. Алгебра двуполюсных схем, построенных исключительно из двухполюсников// Алгебра А-схем. ЖТФ.- 1941.- Т. 11, № 6.- С. 532.

[58] Яблонский C.B. Реализация линейной функции в классе П-схем// ДАН СССН.- 1954.- Т. 94, № 5.- С. 805-806.

[59] Яблонский C.B. Функциональные построения в к-значной логике// Труды математ. института им В.А.Стеклова-1958.- Т 51.- С. 2-142.

[60] Яблонский C.B. Введение в дискретную математику.- М: Наука, 1986.- 384 с.

[61] Яблонский C.B. О суперпозициях функций алгебры логики// Математ. сборник.- 1952.- Т. 30, № 2.- С. 329-345.

[62] Яблонский C.B., Гаврилов Г.П., Кудрявцев В.Б. Функции алгебры логики и классы Поста.- М: Наука, 1966.- 120 с.

[63] Akers S.J. On theory of Boolean functions// JSoc Industr and ApplMath.- 1959.- V.7, No 4.- P. 4870-498.

[64] Brayton R.K. Factoring logic functions// IBM JRes and Dev.- 1987.- V.31, No 2.- P. 187-198.

[65] Butler J.T., Herscovici D.S., Sasao T., Barton III R.J. Average and worst case number of nodes in decision diagrams of symmetric multiple-valued funcsions// IEEE Trans, on Computers.- 1997.- V. 46, No 4.- P. 491-494.

[66] Davio M. Taylor expansions of symmetric Boolean function// Philips Res. Repts.- 1973, No 28.- P. 466-474.

[67] Even S., Kohavi J., Paz A. On minimal modulo-2 sums of products for switching functions // IEEE Trans. Electron. Comput.- 1967.- V.16, No 10.- P.671-674.

[68] Fischer M., Meyer A.R., Paterson M.S., Lower bounds on the size of Boolean formulas, preliminary report// Proc. 7th Annual ACM Symposium on Theory of Computing, Albuquerque.- 1975.- P. 37-44.

[69] Fischer M., Meyer A.R., Paterson M.S., Q(nlogn) lower bounds on length of Boolean formulas// SI AM J. Comput.-1962.- V. 11, No 3.- P. 416-427.

[70] Hodes L., Specker E. Lengths of formulas and elimination of quantifiers// Contributions to mathematical logic.-Amsterdam.- 1968.- P. 175-188.

[71] Mac Williams F.J., Sloane N.J. A. The theory of error-correcting codes.- Amsterdam: North Holland Publisher Company, 1978. [Рус. пер.: Мак-Вильямс Ф.Дж., Сло-эн Н.Дж.А. Теория кодов, исправляющих ошибки.- М.: Связь, 1979.]

[72] Muller D.E. Application of Boollean algebra to switching circuit desing and error detectio// IEEE Trans. Electron. Comput.- 1954.- V.3, No 3.- P. 6-12.

[73] Perkowski M., Jozwiak L., Dreshler R. A Canonical AND/EXOR form that includes both the generalized Reed-Muller forms and Kroneker Reed-Muller forms// 3rd International Workshop on Applications of the Reed-Muller Expansion in Circuit Design, Oxford/UK- 1997- FZI report 5/97.- P. 219-233.

[74] Post E.L. Introduction to a general theory of elementary propositions//Amer. J. Math.- 1921.- V.43, No 4.- P. 163-185.

[75] Post E.L. Two-valued iterative systema of mathematical logic// Annals of Math. Studies.- 1941.- No 5.

[76] Pudlak P., Bounds for Hodes - Specker theorem// Lecture Notes in Computer Science 171, Springer-Verlag.- 1984,- P 421-445.

[77] Reed I.S. A class of multiple-error-correcting codes and decoding scheme // IRE Trans. Inform. Theory.- 1954 - V. 4, N 9.- R 38-49.

[78] Sasao T. Multiple-Valued Decomposition of Generalized Boolean Functions and the Complexyty of Programmable Logic Arrays// IEEE Trans, on Comput.- 1981.- V. 30, No 9.- P. 633-645.

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

[80] Shannon C.T. A symbolic analysis of relay and switching circuits// Trans.AIEE.- 1938.- V. 57.- P.713-723.

[81] Shannon C.E. The synthesis of two-terminal switching circuits // Bell. System. Techn. J.- 1949.- V. 28. - P. 59-98.

[82] Stetsenko V. On almost bad Boolean bases // Theoretical Computer Science. 136.- 1994.- P. 419-469.

[83] Wegener I. The Complexity of Boolean function.- Wiley-Teubner Series in Computer Science, Wiley-Teubner, 1987.

[84] Wood R.A. A Higt Density Programmable Logic Array Chip// IEEE Trans.- 1979.- V. 29, N 9.- P. 602-608.

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

[85] Винокуров С.Ф. Перязев H.A. Полиномиальные разложения булевых функций по невырожденным функциям// Алгебра и логика.- 1991.- Т. 30, № 6.- С. 631-637.

[86] Винокуров С.Ф. Перязев H.A. Представление булевых функций полиномиальными формами/ / Кибернетика и системный анализ.- 1992.- № 2.- С. 210-213.

[87] Перязев H.A. Представление функций алгебры логики бесповторными формулами //XI межреспубликанская конференция по математической логике. Тезисы докладов.- Казань.- 1992.- С. 110.

[88] Винокуров С.Ф. Перязев H.A. Полиномиальная декомпозиция булевых функций //Математические заметки.-1993.- Т. 53, Вып. 2. - С. 25-29.

[89] Винокуров С.Ф. Перязев H.A. Разложение булевых функций на сумму произведений подфункций //Дискретная математика.- 1993.- Т. 5, Вып. 3. - С. 102-104.

[90] Винокуров С.Ф. Перязев H.A. Полиномиальные разложения булевых функций / / Кибернетика и системный анализ.- 1993.- № 6.- С. 34-47.

[91] Перязев H.A. Реализация булевых функций бесповторными формулами// В кн. Методы и системы технической диагностики. Вып. 18.- Изд-во Саратовского университета, 1993. - С. 138-139.

[92] Перязев H.A. Алгебраическая характеризация бесповторных булевых функций в некоторых базисах //III международная конференция по алгебре: Тезисы сообщений.-Красноярск, 1993.- С. 260.

[93] Винокуров С.Ф. Перязев H.A. Полиномиальные разложения булевых функций по неоднородным операторам //Фундаментальные проблемы математики и механики. Математика - М.: Изд-во Моск. ун-та, 1994 - С. 317-318.

[94] Манцивода Ю.В., Перязев H.A. Значение функции Шеннона для симметрических булевых функций в классе полиномиальных нормальных форм //Сб. Алгебра, логика и приложения.- Иркутск, 1994.- С. 125-131.

[95] Перязев H.A. Реализация булевых функций бесповторными формулами / / Фундаментальные проблемы математики и механики. Математика.- М.: Изд-во Моск. ун-та, 1994.- С. 320.

[96] Перязев H.A. Сложность булевых функций в классах полиномиальных форм / / Сибирский журнал исследования операций.- 1994.- Т.1, № 1- С. 82.

[97] Перязев H.A. Реализация булевых функций бесповторными формулами в некоторых базисах // Сб. Алгебра, логика и приложения.- Иркутск, 1994.- С. 143-154.

[98] Перязев H.A. Неразделимые и квазибесповторные булевы функции// Меж д. конфер. по математ. логике. Тез. сообщений.- Новосибирск, 1994.- С. 80-81.

[99] Peryazev N. Complexity of the Boolean functions in the classes of polynomial forms //Abstracts of papers NSL'94.-Kanazawa (Japan), 1994.- C. 51.

[100] Перязев H.A. К вопросу о сложности реализации булевых функций формулами в различных базисах / /Дискретный анализ и исследование операций.- 1995.- Т. 2, № 1.- С. 78-79.

[101] Перязев H.A. Класс булевых функций с нелинейной сложностью при реализации формулами над нелинейными базисами/ / Международная конференция по прикладной логике: Тезисы сообщений.- Иркутск, 1995.- С. 60.

[102] Перязев H.A. Сложность представлений булевых функций формулами в немонолинейных базисах// Иркутский ун-тет. Серия: Дискретная математика и информатика. Вып. 2.- Иркутск, 1995. - 15 с.

[103] Перязев H.A. Сложность булевых функций в классе полиномиальных поляризованных форм// Алгебра и логика.-1995.- Т. 34, № 3.- С. 323-326.

[104] Перязев H.A. Реализация булевых функций бесповторными формулами// Дискретная математика.- 1995.-Т. 7, № 3.- С. 61-68.

[105] Винокуров С.Ф. Перязев H.A. Полиномиальная декомпозиция булевых функций по образам однородных операторов от невырожденных функций// Изв. ВУЗов. Математика.- 1996.- № 1.- С. 17-21.

[106] Перязев H.A. Описание базисов, в которых линейные функции имеют линейную сложность// В кн. Материалы VII межгосударственной школы-семинара "Синтез и сложность управляющих систем (Минск 13-16/XI 1995)".- Изд-во мехмата ф-та МГУ, Москва, 1996.- С. 23-24.

[107] Перязев Н.А., Разгильдеев BP. Число бесповторных булевых функций в бинарных базисах// Тезисы докл. XI Международной конференции по проблемам теоретической кибернетики.- Ульяновск, 1996.- С. 161-162.

[108] Перязев Н.А. Слабоповторные булевы функции в бинарном базисе// Международная конференция "Всесибир-ские чтения по математике и механики".- Томск, 1997.-С. 163-164.

[109] Mantsivoda J., Peryazev N. The Complexity of Symmetric Functions in the mod-2 Sum of Product Forms// 3rd International Workshop on Applications of the Reed-Muller Expansion in Circuit Design.- Oxford/UK, 1997.- FZI report 5/97.- P. 166-173.

[110] Винокуров С.Ф., Перязев Н.А. Полиномиальные разложения булевых функций по образам неоднородных операторов/ / Иркутский ун-тет. Серия: Дискретная математика и информатика. Вып. 3.- Иркутск, 1998.- 24 с.

[111] Перязев Н.А. Слабоповторные булевы функции в бинарном базисе // Иркутский ун-тет. Серия: Дискретная математика и информатика. Вып. 4.- Иркутск, 1998.- 12 с.