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

РГо ОД 2 1 ДПГ 2ДП

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

Кириченко Константин Дмитриевич

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

Специальность 01.01.09 - математическая кибернетика

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

Иркутск - 2000

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

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

доктор физико-математических наук Перязев H.A.

Официальные оппоненты: доктор физико-математических

наук, профессор Морозов A.C.; кандидат физико-математических наук, доцент Дулатова З.А.

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

Институт динамики систем и теории управления СО РАН.

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

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

Автореферат разослан 19 мая 2000 г.

Ученый секретарь

диссертационного совета, к.ф.-м.н., доцент

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

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

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

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

— в том случае если такое представление существует, найти наилучший, в определенном смысле, терм, представляющий данную функцию.

Решение первой проблемы принадлежит Э.Посту1. На постановку второй проблемы повлияло то, что булевы функции являются общепризнанной моделью для проектирования электронных схем. В связи с этим, имеется большой практический интерес к нахождению термальных представлений булевых функций, имеющих наименьшую сложность. Эта проблема еще далека от окончательного решения. С одной стороны, широко известен результат О.Б. Лупанова2, который получил асимптотическое выражение для оценки сложности представлений булевых функций термами над различными полными базисами. Им доказано, что почти все булевы функции имеют сложность

Однако, C.B. Яблонский3 показал, что не существует эффективного метода задания последовательностей самых сложных булевых функций. Более того, все известные до сих пор последовательности

'Post 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.

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

3Яблонский C.B. Об алгоритмических трудностях синтеза минимальных контактных схем //Сб.Проблемы кибернетики. Вып.2.- М.:Фиэматгиз, 1959,- С.75-122.

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

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

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

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

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

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

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

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

базисы по сложности термальных представлений7.

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

Цели исследований:

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

• разработка критериев бесповторности для различных базисов;

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

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

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

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

7Субботовская Б.Л. О сравнении базисов при реализации функций алгебры логики формулами// ДАН СССР.- 1963.- Т. 149, № 4.- С. 784-787. Черухин Д.Ю. Алгоритм сравнения булевых базисов// Материалы двенадцатой международной конференции по проблемам теоретической кибернетики. - Нижний Новгород. -1999. - С. 249.

Апробация работы. Результаты диссертации были представлены на Сибирской конференции по исследованию операций (Новосибирск, 1998), Второй международной конференции "Мальцевские чтения" (Новосибирск, 1998), Двенадцатой международной конференции по проблемам теоретической кибернетики (Нижний Новгород 1999), Международной конференции по математической логике, посвященной 90 - летию со дня рождения А.И. Мальцева (Новосибирск 1999), конференции "Алгебра, логика и кибернетика", посвященной памяти А.И. Кокорина (Иркутск 1999), семинаре Института динамики систем и теории управления СОР АН, а также многократно докладывались на семинарах Иркутского государственного университета.

По теме диссертации имеется 7 публикаций [1] - [7].

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

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

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

Под базисными множестами понимаем любые множества булевых функций. Под базисами понимаем конечные полные системы булевых функций, то есть такие множества, что любая функция пред-ставима термом над ними. Для базисов < &, V, — ,0,1 > и < V, -, 0,1 > введем обозначения В0 и В\.

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

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

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

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

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

Множество булевых функций Р, содержащее тождественную функцию, называется наследственным, если верно, что для любой / £ Р, всякая остаточная f" (Е Р.

Множество булевых функций Р называется инвариантным, если для любых f(ü,y) £ Р и g(v) £ Р, где ü П ¿5 = 0 выполняется f{ü,g(v))£P.

Обозначим за Рв множество функций, бесповторных в В, за 5в

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

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

Следствие. Если для наследственного, -инвариантного множества булевых функций Р и базисного множества В с нулем и единицей верно, что В С Р и 5в П Z5 = 0, тогда Pß — Р.

Из следствия вытекает метод построения базисного множества В для произвольного наследственного, инвариантного множества Р, такого что Pß = Р.

Построение В начинаем с базиса Во, который обладает наименьшим множеством бесповторных функций из множества всех базисов, содержащих константы. Проверяем все слабоповторные в В функции на принадлежность Р и строим В' = BU(Sb ПР). Этот процесс повторяем в том случае, если Sb П Р Ф 0.

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

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

За S(f) обозначим множество фиктивных аргументов функции /, за p(f) —- множество существенных аргументов функции /.

Производной функции /(an,.. - ,хп) по аргументу Х{ называется функция fx. — /^©/¿р где остаточные функции/. Это опре-

деление индуктивно распространяется на подмножество аргументов.

Булеву функцию /, rang(f) > 1 будем называть твердой, если

8Субботовская Б.А. О сравнении базисов при реализации функций алгебры логики формулами// ДАН СССР - 1963 - Т. 149, № 4.- С. 784-787. Гурвич В.А. Критерий бесповторности функций алгебры логики// ДАН СССР.- 1991,- 318, №3.- С. 532-537. Перязев H.A. Реализация булевых функций бесповторными формулами// Дискретная математика,- 1995.-Т. 7, № 3.- С. 61-68.

для любой существенной переменной х выполняется условие 1 и одно из условий 2,3.

1) ад = *(/)■

2) ад = <*(/) и ад = *(/).

3) ¿(л с ад и 5и) с ад.

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

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

Теорема 2. Функция / является наследственно нетвердой тогда и только тогда, когда / бесповторна в базисе В\.

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

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

За В~ обозначим максимальный из базисов В1 С В*, такой что в В' функция д не представляется бесповторно.

Легко доказать, что если функция д £ В*, то д слабоповторна в

в7-

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

Пусть д некоторая функция, В — базис, д £ В*, и гапд(д) = гапд(В*), тогда за Бяв обозначим множество булевых функций, слабоповторных в В, но не слабоповторных в В~;

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

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

Определим:

а _ Г х, если а — О, ~ \ х, если сг = 1.

Функции / и д называются однотипными, если выполняется д(х) — /г^..(5), где ¿5,..., ¿„ некоторая перестановка 1,..., п, а

" получается из / подстановкой вместо Х\,... ,хп термов xf',.. ■ ,xf\ В противном случае функции неоднотипные.

Функции fag называются обобщенно однотипными если / однотипна к д, или / однотипна к д.

За v обозначим множество переменных Vi,... ,vn, при этом |«| — п; за &wCT обозначим терм i^1 ■ ... • ; за Vva обозначим терм 1 V ... V .

Теорема 3. Для любой булевой функции /* £Sfj, такой что rang(f *) > гапд(В*) + 2, найдется обобщенно однотипная к ней функция /, которая может быть задана одним из следующих термов:

1) }{щ,...,йк,Х1,...,Хп^к) =

= P((VU!) V ... V (Vut), (&5i), ■ • •, (&Si). • • •> «п-0»

где p(l,уь ..., y„) = ¿/(г/ч, • • •, ¡/¿J;

2) /(ai!,..., xjb, xjt+i, arjt+n) =

= t(x i,.. ,,xk,g(xk+i, . . .,Xk+n), Kxk + i, • ■ •, ®*+rj)), где t(x\,..., Xk, z\, ¿2) такая что для любого i < к переменная z\ фиктивна в остаточной tJ , a z^ — в остаточной t\...

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

Теорема 4. Множество S9B конечно, и для любой функции f (В SgB выполняется rang(f) < (rang(B*))2 тогда и только тогда, когда в множестве Sg отсутствуют функции t(H, 1/1,2/2), wo-кие что rang[t) < (rang(B*))2 и для любой переменной х £ й и константы г, переменные y\,yi выделимы б = р(й, /i(j/i, 2/2)) « функция h равна либо ух ■ уч, либо yi ■ У2, либо у\ V У2, либо yi V г/г-

Следствие 1. Множество Sg конечно, если для д(х\,... ,хп) выполняется следующее свойство: для любой переменной ж,- найдется переменная Xj, такая что для любой константы сг в остаточной /¡Г будет существенна переменная Х{.

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

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

втпорных в Во конечно.

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

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

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

Заметим, что для одного из предэлементарных базисов, а именно для базиса Bi = В^{^1X7^X1X2} описание слабоповторных функций было сделано H.A. Перязевым10.

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

Всякий базис BaL){g], гдед — х\-.. ,'ХпУх\-. . --Хл для п > 2будем называть предэлементарным симметрическим базисом порядка п.

Всякий базис Во U {р}, где g = х^ ■ . ■ ■ ■ хп V х\ (х2 V ... V хп) для п > 3 будем называть предэлементарным монотонным базисом порядка п.

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

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

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

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

xi(x2 VZ3) V Х3Г4;

xi(x2 V Х3Х4) Vx5(x3 V x2x4); xi(x2V...Vxn)Vx2-...-xn, Xl(x2 V13 • . . . • Г„) V X2 ■ ¿3 ' ■ Xi ■... ■ хп V ¿1 ' ... -xn,

n 1

n> 3; .-rn, n > 3; n > 2.

1998.- 12 c.

п, где п > 3:

xi(x2 V х3) V х3х4;

Xi(l2 V Х3Х4) V х5(х3 V z2x4);

xi(x2 V ... Vxn) Vx2 ■ • ■ ■ • Xfc, к > 3;

х^хг V х3 •... • Xjt) V x2 ■ x3 - ... ■ xk) к > 3;

£i •... ■ xn V ¿i • ... ■ xk, к >3,к ф n;

xig(x2,.. - ,xn+i) V xi ■ ... • xn+i;

£1 ■... • xn-ig(xn,..., x2n-i) V xi ■... ■ X2n-i\

xi •... • xng(x„+1,... ,x2„) V xi • ... • x2rl;

¿1 • • • • • Ёп/2Я(хп/2+1, • • - , ^Зп/2) v Xj ■ . .. • xn • xn+i •... • x3„/2 четных n;

¿i ... ■ xn/7g{xn¡ 2+1,.. ., x3n/2) V

Vxí •. ■ ■ ■ xn/2g(xn/2+i, ■ ■. ,xn,xn+i,... ,x3n/2)

при четных п.

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

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

xj(x2 V х3) V х3х4;

xi(x2 VX3X4) Vx5(x3 VX2X4);

xi(x2 V ... V xn) V x2 - ... -Xfc, k > 3 , k ф n;

xi(x2 V x3 • ... • xk) V x2 • x3 •... -xk, k > 3;

Xx •...•xfJ Vi, •...•xt, k > 2;

xig(x2l ...,xn+i) V xix2(x3 V...Vrn+1);

x1g(x2,...,xn+i) V xi ■ ,..-xn+i;

¿1 g{x2,. ,.,xn+1) V xix2(x4 V ... V xn+1);

xlg(x2,. ..,хп+г) V xix2;

x1x2g{x3, х4,х5) V xj((x2 Vx3)x4 V x5).

Отметим, что при к > 1п множества слабоповторных функций ранга к для Во и предэлементарного симметрического базиса порядка п совпадают, для предэлементарного монотонного базиса ранга 3 множество слабоповторных функций ранга более чем 5 совпадает со множеством слабоповторных функций для Во, для предэлемен-тарных монотонных базисов ранга п > 3 множество слабоповторных функций ранга большего чем п+ 1 совпадает с аналогичным множеством для В о.

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

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

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

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

3. Доказаны некоторые свойства слабоповторных булевых функций в произвольных небинарных базисах.

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

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

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

[1] Кириченко К.Д. Свойство слабоповторных булевых функции в различных базисах// Сибирская конференция по исследованию операций. - Новосибирск. - 1998. - С. 127.

[2] Кириченко К.Д. О слабоповторных булевых функциях в некоторых базисах// Международная конференция по математической логике. - Новосибирск. - 1998. - С. 29.

[3] Кириченко К.Д. Свойства слабоповторных булевых функций в небинарных базисах// Двенадцатая международная конференция по проблемам теоретической кибернетики. - Нижний Новгород. -1999. - С. 93.

[4] Кириченко К.Д. Слабоповторные булевы функции в некоторых предэлементарных базисах // Иркутский ун-тет. Серия: Дискретная математика и информатика. Вып. 13 - Иркутск, 2000.-

[5] Кириченко К.Д. О критериях бесповторности булевых функций в различных базисах// Оптимизация, управление, интеллект. 2000, N 4 - С 186-192.

[6] Кириченко К .Д. Критерий бесповторности функции алгебры логики в бинарном базисе// Международная конференция "Логика и приложения". - Новосибирск. - 2000. - С 57-58.

[7] Кириченко К.Д. Слабоповторные булевы функции в небинарных базисах// Иркутский ун-тет. Серия: Дискретная математика и информатика. Вып. 14 - Иркутск, 2000 - 20 с.

60 с.