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