Введение в дискретную математику - Яблонский С.В.
Скачать (прямая ссылка):
Лемма 4. Для любого п можно построить универсальный многополюсник Un для множества всех булевых функций от п переменных
L{1771)<2-22П,
Рас. 24 Доказательство. Построение
многополюсника Un будем осуществлять индуктивным способом.
Базис индукции (ц = 1). В качестве UL возьмем многополюсник, изображенный на рис» 24. Мы имеем L(U1) = S<2‘2*\
Индуктивный переход. Предположим, что построен универсальный многополюсник для множе-
ства всех булевых функций, зависящих от переменных
2i, хп-и и I (?/„_:)< 2.22 .Рассмотрим разложение
/("^li • • ч Хц— 1, Хп) xj (Xj, . . ,, Хп— i) V Xrtf (Х\, • . i, — 1) ?
Множество всех булеЕЫХ функций, зависящих от переменных хи ..хп, разобьем на три непересекающихся класса.
I. f =/" s0. Этот класс содержит одну функцию / = 0.
II. Ровно одна из функций f или f" тождествеино равна 0. В этом классе содержатся функции / вида
или
/ = xnf (гс1р ..xn-i) (/' Ф 0)
f-ХпПх, (Г* 0),
<г. е. 2 (2г — l) функций.
ГЛ. 2. СИНТЕЗ СХЕМ ИЗ ФУНКЦИОНАЛЬНЫХ ЭЛЕМЕНТОВ 359
III. Всеуостальные функции, т. е. функции /, у которых ГФЪжГ'Ф 0.
В этом классе имеется
22" — 2 — 1) — 1
функций.
На рис. 25 изображен многополюсник VЗдесь выходы многополюсника 11п-1 занумерованы числами
Рис. 25
1, ...,2а * причем считается, что на выходе 1 реа-
лизуется константа 0.
Выходы многополюсника 1)п разбиты на три класса в соответствии с разбиением множества всех булевых функций, зависящих от переменных хи ..хп. Данный многополюсник содержит;
360 ч. V. НЕКОТОРЫЕ ПРИЛОЖЕНИЯ К КИБЕРНЕТИКЕ
а) подсхему ип~1 и вне ее еще
б) один инвертор,
в) 2 (2 — 1) конъюнкторов,
г) 22 1 — 2 (22’1 1 — 1) — 1 дизъюпкторов.
Таким образом,
Ь (и„)=*Ь(?/„_,) +1 + 2(23"-1 - 1) + 2!" - 2 (23""' - 1) -— 1 = ?({/„-,) + 2г" + 2г” <2-2гП.
Лемма доказана.
Теорема 6 (К. Э. Шеннон [34]). Существует метод > синтеза (алгоритм ЛД, который . для каждой булевой функции /(х,, ..., х„) позволяет построить схему из Ф. Э. сложности ^а4(Л и
ЬА4(/(я?!, .. .,х«)) ^ 8~-
Доказательство. Возьмем разложение
/ (х1} ..., х„)= \/х^,^ • • • &яу* &
<С1..°й)
& / 0^1) • ? * , Щ . . . , Хл)-
Рассмотрим схему 2/, изображенную на рис. 26.
Ук — многополюсник, универсальный для множества всех конъюнкций к01...ам гДе
'^(Т1...сй= X . . . & X й
1 Я 1 н
(к — фиксированное число). В качестве В* взята схема 2й (см. рис. 22).
Рис- 26 ип-к — многополюсник, уни-
версальный для множества всех булевых функций, зависящих ОТ переменных Ха+1, ..., хп. Через т(<ц, ..., оА) обозначен его выход, на котором реализуется функция
/(01, • • *, ак> .,,, хп),
ГЛ. 2. СИНТЕЗ СХЕМ ИЗ ФУНКЦИОНАЛЬНЫХ ЭЛЕМЕНТОВ 381
Легко видеть, что данная схема 2/ реализует функцию /(#!, ..., хп) в соответствии с приведенным выше разложением. Оценим сложность
L (?,) < L (У*) + L+ 2-2" — 1 < 2-2* +
-4 + 2.23"-'' + 2-2k -1 =4-2'1 + 2.2“”''' + 4-5.
Подберем параметр к таким образом, чтобы правая часть этого неравенства стала возможно меньше. Так как нас интересует порядок величины La4(/), то, вместо минимума правой части, который в дискретном случае вычисляется сложно, мы возьмем значение правой часта при т = [log^rc — 2 log2 и)], где т — п — к. Это значение подбирается, исходя из следующих соображений:
с ростом к член 4 * 2* возрастает, а член 2-22 убывает, и минимум достигается, когда оба члена становятся близкими друг к другу.
Мы имеем ~ (п — 2 log и) < 2т < (/г — 2 log п),
г I о о2те 4-2" 2П 2п
+ 2-2г а;1---------------------+2±-^8±~.
~2~ ^ П П
Следствие. Учитывая пижюю оценку, мы получаем
2п
и, значит, алгоритм Лк является наилучшим по порядку.
§ 6. Асимптотически наилучший метод
синтеза схем из Ф. Э. (метод Лупанова)
Первым асимптотически наилучгаим методом синтеза для реализации всех булевых функций был метод Лупанова, который был сначала сформулирован для контактных схем и затем им же был распространен на схемы из Ф, Э.
Теорема 7 (О. Б, Лупанов [18]). Для схем из Ф.Э, в базисе, состоящем из инвертора, дизъюнктора и конъ-юнктора, можно построить асимптотически наилучший метод синтеза и
г , ч 2п
362 Ч. V. НЕКОТОРЫЕ ПРИЛОЖЕНИЯ К КИБЕРНЕТИКЕ
Доказательство. Зададим произвольную булеву функцию хп) при помощи таблицы размера
2*Х2"-* (см. табл. 3).
Таблица 3
Строки этой таблицы нумеруем наборами значений по переменным хи ..., хк, столбцы — по переменным лй+1, . . . ..хп. На пересечении строки (щ, ..., щ) и столбца (сй+,... о„) помещаем значение /(а±.........ой, сй+1, ..о„).
Легко видеть, что столбец с номером сй+1, ..о„ задает функцию 1{хи ..., хкі ак+1, а„), являющуюся
компонентой разложения
/(«і, * * •> яп)
= V хвк)Х1 - ? • <”/ К, ? . ?, ®к. <**+!, . . -, оп). (1)
Возьмем целое число в, 1 < ж < 2й, и разрежем таблицу на полосы шириной я (см. табл. 3). При этом последняя полоса может оказаться меньшей ширины я' (я'<я). Занумеруем сверху вниз полученные полосы числами 1, 2, ..., р, где р = ]2*/я[, и рассмотрим полосу с номером і (см. табл, 4) и строками (Оі(!)... 0*(1)), ...
(0,(і)...0А(в)).
Эта полоса распадается на короткие столбцы высоты я для последней полосы — высоты я'. Поэтому число 1(1) сортов коротких столбцов будет не более 2\ Произведем нумерацию втих сортов числами 1, 2, ..., ?(і).
