Введение в дискретную математику - Яблонский С.В.
Скачать (прямая ссылка):
^А,(1) -2,
(я) ^ 2ЬА^п —* 1)+ 4,
23 С В. Яблппсш:й
354 Ч. V. НЕКОТОРЫЕ ПРИЛОЖЕНИЯ К КИБЕРНЕТИКЕ
Окончательно имеем
?*,(«)< 3.2*-4.
Если учесть информацию о реализации функций от двух переменных, например, что 7м3(2)^5, то можно
Рис. 22
Базис индукции
Рас* 23
I l У I II in i::t СХЕМ ИЗ ФУНКЦИОНАЛЬНЫХ ЭЛЕМЕНТОВ 3?5
полупив лучшую оценку:
2,25.2n-4.
Итак, мы видпм, что построенные алгоритмы А,, и^в некотором смысле дают возможность получить все более компактные реализации для функций и, в конечном счете, все более хорошие оценки для функций Шеннона. С другой стороны, получение более хороших результатов синтеза достигается за счет некоторого усложнения ал ги ритм а.
§ 4. Нижняя оценка для L (/г)
Для того чтобы можно было судить о качестве алгоритмов синтеза, нужно знать, насколько отличается величина LA(f) от ?(/). Это сравнение осуществить невозможно, так как величина LA (/) вычисляется довольно сложно (например, для алгоритмов Л2 и a L(f) хотя и вычислима, но для большинства функций с практически недоступной слоя;ностью.
Ввиду этого качество алгоритма синтеза оценивают путем сопоставления функции Шеннона ЬА(п) и L{n). К сожалению, сравнивать величины ЬА(п) п Т,{п) для каждого п мы но можем, так как, хотя LA{n) и вычисляется легче, чем />л(/), функция L{n) вычисляется с практически не доступной сложностью. Поэтому приходится ограничиваться асимптотическим сравнением LA{n) и L(n), т. е. их сравнением при /г
Напомним следующие понятия из анализа. Пусть ф(я) и ф (п.) — вещественные положительные функции от натуральной переменной п.
1. Функция ч=(к) асимптотически больше или равна функции ф(н), т. е. ф(/г)5* ^(н), если для любого f>0 найдется Л/ = Л’(е) такое, что при любом п ^ Лг ф(л)> >{1 — е) if (и).
2. В случае, если ф(п)^г|;(и) и ф(т/), говорят. что <р(гс) и асимптотически равны (эквивалент-
ны) И пишут ф(л)~ф{«). Здесь, очевидно, предел ф(л)/ф(л) существует и равен 1.
3. Если 0 < Ci < ф(л)Л]'(л)< с2, то говорят, <мп функции ср(п) и ф(п) эквивалентны С ТОЧНОСТЬЮ Ко /,о рябка, В этом случае пишут g (n)X ф{л).
23*
356 Ч. V. НЕКОТОРЫЕ ПРИЛОЖЕНИЯ К КИБЕРНЕТИКЕ
Для сравнения асимптотики ЬА{п) п Ь{п) важно получить достаточно хорошую нижнюю асимптотическую оценку для Ь(п) для базиса, состоящего из инвертора, конъюнктора и дизъюнктора.
Теорема 5. Ь(п)^2п/п.
Доказательство. Как мы видели выше (теорема 2), число минимальных схем из Ф. Э. с п входами и одним выходом (р = 1), содержащих ровно к элементов в рассматриваемом базисе (V ~ 2, г = 3), т. е. 50(н, 1,А), оценивается следующим образом:
5„(я, 1. Ь)< -д 3*(в + Л)“+‘.
Обозначим число минимальных схем из Ф. Э. с данными входами хи ..., хп, данными выходами 2„ ..гр, содержащих не более к элементов, через 5(п, р, к). Тогда
л
5 {п, р, к) = 2 5о («1 Р> О-
2=0
Оценим сверху 5(/г, 1, к). Мы имеем н л
?(и, 1, к) = 2(и. 1, *)<2тт3* + <
< (й + 1) -1.3* (п + й)“+1 < ± 3А (в + й)г'1+а.
Если к > /г, то
5 (в, 1, к) < = (12е)Л < <л>‘«
где с — некоторая константа.
Положим к = [2"/л] (при этом условие к> п выполняется, начиная с п — 5) и оценим сверху число минимальных схем из Ф. Э. сложности не более к (при п > 5). Мы имеем
/ 9П\2П/П
1, й)< (с —) ,
и, значит, минимальными схемами сложности не более к
/ 2?г\2т7«
может быть реализовано не более (с— 1 булевых
функций ог п переменных.
ГЛ. 2. СИНТЕЗ СХЕМ ИЗ ФУНКЦИОНАЛЬНЫХ ЭЛЕМЕНТОВ 357
Рассмотрим выражение / 2П>\ 2?1/п
(logac + п — log 2п) —2* =*
2п
•= — (loga с — logo??) -» ОО (при ?? —> со).
Следовательно, при достаточно большом п числитель будет меньше знаменателя. Значит, минимальных схем сложности не более к не хватает для реализации всех булевых функций от п переменных, и поэтому существуют функции от п переменных, которые не могут быть реализованы со сложностью, меньшей или равной
т. е. при достаточно больших п
Теорема доказана.
Следствие. Доля тех функций /, для которых ?/(/)> 2Vn, стремится к единице при п<*>.
§ 5. Оптимальный по порядку метод
синтеза схем из Ф.Э. (метод Шеннона)
Полученная выше нижняя оценка для L{n) показывает, что наилучшие из элементарных методов синтеза отличаются по порядку от нижней оценки в п раз. Это означает, что дальнейшее совершенствование методов синтеза может привести к уменьшению верхней оценки для функции Шеннона по порядку не более чем в п раз по сравнению с с2п. В действительности оказалось, что существует такой метод синтеза, который приводит к верхней оценке для функции Шеннона, по порядку совпадающей с нижней оценкой. Этот метод был создан К. Шенноном для контактных схем. Здесь мы изложим этот метод для реализации булевых функций схемами из Ф. Э.
Пусть {fi(xlt . . ., ..., Js(xu .. lf хп)} — множество
булевых функций (fi ч* /j при i^j).
358
Ч. V. НЕКОТОРЫЕ ПРИЛОЖЕНИЯ К КИБЕРНЕТИКЕ
Определение. Многополюсник из Ф. Э., имеющий п входов и s выходов, называется универсальным для данного множества функций, если для каждого i(l<i^s) в многополюснике найдется выход т(0 такой, что на нем реализуется функция fi(xu ..., хп).
Пример 2. Пусть {Л!,, ..it,} — множество конъюнкций. Тогда многополюсник (см. рис. 20) является универсальным для этого множества.
