Введение в дискретную математику - Яблонский С.В.
Скачать (прямая ссылка):
Л = 0, 1, 2, ...
Берем Ь == 0. Мы имеем конечное число соединений, не содержащих элементов. Для каждого соединения проверяем, является ли оно схемой или нет. Если соединение есть схема, то выясняем, реализует ли оно данную систему уравнений. Таким образом, либо мы найдем требуемую схему (она, очевидно, будет минимальной) или среди схем сложности Ь = 0 искомой схемы нет. В последнем случае минимальная схема имеет сложность ?(?)>0.
ази
М. V. нккитикьщ ПРИЛОЖЕНИЯ К КИБЕРНЕТИКЕ
Берем h = 1. Мы имеем конечное число соединений, содержащих один элемент. Для каждого соединения проверяем, будет ли оно схемой или иет. В случае, когда соединение есть схема, выясняем, реализует ли оно данную систему уравнении. В результате этого мы либо найдем требуемую схему, и она будет минимальной, либо среди схем сложностей h —0 в h = 1 искомой схемы нет. Значит, минимальная схема 2 имеет сложность ?(2)>1 и т. д. В силу полноты системы этот процесс должен окончиться, и в результате мы построим минимальную схему. Теорема доказана.
Приведенный выше алгоритм для построения минимальных схем относится к классу алгоритмов тина «полного перебора», так как он основан на просмотре всех схем до определенной сложности. Алгоритмы полного перебора, как правило, обладают большой трудоемкостью. Они, но существу, не дают возможности изучать свойства искомых объектов и непригодны для практических целей. Ввиду этого далее рассматривается более простая задача, для которой исходная система уравнений содержит одно уравнение
2 /{# 1, . ? у
и, следовательно, искомая схема 2 имеет один выход.
Сложность минимальной схемы будем обозначать через ?(/).
Кроме того, вместо синтеза схем для отдельных функций (уравнений) рассматривается задача синтеза для класса Р1п> всех функций от п переменных. При этом качество алгоритмов синтеза сравнивается путем сопоставления так называемых функций Шеннона. Более точно, пусть
L (п) « max L (/), ЬА (я) = тах ЬА (/),
/ер{п)
где La (/) — минимальная сложность схем, реализующих /, которые получаются при помощи алгоритма А.
Функции L(n), ЬА{п) называются функциями Шеннона, Они, очевидно, характеризуют сложность класса РЫ) с точки зрения реализаций его функций минимальными схемами, соответственно минимальными относительно данного алгоритма схемами, и
Ьл{п) ^ L (я).
Задача синтеза состоит теперь в том, чтобы пайтп алгоритм А, для которого ЬА(п) была бы возможно олиже к L(n) (папрнмер, LA(n)~ L{n)), н чтобы трудоемкость алгоритма А была существенно меньше, чем трудоемкость алгоритма полного перебора. Следует обратить внимание на то, что в новой постановке задачи мы не требуем, чтобы алгоритм А для каждой функции / находил минимальную схему, необходимо только, чтобы простейшая схема, получаемая при помощи А, имела сложность LA{j), сильно не превышающую L{n).
§ 3. Элементарные методы синтеза
Мы приведем несколько алгоритмов синтеза, использующих элементарные идеи, в случае когда базис F со-
Рассмотрнм разложение функции j{%\, хп) (/^ const) в виде совершенной д. н. ф.:
*
f{xx, ..Xr) = V «I1 & * *• <№” — V
{Oj,. -<Тц) »“1
f{°\..
Введем вспомогательный «элемент» (см. рис. 18), с помощью которого лei ко изобразить (см. рис, 19) схему 2*,
реализующую конъюнкцию К, где
к =? х\1 & ... & Хп
Очевидно, Ь(Хи) < п + (ft — 1), И 2* содержит подсхе-
сложность п — 1. Если «склеить» схемы 2к1, 2^, на-
чиная от входов XI, ..., хп шслоть до вспомогательных элементов, то получим схему 2 (см. рис. 20).
Мы имеем ?»{2)< п + s(n — 1). Подключая выходы схемы 2 к схеме из Дизъюякторов, мы получим схему для f(xu Хп) -(см. рис. 21).
Этим завершено описание метода синтеза по совершенной д. н. ф. (алгоритм Ai). Окончательно получаем
^Aj (/) ^ Л -t- S {п — 1) -I- $ — 1 <С п п$ = п (б + 1). Поскольку } Ф 1, то s < 2" — 1 и LAi (/) <1 п2г\ а также
*?
МУ одинаковую для всех конъюнкции и имеющую
Рис. 20
Г.И 2. СИНТЕЗ СХЕМ ИЗ ФУНКЦИОНАЛЬНЫХ ЭЛЕМЕНТОВ 353
б) Метод синтеза, основанный на более
компактной реализации множества все * , а о .
КОНЪЮНКЦИЙ I#!1 & . . .
На рис. 22 представлено индуктивное построение многополюсника 21* (« = 1, 2, ...), реализующего множе-
„ г о о .
ство всех КОНЪЮНКЦИИ I ЯД & ... & Хлп |. Мы имеем
?(2")*?(2п-1)+1 + 2я,
Ь (Еп) = 22 +...+ 2" + п - 2 ? 2й + п ~ 4.
Для построения схемы, реализующей функцию .. ., л:,,), нужно в многополюснике
2'1 отобрать выходы, соответствующие членам се совершенной д. п.ф. К{,...,Ке, подключить их к схемо (см. рис. 21), осуществляющей логическое сложение, и удалить лишние элементы. Это потребует еще не более
Б < 2я — 1
элементов V.
Таким образом, этот метод (алгоритм А2) Рис. 21
дает
?а2(/Х 3-2"+ п-5 и ?Да(л)<3.2" + п-5.
в) Метод синтеза, основанный на р а з л о-ж е н и и функции / (а*!, ..., х„) по переменному хп.
Возьмем разложение
/(^1, • • •? —1,
== &п & /(^1» * • ?> 1) V Хп & /(.ЯД, . . ,, 1, 0)
и для краткости положим
/'*=/(*!. ДТя-ь 1), Г =/(^1, - х*-ъ 0).
На рис. 23 представлена индуктивная процедура построения схемы для /.
На основе этого метода и.меем алгоритм А3:
