Введение в дискретную математику - Яблонский С.В.
Скачать (прямая ссылка):
Пусть
(^і, ? •Ї«) — столбец /-го сорта.
Обозначим через 1^(х і,...,?А) булеву функцию, определи-
ГЛ. 2. СИНТЕЗ СХЕМ ИЗ ФУНКЦИОНАЛЬНЫХ ЭЛЕМЕНТОВ 363
емую этим коротким столоцом:
У и если (Сті ... стА) = (°і (I) ... ок (/)),
I = 1.....
О, если (Оі ... о*) не принадлежит
г-й полосе.
Столбец с номером аь+1... сп разрезается полосами на р коротких столбцов. Поэтому
/ (х^, . . . ^ Хк, • > і ) Я(1) =
—/і^і» ? • •» *а) V ? • • V /р;р (*і **), (2)
где /і — номер сорта соответствующего короткого столбца, принадлежащего г-й полосе.
Таблица 4
ot(l) ... aA(i) її
ot(s) ...ab{s) V*
Теперь перейдем к описанию схемы Z. Ее мы получим в виде соединения отдельных блоков (см. рис. 27). Попутно будем оценивать сложность блоков.
1. Блок А реализует все конъюнкции Xi ? • • X<5Rh
L(A)^k2\
2. Блок В реализует все конъюнкции
L(B)<{n-k) 2П~\
3. Блок С реализует по совершенной д. н. ф. функции /в(я„ я;*)
L(C)<(s-l)(t(l)+...
.. ,+t(p))< sp2*. Рис. 27
4. Блок ?> реализует функции /(яг,, ..сйн1, ..о») на основе формулы (2)
?{D\^{p - 1)2"_* < р2п~\
364 Ч. V. НЕКОТОРЫЕ ПРИЛОЖЕНИЯ К КИБЕРНЕТИКЕ
5. Блок F реализует функцию /(#!, ..хп) исходя из ее разложения (1)
Ь {Р) < 2п~к + 2п~к - 1 < 2 ? 2П~\
Суммируя полученные оценки, имеем Ь (X) ^ к2к + {п — к) 2л~к + 8Р2* + р2п~к + 2 • 2"-\ Положим /г = [3 1о^2 я], в ~ \п — 5 п]. Тогда
Ь (X) ^ к2к + и2"“к + 2к+* 4-
причем
=<>(?). "2"" -»(?).
Поэтому
пП
В силу произвольности функции /(#!, ..жп) отсюда следует, что
071
ь (п) ^ —.
* 7 ^ п
Соединяя полученные соотношения с теоремой 2, мы завершаем доказательство.
§ 7. Синтез сумматора
Общая теория синтеза схем из Ф. Э. приводит к важному выводу о том, что большинство булевых функций (при п °°) имеет сложные минимальные схемы. Это означает, что практическую ценность с точки зрепня синтеза представляет весьма узкий класс булевых функций. Поэтому наряду с универсальными методами синтеза необходимо иметь методы синтеза, приспособлен-
Для этого рассмотрим хорошо известный алгоритм сложения чисел хну «столбиком»
(?п +1 ?» • • * Зх)
Х%1 • > • ^1
Уп • *?У1
+ 1 ^
Здесь числа qn+u • • *» ?1 обозна-
Я*/ - **
Рис. 28
Рис. 29
ные к отдельным классам булопых функций, полнее учитывающие свойства отдельных функций.
В этом параграфе мы познакомимся с одним из подходов к реализации достаточно узкого класса функций. Речь пойдет о построении мпогополюсной схемы и<1 функциональных элементов, реализующей сложении двух ми
сел, заданных в двоичной сшлсш* счисления
X — Х.цХл*. X1,
у = упуп^ ... ух.
чают результаты переносов из предыдущих разрядов (^1 = 0). Очевидно,
г{ = Xi + у1+ ^(то<3 2),
?1+1 = ЗД* V V у&.
Основываясь на тождество х1 + у, + = (од, Уед У .ад) & (ж, V г/* V д;) V
легко получить схему, реализующую соответствующее
аш Ч. V. НЕКОТОРЫЕ ПРИЛОЖЕНИЯ К КИБЕРНЕТИКЕ
преобразование величин xt, уи qt в zif ql+i (см. рис. 28). Обозначим данную схему через ?({1<1<гс), Тогда искомая схема 2П — сумматор для двух п-разрядных двоичных чисел — получается путем последовательного соединения блоков Bt (см. рис. 29). Здесь zn+1 = <jrn+1) и блок ВI осуществляет преобразование
Zj — Хх + 01 *= х{ул {Xi V yj,
Чг ~ XiUi>
Очевидно, L(Bi) — А и Л(б()= 9 при 1 < i < п. Таким образом,
?(2„) ^ 9(п - 1)+ 4 = 9л - 5 < 9п.
§ 8. Синтез схем из Ф. Э.,
реализующих симметрические функции
Другим интересным классом двоичных преобразований является класс так называемых симметрических функций.
Определение. Булева функция S(xt, хп) называется сшшетрической, если она является симметрической относительно всех переменных Xi, ..., Хп, т. е. если для любого набора (сс», ,.aft) и любой подста-/1 .,. п \
ЕОВКИ I . . имеет место
\7i < * • ]п }
^ к, * * * * ajn) “ ^ ‘ ' 1 а»).
Классу симметрических функций, очевидно, принадлежат константы 0 и 1, функции хи Xi & хя, zt V х2, xt + + Х2, XtX2 -V XiXs V Х2Х3 и т. д.
Легко видеть, что если для набора (cct, ..., ап)
S(au ..а„) = 1,
: и (ai, ..а„)’ содержит ровно i единиц, то для любого набора (сс1г , *, , ап), содержащего также ровно i единиц,
S (а!и а',) = 1.
В таком случае симметрическая функция S (г,, ..?„) характеризуется списком своих рабочих чисел iu ... ..ir(0 ц <.. .< ir < п), обозначающих число единиц в наборах (at, ..а„), для которых
S (~ti, . 1 .) ®п), 1. ^
Поэтому можно писать
— ^Д,...ДГ (“^1» * ? ч “*-«)>
где индексы (1р ..., /, — рабочие числа функции $(хи ... Например,
Х3Х2 V Х^Х-з V Х2Х3 = 52_ э (г„ Хг, Хз) .
Рассмотрим вспомогательное преобразование
(а1т . . ., аЛ) -*? /(аА ая)|
где *(«!,...,«*) — число единиц в наборе (а„ ..а»). Это преобразование будет реализовано многополюсником Х;1 из х1 функциональных элементов (ем. рис. 30), в котором на выходах 2,, 2|^2л]-Т1 по~
является двоичная запись числа а^, когда на вход поступает набор (а,, .. ., а..).
Пусть п = 2"‘. Тогда [1о§д н\ + 1 = т + 1.
Лемма 5. Можно построить многополюсник 2,,, осуществляющий в вышеуказанном смысле пресорисование
(а1, . .., од.) -> /(а1.о., ь
и ?(2'п)<18л —91оеп- 18.
Доказательство провидит с я индукцией
