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

1 ■ /г- г

/ о К ;,« '<

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

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

л

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

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

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

Иркутск - 1998

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

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

член-корреспондент РАН, доктор физико-математических наук, профессор Васильев С.Н.;

доктор физико-математических наук, профессор Рыбаков В.В.;

доктор физико-математических наук Пальчунов Д.Е.

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

Новосибирский государственный технический университет.

Защита состоится 2 июля 1998 г. в 14 часов на заседании диссертационного совета Д 063.32.04 в Иркутском государственном университете по адресу: 664003, г. Иркутск, бульвар Гагарина, 20.

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

Автореферат разослан 1 июня 1998 г.

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

совета, доцент

Бельтюков Н.Б.

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

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

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

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

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

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

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

В 20-40-х годах Э. Посту удалось описать все порожденные с помощью суперпозиции классы булевых функций — замкнутые классы функций2. Оригинальное детальное изложение этого результата было весьма сложно и занимало большой объем. В дальнейшем доказательство результата Э. Поста было упрощено3.

Для теории булевых функций актуальным является представление функций формулами специального вида. Хорошо известны разложение Шеннона, двойственное к нему, разложение, получаемое из разложения Шеннона заменой дизъюнкции на сложение по модулю два, разложение Акерса, а также канонические формы: совершенные дизъюнктивная и конъюнктивная нормальные формы, совершенная полиномиальная нормальная форма, поляризованные полиномы Же-галкина.

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

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

2Post E.L. Introduction to a general theory of elementary propositions//Amer. J. Math - 1921 - V.43, No 4 - P. 163-185; Post E.L. Two-valued iterative systema of mathematical logic// Annals of Math. Studies.- 1941.- No 5.

3Яблонский C.B., Гаврилов Г.П., Кудрявцев В.Б. Функции алгебры логики и классы Поста.- М: Наука, 1966.- 120 е.; Марченкоа С.С., Угольников A.B. Замкнутые классы булевых функций.- М: Ин-т лрикл математики АН, 1990.147 с.

4Глушков В.М., Капитонова Ю.В., Летичевский A.A. Автоматизация проектирования вычислительных машин.- Киев: Наукова думка, 1975.- 231 с.

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

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

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

0.Б. Лупановым7 асимптотическое выражение для функции Шеннона, используемой для оценки сложности.

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

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

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

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

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

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

ческими формами для класса К.

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

формулами, существование которых определяется решением проблем 1 и 2.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Публикации. Результаты диссертации опубликованы в работах [1-27].

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

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

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

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

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

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

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

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

Функция, получаемая из /(хх,...,х„) подстановкой вместо некоторой части переменных г,-,,..., х,т констант <г\,..., <гт, называется остаточной и обозначается так: ; число т £ {0,..., п} на-

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

Производной функции /(х1,... ,хп) по аргументу г,- называется функция= где , остаточные функции/. Это опре-

деление индуктивно распространяется на подножество аргументов. Для производной функции / по аргументам я,-,,..., г,т используется

д ^

также следующее обозначение: —-г-. Для компактной записи

дх{1...дх{т

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

.4, =/(*!,»),«£, =£,(*!. 2/)'

з/) = {¿1\;:::?-\1(хи...,хт,у)).

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

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

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

Первый критерий бесповторности получен Б.А. Субботовской6 для элементарного базиса Во в терминах забивания переменных. Другой критерий для этого же базиса получил В. А. Гурвич8 на языке дизъюнктивных нормальных форм.

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

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

Для функции /(®1,. ..,£„) введем в рассмотрение сопряженную по аргументу х; функцию

= - /¿4) V х,- - V /¿<),

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

Теорема 1. [7, 11, 20] Булева функция реализуется бесповторной формулой над множеством всех бинарных булевых функций тогда и только тогда, когда она наследственно неплотная.

Автором получен еще один критерий бесповторности в элементарном базисе в терминах невырожденности, на основании которого доказываются аналогичные критерии для базисов {•, |} и {V,

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

Теорема 2. [8, 13] Булева функция реализуется бесповторной формулой

- в базисе {-,\Л —} тогда и только тогда, когда она неконстантная наследственно невырожденная;

- в базисе {•, |} тогда и только тогда, когда она положительно и наследственно невырожденная;

- в базисе {V, 4} тогда и только тогда, когда она отрицательно и наследственно невырожденная.

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

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

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

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

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

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

A.B. Кузнецова10 о том, что любая булева функция представляется бесповторной формулой над множеством неразделимых функций "почти" однозначно.

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

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

Первым шагом в этом направлении был результат, полученный

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

10Кузнецов A.B. О бесповторных контактных схемах и бесповторных суперпозициях функций алгебры логики// Труды математ. института им.

B.А. Стеклова- 1958-Т. 51,-С. 186-225.

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

( х"\...,х"

Напомним, что функция определяемая формулой I /х,')...^»'"

которая получается подстановкой вместо переменных ц,..., хп формул я?1,...,, где

„ ( х, если (т — 1 ,. . .

х" = < _ есЛ1[ сг — 0 11 (11 > • • • 1~ произвольная перестановка чисел от 1 до п, называется обобщенно однотипной к формуле /(хг,.. .,х„). Очевидно, что отношение обобщенной однотипности является отношением эквивалентности на множестве булевых функций.

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

Теорема 5. [24, 27] Следующая система булевых функций является полной системой представителей классов эквивалентности по отношению обобщенной однотипности для булевых функций, слабоповторных в бинарном базисе Вг:

Х1Х2Х3ФХ2Х3]

х1(х2 V ¡с3) ф х2х3;

х1х2хзхА ф (жх ф х2)х3х4;

хх(х2 V 3:32:4) е (хз V х2х4);

х1(х2 V х3) V Ж3Х4;

Х1(х2 V Х3Х4) V х$(хз V £224);

жх(г2 V ... V хп) V х2 ■... ■ хп, п > 3;

V Хз ■.. .-хп) V х2 - Хз ■. ..-хп,п > 3; хг ■... ■ хпУх\ •... • х„, п > 3.

Отметим, что при доказательстве этой теоремы использовался результат В.А. Стеценко11.

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

11 Стеценко В.А. Об одном необходимом признаке для предмаксимальных базисов в Р2Ц ДАН СССР.- 199О,- Т. 315. - С. 1304-1307; Стеценко В.А. О предпло-хих базисах в Рг// Математ. вопросы кибернетики. Вып.4.- 1992.- С. 139-177.

слабоповторных функций ранга больше 4 в этих базисах совпадают (следствие к теореме 5).

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

Наиболее общая постановка задачи разложения по произвольной функции рассматривалась О.Б. Лупановым12.

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

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

Пусть наборы х,тпу,<г имеют размерность соответственно п и к. Матрицу А = [ат<7] назовем матрицей булевой функции f(x, у), если а г а = /(г, а). Столбцы А — значення /(г, а) при фиксированном <7, строки — значения /(г, а) при фиксированном т. Пусть М — квадратная подматрица матрицы А = [ау]. Определим матрицу А*(М) = [ajj] следующим образом:

. _ Г 0, если <¡ij £ М; ~ \ Mi¡, если aij g М,

где Míj — алгебраическое дополнение элемента a¡j в матрице М.

Теорема 6. [5] Для любой булевой функции f(x,y) существует разложение вида:

и т

где аТ<7 € {0,1}. При этом коэффициенты разложения можно определить следующим образом:

[я™] = А'(М),

где А — матрица функции f(x,y), М — подматрица А, соответствующая базисному минору матрицы А.

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

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

Теорема 7. [4] Пусть {дТ(х,у)} — система булевых функций, причем существенными переменными функции дТ(х,у) являются у и только те ц, которым соответствует г,- = 1. Любая булева функция ¡{х, у) имеет разложение вида

а т

тогда и только тогда, когда все функции системы невырождены. [PctY = [о<7г]-1, где <хат = {дт(<т,у))'у, у = 5о(гД), векторы х,т,а — одной, а г — произвольной размерностей.

Хорошо известно полиномиальное разложение булевых функций, получаемое из разложения Шеннона заменой дизъюнкции на "сложение по модулю 2", а также канонические формы, основанные на этом разложении: полиномиальная совершенная нормальная форма и полином Жегалкина. Опубликован целый ряд работ по минимизации таких форм, их взаимному преобразованию. Имеются обзоры результатов по полиномиальным формам такого вида13.

Однако этими разложениями далеко не исчерпываются все представления булевых функций с внешней операцией "сложение по модулю?'.

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

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

13Мачикенас Э.К., Супрун В.П. О полиномиальном разложении булевых функций// Изд-во Белорусской АН, физ-мат. лит-ра, Минск.- 1988.- 31 с; Perkowski М., Jozwiak L., Dreshler Е. 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.

Рассмотрим полиномиальные разложения следующих видов:

/(*)2/) = £>Г .....х'-.Д-г,,/) и (*)

<г

т / т { д/ \°'->° \

Д*1,...,х„) = £ £ ''•'•"■•''-•и,, дх• )

м

Если вместо многоместной конъюнкции х\ ■... • хп ■ и взять произвольную нечетную функцию д(х 1,х„, и), то можно получить разложение:

С Т

из которого получается обобщение (*), если в качестве оператора q взять оператор нормализации — р-оператор [1, 2], и обобщение (**), если в качестве оператора q взять оператор дифференцирования — ¿-оператор [4]. Дальнейшим обобщением таких разложений является разложения по однородным р^-операторам [21]. В [6] диссертантом в соавторстве с С.Ф. Винокуровым был сделан обзор по всем таким разложениям.

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

Альтернативным вложением будет называться такое отображение ф : Е" —> Е£, что фф является тождественным на множестве £¿2 , где ф : Е£ —Е" отображение, редуцированное следующим:

О —> 0,1 —> 1,2-4 0.

Если для всех ] выполняется ф(г)^ £ {0,1} или (Е {2,1}, то ф

назовем однородным вложением.

Пусть г € и г = ф(сг), где ф — альтернативное вложение. Для булевой функции /(х, у) индуктивно определим операторы следующим образом:

Р^Дх 1,у)=/(хиу), =/(хьу), ~/'Х1(Х1,у).

l.y) = f'Xl{xi,y), ptlj(xi,y) = /(*i,J/),

ptlji^uy) = f(xi,y),

dtlJ(XUy) =f(xlly), dtlj{xi,y) = /(жьу),

dtlj{*uy) =f'Xl(xuy).

где q 6 {pd,pt,dt}.

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

Матрицу [аат], где аат = (<?гЗ(х)г Ь будем называть матрицей оператора qf по функции д(х), или просто матрицей оператора, если понятно, какая функция имеется в виду.

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

Теорема 8. [21] Для любой булевой функции /, любого однородного оператора t существует разложение

f(x,z) Г К г))

т а

тогда и только тогда, когда g(x,v) — нечетная функция, где y = d°xg(x,l),ßT0 = d°ilg{x,v).

В восьмом параграфе теорема 8 обобщается на случай неоднородных операторов.

Теорема 9. [9, 26] Для любой булевой функции f(x,y), для любого неоднородного оператора из множества {pd%,ptf,dtf} существует разложение вида:

С Т

тогда и только тогда, когда g(x,v) — нечеткая функция, где Ißar]1 = [<*<rr]~\ [«от] —матрица оператора gjf по функции g'x[x,v), у = d°(g(x,l))t т,<т£Е2.

В теореме 10 этого параграфа получены формулы нахождения

коэффициентов разложения без применения операции обращения матрицы [26].

Девятый параграф посвящен каноническим полиномиальным формам булевых функций. Предельные разложения в теоремах 8 и 9 вводят широкий класс канонических полиномиальных форм. Для однородного оператора существование канонических форм доказано в теореме 11 [21].

Для неоднородных операторов теорема о существовании канонических форм выглядит так:

Теорема 12. [9, 26] Для любого неоднородного оператора q^ из множества существует каноническая форма для

множества всех булевых функций следующего вида:

№ = J>tfi(*)

т

по любой нечетной функции у(х); коэффициенты канонической формы имеют вид: уТ = (фт(х) • f(x)), где фт(х) — строки обратной матрицы к матрице оператора q^ по функции д{х).

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

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

Особенно сложно получать нелинейные нижние оценки сложности в базисах, отличных от элементарного и бинарного. Среди методов тагах оценок выделим метод Нечипорука15, Шпекера-Ходеса16, а

и Лупаноа О.Б. О методах получения оценок сложности и вычисления индивидуальных функций// Дискретный анализ. Вып. 25.- Новосибирск, 1974. - С. 3-18; Храпченко В.М. Нижние оценки сложности схем из функциональных элементов (обзср)// Кибернетический сборник. Новая серия. Вып. 21.- М: Мир, 1984. - С. 3-54; Wegener I. The Complexity of Boolean function - Wiley-Teubner Series in Computer Science, Wiley-Teubner, 1987; Нигматуллин Р.Г. Сложность булевых функций.- М.: Наука, 1991.- 240 с.

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

16Hodes L., Specker Б. Lengths of formulas and elimination of quantifiers// Contributions to mathematical logic.- Amsterdam.- 1968.- P. 175-188; Pudlak P.,

также результат Б.А. Мучник (Субботовской)17 по оценке линейной функции.

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

Приведем необходимые для формулировки этого результата определения.

Под сложностью Xе (Ф) формулы Ф понимаем число всех вхождений переменных в Ф. Сложностью L°B(f) булевой функции / в базисе В называют наименьшее значение Ь°(Ф), при условии, что формула Ф в базисе В представляет функцию /.

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

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

/, получим В ;

I /

— для каждой функции J £ В добавим к В все обобщенно одно-

н

типные функции /, получим В ;

а

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

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

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

Теорема 13, [17, 18] Пусть В произвольный нелонолинейный базис ранга к. Тогда любая булева функция f(xi,...,x„) имеет для любого т < п остаточную функцию 'такую, что выпол-

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

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

няется неравенство:

Одно из первых исследований по сложностям булевых функций было проведено применительно к линейным функциям. В 1954 году C.B. Яблонским18 была получена точная верхняя граница для сложности линейной функции в элементарном базисе, равная по порядку п2. В 1961 году Б.А. Субботовская19 получила нижнюю границу сложности линейной функции в этом же базисе порядка л3/2. Отметим что данный результат был вообще первой нелинейной оценкой в классе формульных представлений булевых функций. В 1971 году

B.М. Храпченко20 повысил эту оценку до п2, чем завершил исследования сложности представления линейных функций в элементарном базисе. Б.А. Мучник (Субботовская)17 получила в 1970 году нелинейную оценку сложности линейных функций в неполилинейных (в этой работе такие базисы назывались нелинейными) базисах.

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

Теорема 14. [18, 22] Линейные функции имеют линейную сложность отп своей размерности в базисе В тогда и только тогда, когда базис В является монолинейным.

Непосредственно полученным методом следует обобщение на более широкий класс базисов результата21 о том, что класс "почти всех" булевых функций имеет нелинейную оценку сложности во всех немонолинейных базисах [16,17]. В работе21 аналогичный результат доказан только для базиса {&, V, — }.

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

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

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

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

C. 299-306.

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

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

Пусть d(P(f)) обозначает число слагаемых в полиномиальной форме P(f) функции /. Тогда

Ll{f) = min d(P(f)),

где минимум берется по P(f) из множества Р представляющих функцию /.

L%(Kn) = max L2P(f),

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

Теорема 15. [10, 25] Функция Шеннона для множества симметричных булевых функций S в классе полиномиальных конъюнктивных нормальных форм Р вычисляется следующим образом:

г2 ее \ — / Зт" при п нечетном;

2-3» при п четном.

Классическими полиномиальными формами являются полиномиальные конъюнктивные поляризованные формы, которые также называют обобщенными формами Рида-Маллера23 или каноническими поляризованными полиномами Жегалкина.

22Even 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.

23 Reed I.S. A class of multiple-error-correcting codes and decoding scheme // IRE Trans. Inform. Theory- 1954.- V. 4, N 9- P. 38-49; Müller 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.

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

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

В работе24 получены следующие оценки для функций Шеннона в классе полиномиальных конъюнктивных поляризованных форм для множеств всех В„ и всех симметричных 5„ булевых функций:

Ь%(Вп)< 3-2""2, ьЦБп) >

В следующей теореме автором доказано, что функции Ь^(В„) и равны, а также найдена формула для их вычисления.

Теорема 16. [15, 19] Функция Шеннона для классов всех и всех симметричных функций в множестве п.к.п.ф. вычисляется так:

¿2(Вп) = 12(5п)= Г2"+11

Этот результат распространяется на более широкие классы полиномиальных форм. Классы полиномиальных канонических форм, полученные применением однородных операторов рс1, р1, «И по функции многоместной конъюнкции обозначим ОР,РТ,ОТ, соответственно, Б О — объединение этих классов.

Теорема 17. [12, 26] Значения функции Шеннона для классов всех и всех симметричных функций в множествах ОР, РТ, ИТ, БО полиномиальных конъюнктивных форм по однородным операторам совпадают и равны

г2п+1-3 '

Отметим, что из полученных результатов следует, что функция Шеннона для симметричных функций возрастает в классах полиномиальных конъюнктивных форм по однородным операторам значительно быстрее, чем в классе полиномиально конъюнктивных нормальных форм, а именно, при п оо имеет место —> 0.

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

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

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

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

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

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

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

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

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

Список опубликованных работ по теме диссертации

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

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

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

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

- С. 25-29.

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

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

- С. 34-47.

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

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

- С. 260.

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

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

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

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

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

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

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

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

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

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

- 15 с.

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

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

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

- С. 17-21.

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

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

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

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

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

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