Математическая логика. Шапорев С.Д, страница 13

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

Ни первая, ни вторая возможность на схеме рнс. 1.11 не может рсвлизоватьс». Слеловательно, эта схема не является х -схемой. рлвш Г. Ля»абра латки ( л бр вы вы ныщ Рпс. 1.12 Рнс. 1.11 Две контактные схемы называ»отея зкяшоггнлтмни, если опи регшизуюг олпу и ту же булеву функцию или одну и гу гке систему ф>нкций. Схема»ызывватая ыинилныьиоб, если она содержит наименьшее возможное число контактов среди всех схем, имеющих ту гке функцию щювадимостн. Пусть /(х,,х„,х„) — булсва функция п переменных. Обозначим (срез »(/) число контактов в реализующей ес минимвлыюй схеме.

а через Ем(/) — число контактов в минимшьной я-схеме отой функции<(агав С(/) /.(/) И !9.21 Наибояьшее значегшс ь(/) для /(х,, хы,х„) назьгвастся фуллггиеи П(с»- нона 2(гг) йеличина й(/) или /ч(/) называетая слгохиасггг(ю бугеааг> функции ! в классе контактных схем ияи в кяассе я-ахем Глажяг ылыо булевой функ»щи /' в классе формул <нвд чножсством саюок (о, л, )> называется числа вхождений символов переменных. Сложность функции / а зтам классе ((гарцуя обозначается крез /чь (/) Оценим 2(п) сверху, используя ицдукп»нный способ реализации функцш(. разложим функцию /(~, х,,...,.х, ) по переменной .1»ы / = х» (ф(хыхз,....ь»)о х»ы»Р(х(х„.,х» ). Если функции ф н ф( лизованы, ю функция / реализуется, как показано нн рнс.

1 !2. Волн для реализации функций ог !с переменных требуется не более с контаюоа, то для реализации / их нугкно не более 2с»»-2, т.е. с»., <2с» 2. Так как с(=1,то с» <2 ( 2' 'т2 ь..,ь2 т2=3 2» ' — 2.Итак, Д(п) < 3. 2Я вЂ” 2 . (1 !9.3! Рдшлэ» глше в ((0(6-200»! — р ч я Часы ! Мал машчесяэя логика Рассмотрим теперь способ реализации функций, нс приводящий к г -схемам. При построении схемы с помощью СДНФ нужно отдельно решзизовать каждую юементарную конъюнкцИю, а потом параллельно соединить исс полученные схемы.

Можно, однако, реализовать асс элементарные конъюнкции олновременно. Эта делается с помощью многополкюников слслующнм абразом. Схема с л э! полюсами называется (1,1)-лщ осликом с одним входом и ! выходами. На выходах (1,1)-полюсника реализуется алновременио !с функций алгебры логики. Унивсрсатьным (1,2')-пол~асником называется ( "- 1,2")-полюсявк !рис. !.13), на выходах которого реализуются все полные правильные элементарныс конъюнкцгзи от п переменных. Рвс.!.13 Он получается при отолгдествлснии входов элементарных коныонкций !рис.

!.9! или методом, изображенным иа рис.1.!3. Укажем способ построения схемы для функции атгебры логики, использующий универсальный многополюсник. Пусть нужно реализовать функцию /(х.х„...,.т„). Представим ее в виве СДНФ. Отождествим у унилерсвльного (1,2")-полюсника выходы, иа «оторык реализуютси элементарные конъюнкции, вхолящие в СДНФ. Объявим получившийся в результате полюс выходом схемы. Эта схема, очевидно, РеализУет 2(х„хз„,,зй).

Можно похожим образом описать схему, реализующую любую булсву функцию 3'(х,хз,...,х„), разложенную в сднФ по послелним и — й псре- менным; !(хм...,хг!хян,...,х„)= о ф (хн...,хя)тгг л...лх„". П,194) /Лава !. дм евра ломки /ал сора вн азнеанид) Схема для фо1зчулы 1 19 4 состоит из двух частей !рис. 1.14) первая засть / М прсдставзяез сооой универсальный !1,2" ~-паззюснззк для персмснпьж , х,.„...,.з„. Какдый выхол схемы М, составл:твуст некоторой эясмен- с 3"" пзрной конъюнкции х,,", ох,",! л...ля" в формуле !1194! Вторая часть М представллет собой совокупность схем дял всех 2 функций ф от /т дсременных л, з„,х„у которых отождсствлены лыходы.

2л ~зз эзпх функций — коэффициенты при элементарных копыонкциях в !!.19 4!. Схема для 2(х,, х;,.... т„) конструируется слслуюшим образом: отожлсствдяется вход М„соответствующий функции ф, стояо!ей козффицимпоч при конъюнкции хз,",' лхе",з л...ля„" с вы»адач М,, озвечаюизнм этой конъюнкции. Если провести отождествление всех выхолоп М,, получим схему для функции /(т,, т,,,зй). И Р н. 1.14 Рпе.

1.15 Пример 1. Найти функпии, реализуемые схемами на рис. 1,15. Первые дес функции прсдсзавлены к-схсьзами, поэтому их восстановление довольно п!юсто: с / (х/ х ) х! х о х)х х хт х)х (х)(хз З 1)Ь!)((х Ж!)хз Э1)Ю 1 = (х,х, Ют, Оч/) (х тз ЮхзЮ1)=х, б>хз, Часы ! Матмагическае лагив во гг,.*л! - г, . *,! ц *.!Рь, .*, у П = — ((х, Ю!)(хз Ю1)Ю1)(х~хз Ю!) = (х х, Ю х, Юха Хая Ю1) Для последнего пункта составим по формуле (!.19.1> функцию проводимости. Для этого необходимо перечислить все цепи, соединяющие начальный а и конечный Ь полюсы скемьс г,(т) = ((хо х) = .

Кг. „, = х х, ч х»,; х х х, ч х х х, ч х х хз х, 4 1 и ч х х х х, и х х, ч х х, ч х х, — = х х, л х х, л х х, = (х (х, Ю1) Ю1) ((х, Ю1)х, Ю1)((х, Ю1)лз Ю!)Ю1= (л; Ю л, Ю1)(х,т, Юх, Ю!)Ю!= = хх х, Юхх, Юх Юх, =хх хЮх Юх,. Пример 2.

Построить контактную схему словщости, не превыщщощей 1, реализующую функцию ,"(,х ) = х, х, Ю х л Ю х,х, Ю1, ! = 5. Предсщвим функцию ! в базисе (ч, л, ). Рели число букв окажется равным 1, то пс«троим соответствующую схему. Если же число букв будет богжше !, то реализуем отдельные подформулы схемами и попытаемся совместить куски схем так, чтобы не возникло "ложных" цепей Так как хЮ> = ху злу,то ((хцх„х )= т х Юх х Юхх Ю!= =х(х, Юх)Юхх, = х(хха чхх)Юлх, =ххзхз гххзхз Юххз —— = (Хг Хзхз .

Х Хзяз)Х Хз Г Х Хз Ляг Хзл~ Ч Х Хзх„= Х Лзх Хз . Х ХЛХзхг Ч ч(тг чхз)(хг чхз чхзф, чхз . хз)=хл, . хх х, гх хзч тзхз . Ч тгХЛ ЧХЛХЛ = Хгта ' ХЛХЛ ЧХ1ХЛ =кто)ЧХз)Ч Х)яз. Итак, число вхождений символов переменных равно пяти. Построим теперь схему (рнс. ! .16) лля функции г (х) = х хз Ю хз.тз Ю х х, Ю 1. Ргм. 1.!Е блюя г Ллгеб а шлеи!елгебрзвы а ывенля! В! рассмотрим в закяючение метод каскадов, применяемый лля пасзроення контакгнык схем. Пусть требуется построить скому для булевой функции /(~,х„...,х„), и > 2.

Обозначим через Па ! = 1 2,...,л, совокупность всех дадфУНКЦнй Д(аи...,а,.хи,...,к„), а,п(01), уы!Л, фУНГНИИ 7 И ПУСЭЬ 17,' - множество, сасгавлевнсе из попарно различных функций из !7, Каж. доцу множеству Ьг,", г = 1,л — ! азаимно однозначно сопоставим множесизо Р; точек плоскости, называемьш егрзлэяала 7-го ралго. К ним добавляется еще три папюса. входной поззьзс и и выходные палиха Ь и с. Полюс а явдяется вершиной нулевого ранга, полюса Ь и г — всршннаьзи и-го ранга ПолюаУ и сопосзаеим фУнкци~о У(х!,хз.

ы хе), полосам Ь и с — константы ! н О, Рассмотрим мнажешео Кы (гйб,с)~ ~ьл~; и разобьем его ~ш классы эквивазентности, шгзес» к олнаму кяассу вершины разных рангов только тогда, когда они соагаезс гвуют равным функциям. Пусть т — произвольная вершина г-го ранга, а грт(лы!,л„„,лы) — соответатвуюшая ей функция. Если гр, (!,х„л,,,.,л;,)иф, (О,хыл,, зя), соединим вершину !' Ранга ! контактом лы, с вершиной и ршзга з ь1, котора» соответствует подфункции гр„(!,х„,„,ль), и конзакзом л;,, с вершиной ж, сооглстствуюцгей падфункцни гр,,(б,хыз,,хл) Гела же Ф (1 х„з,,х„) фг(б,х„л...х,), из обе падфУнкцин тождественно Рвань ФУнкади гбг(х,ьз,хгьэ,..., гя) и контакты междУ соотвеэствУюшнми аеРшинами не проводятся.

Все вершины нз одно~ о кяасса зквиваленнкюти оилкдсствляются. В резуяьтате будет получена схема Е таке», что !ад!2 )= 7(уа),а лс„(тл)ыу(ЕЯ) ВеРшина с можетбытьУдалена вмсте с инцидею ными ей кошактами. Построим с использованием метала «аскалов контактную ахему для функ- 1-з! цин 2 !т )= хытлхз ш т,х, ш хз 6! ! Выбазнм фУгзкцн~а э баз«сс зы, л. и выясним, можно ли для нее построить э -схему.

у (х!, Хз «з ) = лзх, (», 91)Ю х„ы .ь хзх, Ю л„ы .т х х. х, от х,.тз л, =- лзхлхз ы(х~ ы ха ы з'.)з, = — ахах, г хатха ля ха з ц и х,х,хз.ы з, т. хюу = хуы ху, к-схеме эгайфункпии изабразкенвна рис. ! !7. вг Чэ о С. Магемаглмесляя ловка г, Рве. 1,17 Построим теперь схему методом каскадов л = 3, с = 1 2 3; с = 1, !Сс: у (а „х„х, ), 3'(1, хз, хз) = хз сй 1, .с (О хз, хз) = хзха Ю хз ш ! с'= 2, !Сз: У(о„а„хз), 3(1,1хз)=хзф1, у(1,0 хз)=хзщ1, „'(О,1,х,)=1, 3(О,О,хз)=хзЕ!. 1=3, Ус: г(а„аз,аз). У(1,1,!)=О, Г(1,1,0)=1, У(1,0,!)=О, 3(1,0,0)=1, у'(0,1,1)=1, у(0,1,0)=о, у(о,о,!)=о,, (о,о,о)=!. 2 С(хзсо!хслЮхзсй!) !с; =),Е1,1). П; =)О!).

1 а —.«ершннанулевосоранга. ф„(1,хз,хз)=хзш1иф (О хз хз)= = хзхз шхз ш1, аледовательно, полсос а соединяется контактом х с вершиной 1, соответствующей функции ср„(1 хт,хз)= тзш!, а контактом х, с вершиной 2, соответствующей функини ф„(О хз, хз) = хзхз Ю хз Ю! (рис. !. 181. 2 ! и2 — веРшины пеРлого Ранга <Рс(! Хз)=хзсй1, сРс(О хз)=хам!,те ср„(1,Х, з,...,х„)мср„(о,х,сз,..,,хл), и вершина ! ии с какой другойс «ершиной контактами не соединяется. фз(1,хз)=1, фз(о,.тз)= хзси!, Ю,(1 хс з - «л)иф,(о,хссз,...,х„).