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

Иркутский государственный университет

На правах рукописи

Перязев Николай Алексеевич

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

формулами

01.01.09 - математическая кибернетика

Диссертация на соискание ученой степени доктора физико-математических наук

Иркутск - 1998

Оглавление

Введение ...................................................... 4

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

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

функций............................................... 13

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Заключение ................................................... 155

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

Введение

Изучение теорий функциональных систем образуют одно из главных направлений в математике. Теория конечно-значных функций наряду с теорией графов является универсальным аппаратом описания конечных моделей в дискретной математике и математической кибернетике. Изучение таких функциональных систем связано с именами целого ряда выдающихся математиков. Среди них Дж. Буль, Г. Фреге, А. Пирс, М. Шеффер, П.С. Порецкий, Е. Пост, К. Шеннон, И.И. Жегал-кин, А.И. Мальцев, В.М. Глушков, 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).

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

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

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

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

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

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

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

1.1. Основные понятия и определения. Размерностью (сИт(/)) булевой функции / называют число ее аргументов, а, рангом (гапд(/)) число ее существенных аргументов. Булева функция называется существенной, если она не содержит фиктивных аргументов, то есть ее размерность совпадает с рангом, в противном случае она называется несущественной.

Булевы функции эквивалентные функциям размерности 0,1,2 называем, соответственно, константными, унарными, бинарными. Бинарные функции, за исключением линейных функций ранга 2, называем элементарными.

Булева функция называется разделимой [22, 39], если ее можно представить в виде суперпозиции двух неунарных функций с непересекающимися множествами аргументов. В противном случае функция называется неразделимой.

Функция называется остаточной функции /, если по-

лучается из f(xi,. .., а;п) подстановкой вместо некоторой части переменных X(v .. ., жг-то констант crl5..., crm, и обозначается так: Д1''"'^™ ; число m G {0,..., п} называется порядком остаточной функции; если m ф 0, то остаточная функция называется собственной.

Производной функции f(x 1,. . ., жи) по аргументу Ж; называется функция }'х. = Д 0 Д, где Д, Д. остаточные функции /. Это определение индуктивно распространяется на под-ножество аргументов [9, 63].

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

Существенные невырожденные функции называются нечетными, все остальные — четными. Эта терминология отражает количество единиц в векторе значений функции.

Булева функция называется монолинейной, если можно обобщенным отождествлением некоторого подмножества ее аргументов (возможно пустого) получить неунарную линейную функцию. Если это можно сделать обобщенно отождествляя произвольное число подмножеств аргументов, то такая функция называется полилинейной. Ясно, что линейная функция является монолинейной, которая в свою очередь является полилинейной.

Под базисами понимаем конечные полные системы бу-

левых функций. Функции, принадлежащие базису, называем базисными. Наибольший ранг (размерность) базисных функций определяет ранг [размерность) базиса.

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

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

— для каждой функции / Е В добавим к В все остаточные функции /, получим В

— для каждой функции / Е В добавим к В все обобщенно однотипные функции /, получим В ;

— исключим из В все разделимые функции, получим В*.

Базис В называем линейным, монолинейным или полилинейным, если приведенный базис В* содержит, соответственно, неунарную линейную, монолинейную или полилинейную функцию. Заметим, что неполилинейные базисы в работе [34] называются нелинейными.

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

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

Под сложностью Ь°(Ф) формулы Ф понимаем число всех вхождений переменных в Ф, а под сложностью — число всех неунарных базисных функций входящих в Ф. Сложностью £#(/) или £#(/) булевой функции / в базисе В называют наименьшее значение £°(Ф), соответственно Ь1(Ф), при условии, что формула Ф в базисе В представляет функцию /. Формула Ф, на которой достигается наименьшее значение сложности, называется минимальной.

Число слагаемых в полиномиальной форме Р(/) функции / обозначается через ¿¿(Р(/)).

Функция Шеннона [28] для оценки сложности представления классов К булевых функций от п аргументов в множестве полиномиальных форм Р определяется следующим образом:

12Р(/) =тт4Р(/)),

гд�