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

ГОСУДАРСТВЕННЫЙ КОМИТЕТ ПО НАРОДНОМУ ОБРАЗОВАНИИ.», НАУКЕ И ТЕХНИЧЕСКОЙ ПОЛИТИКЕ ОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

На правах рукописи УДК 5X9.71:95

ВИНОКУРОВ Сергей Федорович

ПОЛИНОМИАЛЬНЫЕ РАЗЛОЖЕНИЯ К ПОЛИНОМШЛЪНМЕ КАНОНИЧЕСКИЕ ФОРШ БУЛВВДХ ФУНКЦИЙ

01.01.00.- математическая лотка, алгебра и теория чисел

Автореферат диссертации на соискание ученой стппеш! кандидата {изико-математических »пук

Омск - 19ЭЛ

ШПОАЖЬ^ ьа аягобри логаки л кибернетики

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

кандидат физяко-магеадтических неук, доцзнт Парязев Николай Алексеевич доктор фязихо-мэтематическю: наук, ведуадф научшЛ сотрудник порогов Андрей Сергеевич кандидат физнкэ-математичатошх науь доцент Мясшшов Алоксей Георгиевич

Ведущая организации - Уос.козгкий гооударственннй

унивврситот им.Я.В,Ломоносова

Защита состоится пс2(/п ^ и^е 1992г. в " № " часов на заседании специализированного совета К 064.36.0?.. при Омском государственном университете по адресу: 6*4077 г.Омск. пр.Мира ББ-А.

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

«■ О <~ '

Автореферат разослан " '" Х9Э2г.

Научные руководитель -Официальные ошюнваты -

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

В.Л.Романьков

ОЯЩЯ ХАРАКТВРКстаКА РАГОП1.

Дуальность теми. Задачи представлении функций супврпо-1ШЙИ'У злее простих фун^ргй, а также иаховдзния функцло-льннх базисов И канонических форм над этими базисами являются адициошшми в алгебре и математической логике1) .

В частности в теории булевых Функций регулярно возникает обюдимость в представлении фуягаотй формулами над различии*« зисами2). Такая потребность диктуется тагам пувктическкки ждвми в задачах синтеза логических схем3). При большом числе рэменннх становится актуальной задача декомпозиции для нижения размеров функции. В решении этих задач широко пользуются разложение Шопнона и, связанные с ним, "конъюнктивная

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

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

Мальцев А.И. Алгебраические снсгеми.-М: Наука, 1970.-392с.

Яблонский С.В.,Гаг;рилов Г. П. .Кудрявцев В .В. Функции алгебры гики л класск Поста.-М.: Кяукз, ]966.-120с.

Глушков Р.К. .Капитонова Ю.В, .."отичппский A.A. Автоматизация оакткрования вичислителышх машин.-Киеп: Науковз думка, >75.-229с.

Сапоконко Л.А.,Мухров И.П. Минимизации булевых Функций в lacce дизъюнктивных нормальных форм//'ВИНИТИ Итоги науки и хники. Теоретическая кибернетика.-1907.,-25.-С.68-116.

GC'SJ.'.p I'uSi'.MTulut '. . puJ.,..iijb'i!i!;.l OliyOJUlKJbtlii в 6). В перечисленных полшсшалиш« разложениях в качестве слагаемых используются влементарши конъюнкции. Заменой конъюнкций некоторыми булевыми функциями получаем обобщение полиномиального разложения. Такие обобщения до настоящего "времени слабо исследовались.

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

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

Цель работы. Получить и исследовать новые вида разложений %

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

J) Мачикенас Э.К.,Супрун В.II. О полиномиальном разложении булевых функций.// Дап. ь ВИНИТИ 09.03.83, М89Э-В38. -31с.

сиптемам о?пчго mmn;

- иссл<? делать операторный дотол пострл-зния стлпм фуикикй, ira котзркм вояг.ютю рчзлодоние ;

- рпссмочреть за.П'иу мшшмноош'И пролсгчплчтш г;у лорой fymttwn в илиcor полиномиальных клноничбсг.их форм;

- получить фгэрму-ти рччиолегая копф|£глц:!0нтоп кшююпопких флрм для ириг/енгшия методл детвой 'и границ т: залпчп ««шимипйшш.

Методика нсслсдглзэгагй. В днсосртпции игпользпрлпн мэтолч теории Суленнх ф'уршшй и линейной плгег;р:1.

Н&учнпл новизне к практическин ценность. Результата глло сертмип! яшттся тшми. Спи нрикчнпмч при изучеига» прелстпнлглптй Пулпвнх • Функций, п тдпччх .некс.тозицгн и иахоя'.дония мпнцмплышх фурм. Гезультнтн диссертации могут <?im. нснользопщш п алд:!-Щ7 чр< »жтироршшя ли'трртчнк иреобро-аогитолой иифррмпции.

Апробация. -Отлолълил результат>1 дяеечрт'чвш докладывались на ссллшпрпх "ЛлгпСрл и лопи;п" и "Пршслпднпл логики" Института математики СО АЛ СООГ, 1'нст;путя кибернетики ЛИ УССР, кофедрн дискретной мптоматеки Юоскеьнадго ГУ ит.1. W. Ч .Лсмсиосопс. коф?л~ pu плгсДры. логики и таОорчеижи Иркутского ГУ, IX • Ппемотаной конфорошдо! по тсор-зчической кибернетике (Волгоград ЮЭО), Международной конференции по олгогро пгл:л.чтп А. И. Ширкаю (Рорнаул I9PJ ), -I1.T конфорошц'и пч ирркллдчэЯ лопнет (ПопсспСпрск 19?2).

Публмншшл. Но T(:tœ диссертант! онуОлшсовшю 4 роботн.

Структуре и объем диосертпцта. Работа изложена нп S5 страницах, сооглит из ипедооип и дьух глшз, pmtiuTDX ва 9_ иарв-грпфер. Библиография содпрупт -13 нппменевпшнт.

• Ш>А'Л!(Ж содершш д^ссьгацли.

Во ньодошш дан краткий обзор работ на чаш диссертации, описана ее структура и основная результат». Для дальнейшего излоьшшя прил&дом иькоторие спродзмшнп.

Нагюмшш, что производной йулосой функции ____,хп) по

шромвшшм х{.....х{ (1^1 . .И^т иозыБаотси функции

/(ш} (х......х ) от числа пгцхм-эаяих, определяемая

X ...Ж 1 11

I н>

равенством:

.....

{ í • т

4 1И

где суммироьашш оьрОтся по иоьм мыЦод (о О /.

Для сокргадэиия записи «¿¡»¿и /(х.у) Оудвт ооо-ш&чагасл пил-мастная функции /(г ,.. ,.гп .<',.-■ .!',„' •

т

Еирилениб х обозначает

/ , О С1 -'1 '¡'•••О, X, 1 ■ 1 .

Пусть а>.(х ,..,1 ), ^('с оцчлии ыюжастгю

операторам (Ь), действующи на бу-кшк фушаипич

/и)-^, /(г)=/и). /(гм" /(.г), 1 1 1'« т. . . .

Ь

'""//и)-»;[1.;"":"-'/ц)], 1£{(1.р)и

* 1 ' * 1 т 1-Л 1 * * ' • ,п -х

&

V /и: .... ,х ,,.. ,х

0 ■ Г /(.чг......если 1-р;

* ...х )=-! ,

} .'v,_____с......х ), с зли 1-й.

,■'1.1 I 11 «

к 1

о- оператор будем назшжи. ог^ра'.'орои ^Цфорошшроьашы (й-оиервтораи), если г иригП».г;ет /илько ¡элачеш: «.!, к опора юром нормиросш'ил '¡>-опера одхж), ¡ьс.'ш I иршшмао? только значения р.

Функцию назог-Зм рнроулчнчой, cc.ni ,х Ы). и

нернрокдетюй в противнем случов.

ФУНКЦИЯ НЛЗЫВЛСТСЯ СЛОбО Tk'BrJpokyiC'HGfl, -1 г; ЛИ ОНИ ПОЛНЯТСЯ

невыровдэяноЯ по иевм овоим сущостввпкнм Kf»p<wnm«iM.

В гарвой глатш лиссвртп'дга» россмптрирлппгя лолгаюмиолышв

рРЗЛОГЭНИЯ булпвнх ф>.М?5!П ПО рЯЗЛИЧШ'М (Т.Г.ГГ-НПН функций, F! ТПК.ГО ПО ОССЧлиеННУМ ПОДФУНКЦИЯМ II lfOHCP'V'fWM.

В §1 двотся спят n i дост'то'я/о «ísivin ностанопку pciipoca о сущпствовэ'Ш иол1'|!стаплг Н':го ptvwm-îth по г;истог,эт функций, 'об условиях, ir» упк/гс систсму.

Тзсромя I. Яуаг'; („г,г)} - cuczv\ni су.К'Ркт функций

талая, ч;ю мщяеп J W**/ o*\wvv.u где '1а1=(£т(о,г))г.

Тог5а .«Гл1ж» cyj-yf/i Jyi-uvA f <,::,:>:) 'преСапав'ЛЮ в виде:

'7 Т

1 [аат] ч X V z - }юОсры ппрс-.кепиыг, a u г - naOopii

нанптз-л, г - nepowixip, nvwe.* niOc¡n .г,а,т едной разярр-ност, на£с.р z - пкочяволъчШ. .

Тпкоо роз-тотенпо едиистпо;пго ис оадпчной сиатэмо функций ввиду ■ 'гре^рпчия П'ЧЗ'фо^тп'Юстн матриц); . Пр.чвув чисть

полученною рчпложенпн .улмп'ои упростить путем сеодпния огроиич.эпий ип систему функций {g t.T.r)}. ¡

Теорема ?. ¡];;агь \.Rjs,r)) --сигтсма Су левых функций, npiriGn c:fi\"n^rri'"ji,yi. napùwwbi и'У'чям/ g ,'j:,r) авмюпеп г и .только fío JT , ис:ср¿¡oft» C[U"56a фунщих. fix,::) ъягт рхи<>л-с7г.»с ííu.v« •

Г

i.^-йа и ,аоли:и modаа, когда Sue фушшии сиса&ми c.taSo неби-püböüHU, ийэ^фициигипы u dee надира определены. Ö тоореме I,

В §2 изучашел noAiitioi&ic.MLHtio разложения ко системам функций, которые получены из одной новорожденной функции. Для построения таких, сиглем использовано понятие Ь-оператора на булевой функции, частым случаем которого являются операторы • диффарелцироьания и нормирования.

Теорема 3. ЛюО<ы булзда ¡¡{.нация ихеш разложения

дида:

а г

тогда и только тогда, когда g(x,r) - неЗирохденнаи функция, где

х , о

ßöt=b{x/ö,r), 7=d g(r, 1), разаерпосш набород ü теоре^.ю I,

г .

выражение bjgv{x/à,r) обозначает реьулыхдл. тюдешкзвки надо:>а о

■с ,

влезаю перелынюАХ vxiOo[xi х 6 функцию b gr(z,r).

В случао оператора нормирования коэффициенты разложения

г »

можно находить по формуле ß ^p^Jz/u.r).

Б качества следствия получается разложение Акврса ь) при g(x,r) = (x1e>ö1 ) •.. ■ -г-

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

) ÀkGris S.J. On theory о

f Boolean functions//.}.Soc. Industr. and App] .Math.-1959.-'-7,#4.-P.487-498.

8

. >. »лА

Д;ШО oiliU-aíniíJ hcü.-üp'-'iuátihühll ¿¡/tU-uy.": 'i . ..... . ■.. . -.jj.:í:¡..-формулы.

Формула г (х.....> нал сиг.гаыой ФушсциЗ 0 называется

полной, бели коадая переменная х( ьходит в ей записи, (Шлювторной, вели каждая переменная входит в ей запись но боло« одного раза, и полной бесповторной, если ровно одил раз.■ Теорема í. Нулей а фушщил f(x опр-з-Эеляе.глх

фор.хулой tir .....V ) /:а;! сшядекЯ фушц& S лб.«яж;л нейирохоь-нной, если t U'(,... ,х ) ¡иеел dui;

2т I I к

.....- g tl[xl......In) Ф g h j ( X (.....Xn).

i'-'l J=1

zda ¿ ( Tj,... ,x ) -полпиа 3i.,uv.:6n.>ixtu& фс-цщ/.ш HÍIJ miiupatâ^n-

n'unit .рункцилш из Ü, (г(,.. ,хп) - наполнив фирмули ¡uú снане.ной S. .

СК'ци.то, лк/бую itöätqirncdewiyo OxjAùèya функцию /i-,.....т )

Mox¡io пр>эдаы0шъ juzâ ciur.-ляо£1 S, ccDepKzaßü топя cu oätty невырожденную фушщде he M3HS-3 чэ:¿ о& ддус (робно m двух) переменнее, б Sitae:

к

Я-1-',.....'r„> ^^.....Ä S .....■Tn)'

' J = '

где t (г.....x )-по«ная l полная ояотюбжрнгя) формула на)

новщхг.деннэй функцией im S, h} Ц".,.. , r^) -неполные (рорлули )ию с.исаелгйй S.

Непосредственное следствие откинет невырожденные функции через полином Жэгалкнна'.

Следствие. Небирохоеннимп ôyjtoôuxii фущадияяи ядляхжиия те и только йе функции у иотарш: полином Хессшаиа содержит полную

Естественно 1:;:.'л"л: г-т!- мэлск-мпелышп разложения jt-j бя-пародч булевам функция:*. Необходимо такх» отметить еожиув роль для задач синтеза, которую игроюг фуш'Ц'.'н, преде та&ляеше йосповторыгш Формулами над Синэрнш/ги фуш'.щтач!.

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

Теорема 5. Л*х1аа "улова (¡цчкциз f[zf.....т ) и.пеет газ-

лсгенш- ('-^п

Я',.....*п>=

= л'(• • • • • '0t• • ■ '°г • ■ -V• • >-

£—' j if"

£вО л$п„ сулкироешик? dOJ.vTi'JSt по бсеж «atfopa* (о{,... ,0j ), »

т €{0,1}, rc(f (0,1), ¿f- .»лоая cuHipiaa функции, хроме эиЭиСуз.-

Aemuoc7.v.i и сложения по /toc'y.w Ckj '(1=1.....n).

t

Найлона зпяисимооть ^ и т. соотеотств?шю от функций

ТТ I

Л„к if

В §S pnccvairimuHTiifl н.)Л>агаш<ш-,ки8 {¡в&ютянкл, в которых система функц:п1 стр'ч'.гсн не гпередотвеш'о но envofl футгачги, г. именно, 15сг,о.т!Ьзуктся пч п.-дйнкцни и лраозвэдауе. Теореме в. ЛюС-пя tfynimua fix,l') илегст?

виЯа:

о г

где a f(0,1>, твори х и т, у « а »¿rem vdwiniioPyv pcsxBjMocmb с с опб явственно,

В отой теореме тек^э -приведен метод «вычисления коз№щнентои ■разложения.

to

Теорема 7. .йгЛмл ¿^-.«¡.йл /<,; илссп. ^шка^ыл}

вида:

Из теорбы 7 ьнтскаа'г ряд других разложений, лштьчукдах произьодние.

Во второй гдьъа рчоамйтрихэбютсл пояахххиь.'гишо ¡;*ксш:чск> киэ форах булшхх функций, алгоритмы ьахол.-доная ко&ффишялт'Н а задача минимизации п классах полиномиалышх канонических. фг.рм.

В §6 приведены полиномпальниз канонические фкр.лл псфсикдоомив' системами функций общего вида, а такка системами слабо к:;рекдзшшх функций. Пушоетневание таких форм хшсисиройсао и

В 37 измюд&бяш кгшошческт •рир.ы ОулеШлХ функций получение с различии;,. Ь -«»йрзт&рэг» на ¡.шсн.ост на

Ий&фЭДЫиьж фушкшй. Извеотлиа СГ;8ч>рЛ01ШМ

цорильнан форма :: псляризоьаилиЛ хютлим Яогешшиа т) яи-дои-ся честным случаем охюраторхшх форм. Нлйавиа формула дня ЕичисЛинии лоЗ!Мтз!е>аоа сшраторыхх киношно с:гш Форы, ко нсцольаугядал нахождение ойратгсЯ матрпп'л дси ¡.'.лтрицч я».: .чаш-.» функкпиД оке гег.'.и.

с) Лвааркисяк ¡\0. Сдооа-камм хл.лгльчгл^.а'-нЫч Фс^м-х оуллыхх функций к синтез ыногогахо/пшх ¿.мичкшшх ехоМ'/Авгсматса и м лимахашкь. -ТШЗ. -£Т 1.-0.1И-ПЭ.

г) МиПег Е.Е. АррИсаг1оп йсчЛи'я» ах^Ьл ю иг. 1 ьсМп^ оЦ^аП с1ез!,5:1 егшг аеьесПип >,' 1йЕ Тгапэ. ЗДесЪгоп. Соци:*.. - 1954. - • Р.ь-1 л.; н.;е«1 1.Я. А о1азв оГ

й.-л1 г 1р1 а - гггог- слг.-со*. I со^ея аг.а и.е Лс.чхИкя, яоЬйте // 1ПЬ' Тгалз. 'ГпГопл. 'Г].г.,;". 1954 •- Г', а:) 4Л.

г

Теорема в. По sxOo.ni b-о'юрстору т нзвира&Эепчой булевой функции сут'^сивуш тноничесная фор.га вида:

!{хг......V g .....гп),

где TT=di[b]g(5f.....х.п) -fix,,хг.)].

Кок следствие этой теорзми получается известное утверждение о содержании данного слагаемого в нолиноке Негзлнина

3 §8 исследованы полипемкалгныо канонические Форм;1 по формулой над множеством бинарных функций. Рассмотрены

: подставления по беспсг.торним формулам, и тонко получшш

*

условия для существования представлений такого вида по заданной формуле.

Предложение 5. Иуспь t (х ,... ,.т ) полпач Сеоповтопи.гл формула. Тогда л*х5ая булева tfywum /fxf,...,г ) преОсьъгОаяп единственным соръюл в ЯиЛе:

р.х,.....т a tu':..:,.rT").

' f Г. X I Н

0.1, -1 ' , где a -d \tU,;...,т п)-/(.т,,...,х ) .

1 х I_ ! и ' • f "J

В 59 исследуются вопрос-; представления булевых функций минимальными формзуи в классах полиномиальных кпночнчзских форм. Квк уже отг/ечалось, такая постановка задачи минимизации связана с определением широкого класса канонических предегпвло-Ш5й. Под минимальным продет ашюнием функции -понимается Формула, реализующая г данную функцию и имемцая паименилее общее число

МТёреШнних среди всех формул из определение го класса, также

■

и) Бохмапн Д. .Псстхоф X. Двоичные динамические еистемп. -М:Энергоатомиздат,1936.-101 с.

i f-1

реализующие aïy функцию. Исследаааии ыи .шмалили крадотавланая функций по b-оаэраторам, действующих па некотором множества невырожденных функций. В силу теоремы 8, в которой получены формулы для вычисления ксеффициентов канонических форм, алгоритмы нахождения _минимальных форм используют метод ветвей и границ.

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

ПУБЛИКАЦИИ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ.

1. Винокуров С.Ф., Перязев H.A. Полиномиальное -разложение булевых функций.-В кн.гМеидународнпя конференция по алгебре памяти А.И.Ширшова.Тезисы докл.по логика. Барнаул, -1991.-С.25.

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

3. Винокуров С.Ф:, Перязев H.A. Представление булевых функций полиномиальными формами//Кибернетика и системный анализ -1Э92.-Й2.-С.2Ю-213.

4. Винокуров С.Ф. Полиномиальные операторные разложения и канонические Ф9рш булевых функций.-Препринт.-Из-во Иркутского госуниверситвта.-1992.-26с.