С.В. Яблонский - Введение в дискретную математику (1060464), страница 51
Текст из файла (страница 51)
Теорема доказана. Теорема 4. Суи1естеует алгоритм, который длл налгдой системы булевых уравнений строит минимальную схему Е. Докааательство. Пусть система уравнений имеет следующий вид: г! ~!(хо у хл)у хг = ~,(хь ..., х„). Просматриваем последовательно все соединения со входами х„..., х„и выходами г„..., г, с числом элементов Ь 0,1,2,... Берем Ь О. Мы имеем конечное число соединений, не содержащих элементов. Для каждого соединения проверяем, является ли оно схемой илн нет.
Если соединение есть схема, то выясняем, реализует ли оно данную систему уравнений. Таким образом, либо мы найдем требуемую схему (она, очевидно, будет минимальной) или среди схем сложности Ь = О искомой схемы нет. В последнеьг случае минимальная схема имеет сложность 1,(Х)) О. 350 ч. т. некОтОРые пРплопгення к кпвеРпетпкн Берем А = 1.
Ыы имеем конечное число соединений, содержащих один элемент. Для каждого соедппо)шя проверяем, будет ли оно схемой или нет. В случае, когда соединение есть схема, выяспяеы, реализует ли оно данную систему уравнений. В результате этого мы либо найдем требуемую схему, п опа будет минимальной, либо среди схем сложностей Ь= О и Ь = т искомой схемы пет. Значит, минимальная схема Х имеет ело)кность Ь(Х)>1 и т. д.
В силу полноты системы )в, этот процесс должен окончиться, и в результате мы построим минимальную схему. Теорема доказана. Приведенный выше алгоритм для построения минимальных схем относится к классу алгоритмов типа «полного перебораэ, так как оп основан на просмотре всех схем до определенной сложности. Алгоритмы полного перебора, как правило, облака)от большой трудоемкостью. Они, по существу, не дают возможности изучать свойства искомых объектов и непригодны для практических целей. Ввиду этого далее рассматривается более простая задача, для которой исходная система уравнений содер)кит одно уравнение х = ~(х„ ..., х„), и, следовательно, искомая схема Х имеет один выход.
Сложность минимальной схемы будем обозначать через ЕЦ). Крома того, вместо синтеза схем для отдельных функций (уравнений) рассматривается задача синтеза для класса Роо всех функций от л переменных. При этом качество алгоритмов синтеза сравнивается путем сопоставления так называемых функций Шеннона. Более точно, пусть Ь (п) шах Ь Ц), ).л (л) шах Ьл (Д, )аР)п) )ПРШ) где ь (~) — минимальная сложность схем, реализующих ~, которые получаются при помощи алгоритма А. Функции ) (и), Ь)(п) называются р)умкцилз)и Шемнома.
Онн, очевидно, характеризуют сложность класса Роо с точки зрения реализаций его функций мнпимальнымп схемами, соответственно минимальными относительно данного алгоритма схемами, и Е.,(п) ~ Ь(л). гл. г. синтвз схим из фтнкционлльных элкмвнтов и Задача синтеза состоит теперь в том, чтобы найти алгоритм А, для которого 1.»(п) была бы ко«мои«но олпже к г'(я) (например, Г, (л)=Ь(и)), и чтобы трудоемкость алгоритма А была существенно меньше, чем трудоемкость алгоритма полного перебора. Следует ооратпть внимание на то, что в новой постановке задачи мы пе требуем, чтобы алгоритм А для каждой функции ( находил минимальную схему, необходимо только, чтобы простейшая схема, получаемая прп помощи А, выела сложность Е*(/), сильно не превышающую Ь(я).
Мы приведем несколько алгоритмов синтеза, использующих злементариые иден, в случае когда бааис Е состоит из пнвертора, дпзъюнктора н коньюпктора. а) Метод спнтеаа, основанный на совершенной г д. н. ф. е~ги о' У юрие 1 Рис. 19 Рис. гз Рассмотри»«разлои«ение функции Г'(хо ..., х ) (Г чз сопя«) в виде совершенной д. н. фл » 1(х„..., х,) = ~/ х,'б« ... А«х" Ч К«, ( -'.1 д«« ..д~) Введем вспомогательный «элемент» (см.
рпс. »8), с помощью которого легко изобрааить (см. рпс, 19) схему Ез» 5 3. Элементарные методы синтеза / / /, / Ег / / / / 3я ч. Р. некОтОРые пРнчоженпя к кнвеРнетпкн реализующую конъюнкцию К, где а а К Е11Ь ... Ь Х„».
Очевидно, Е(Х,) < л+(л — 1), и Х, содержит подсхему Хе, одинаковую для всех конъюнкций н пмшощую сложность и — 1. Если «склспть» схемы ХЕ1, ..., Хк,, на- ЧниаЯ От ВХОДОВ Ео ..., Т„ВПЛОТЬ ДО ВСПО«ШГатЕЛЬНЫХ элементов, то получим схему Х (см. рпс. 20). Рвс. 20 Мы имеем 2.(Х) ( я+ з(л — 1). Подключая выходы схемы Х к схеме нз дпзъюнкторов, мы получим схему для Дло ..., х„) (см. рис.
21). Этим завершено описание метода спнтеаа по совершенной д. н. 4. (алгоритм А,). Окончательно получаем Ьл» Щ:~~ и + з (и — 1) + г — 1 ( и + па = и (а + 1), Поскольку 1 е» 1, то «< 2" — 1 и 1л, (~) ( л2"» а также ЬА (и) » (Н2, Гл. й. синтез схем из Функциональных элементОВ 353 б) Метод синтеза, основанный на болев компактной реализации множества всех а о конъюнкций (хт 1 тй... бтх„н) . На рис.
22 представлено индуктивное построение многополюсника Х" (л 1, 2, ...), реализующего множество всех конъюнкЦий (хттбт ... т1т х„н). Мы 1 т имеем Е(Хт) 1, ЦЕ") Е(Х" ')+ 1+ 2", Ь(Х") 2'+...+ 2" + п 2 2" + и — 4. Для построения схемы, реализующей функцию 1(х„..., х ), нуупно в многополюсннке Е" отобрать выходы, соответствующие членам ее совершенной д.н.ф. К„...,К„подключить их к схеме (см. рис. 21), осууцествляющей логическое сложение, и удалить лишние элс.у иты. Это потребует еще не более в < 2" — 1 злементов Ч. Таким образом, этот метод (алгоритм А,) Гас 31 дает Ьл,(Д(3 2" + и — 5 н Е,1, (и) (3 2" + п — 5. в) Метод сиптеэа, основанный на разложении функции 1(х„..м х.) по переменному х». Возьмем разложение у (Хтт ° т Хн-!т Хн) х„бт |(х„.. н х„„1)Чх„тй ~(х„..., х„„О) и для краткости положим У'-Яхт, ..., х.-, 1), У -У(хт, х.-о 0).
На рпс. 23 представлена ипдуктквная процедура построения схемы для 1. На основе этого метода имеем алгоритм Ас'. Ьл (1) 2, Ьлз (и) ~( 2Ьлз(п — 1)+ 4. тт Всснсннс н ннснрстную мстсмстнну и ч. у. некотОРые пРиложення к кинеРнетики Окончательно имеем К,„, (л1 < З,г" — 4. Если учесть информацию о реализации функций от двух переменных, напрпмер, что Ьл (2)~;5, то можно лУ рнВунашйнай лврвнсд йавис инУуниии Рвс.
22 сл-т сл и! и, йивис индуниии йндунтибйы й лврвнай Рве. 23 гл. з. синтвз схкм нз этнкционлльных злвмвнтов Збб получить лучшую оценку: Ля,(п) ( 2,25. 2" — 4, Итак, мы видим, что построенные алгоритмы А„А, и А, в некотором смысле дают воэможность получить все более компактные реализации для функций и, в конечном счете, все более хорошие оценки для функций Шеннона. С другой стороны, получение более хороших результатов синтеза достигается эа счет некоторого усложнения алгоритма.
4 4. Нижняя оценка для Е (и) Для того чтобы можно было судить о качестве алгоритмов синтеза, нужно анать, насколько отличается величина Ь ()) от Е()). Это сравнение осуществить невозможно, так как величина Ь~(!) вычисляется довольно сложно (например, для алгоритмов А, н А,), а Ь()) хотя и вычислима, но для большинства функций с практически недоступной сложностью, Ввиду этого качество алгоритма синтеза оценивают путем сопоставления функций Шеннона Ь~(п) н Е,(п). К сожалению, сравнивать величины Ь.,(п) и Е(п) для каждого и мы не можем, так как, хотя в.
(и) и вычисляется легче, чем Ь (1), функция Е(п) вычисляется с практически недоступной сложностью. Поэтому приходится ограничиваться асимптотическим сравнением Ь~(п) и ь(п), т. е. их сравнением при и- Напомним следующие понятия из анализа. Пусть ф(п) н ф(п) — вещественные положительные функции от натуральной переменной и. 1. Функция ф(п) аснмптотически бояыие или равна функции ф(п), т. е.
ф(п)Э ф(п), если для любого е > О найдется У )У(е) такое, что при любом п>У ф(п)> >(т — е)ф(п). 2. В случае, если ф(п)> ф(п) и ф(п)> ф(п), говорят, что ф(п) и ф(п) асимптотически равны (эквивалентны) н пишут ф(п) -ф(п). Здесь, очевидно, предел ф(п)/ф(п) существует и равен 1. 3. Если О < с, < ф(п)/ф(п)< с„то говорят, что функции ф(п) и ф(п) эквивалентны с точностью до порядка. В этом случае пишут ф(п) Х ф(п), 356 ч.
ч. некОФОРые пгиложкния к кььййгнитики Для сравнения асимптотики ь (я) и й(п) важно получить достаточно хорошую нижнюю асимптотическую оценку для 5(я) для базиса, состоящего из инвертора, конъюнктора и дизъюнктора. Теорема 5. 5(л)Э2"~я. Доказательство. Как мы видели выше (теорема 2), число минимальных схем из Ф. Э. с и входами и одним выходом (р 1), содержащих ровно Ь элементов в рассматриваемом базисе (т 2, г 3), т, е. 8,(п,1,Ь), оценивается следующим образом: 8ь(я, 1, Ь) ~ —, 3" (и+ Ь) '"+'.
Обозначим число минимальных схем из Ф. Э. с данными входамн и„..., л„, данными выходами г„..., г„содержащих не более Ь элементов, через 8(и, Р, Ь). Тогда л 8(ль Рь Ь) Х8л(ль Рь ь) Оценим сверху 8(я, 1, Ь). Мы имеем л л 8(Я,1,Ь) Я8л(нь 1, $)( ~ ~— 3~(п+ ь)ы+'~ 4-е ь-л а~(Ь+ 1) — „', 3'(и+ Ь)'"" ( —,', 3" (я+ Уь)'"+'.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
