Введение в дискретную математику - Яблонский С.В.
Скачать (прямая ссылка):
Ближайшая цель изложения состоит в описании алгоритма для построения минимальных схем. Б связи с этим введем одно понятие и докажем три леммы.
Пусть задано п входов р выходов ...
иг элементов Ри ..которые будут изображаться так, как это указано на рис. 10.
Определение. Соединением 8 данных входов, выходов в элементов называется геометрическая фигура, состоящая из этих объектов и обладающая следующими свойствами:
1) каждый вход элементов подключен либо ко входу, либо к выходу элемента;
2) каждый выход подключен либо ко входу, либо к выходу элемента,
входы
Выходы
гленеуты
Рис. 16
IV!. 2. *ЛИА1?*3 ИЛШ ПО ЧЛ'ІІГЩІїиИА.М.ЬП-ОІЛ олшпвахуд 04/
Замечание. Очевидно, схема 2(яг1, -.., хіп, 2^, ...
..., 2;- ) из Ф. Э. является соединением. В то же время существуют соединения, не являющиеся схемами из Ф. Э. (см. рис. 17).
Лемма 1. Число ?*(п, р, її) соединений с данными входами Хці .,Хіп,данными выходами Zj^r гі}) и содержащих к Ф. Э., занумерованных числами от 1 до її, не превосходит
т*{п + к)к'+*>,
где V = шах п{.
і< і<г
Доказательство. Каждый из к занумерованных элементов можно выбрать г способами, а каждый из его
V
входов можно подключить либо к одному из входов либо к выходу одного из к элементов, т. е. вход элемепта может быть подключен п 4- к способами. Всего для элемента имеется не более г(п + ку возможностей. Очевидно, что каждый из выходов может быть подключен п + к способами. Поэтому
5* (я, р,
Теорема 2. Число 30{п, р, к) минимальных схем
из Ф. Э. с данными входами данными выходами и содержащих к Ф. Эудовлетворяет
неравенству
Зй(п, Р* й)< -щ- (п + /г)Лу+р
Доказательство. Очевидпо, что в минимальной схеме на выходах разных элементов получаются разные функции от переменных хц, ...,.Г{П (иначе один из таких элементов можно было бы удалить из схемы, и, из-
Д4й
м. V пйдиштл и^шитышн л ииьк^нк! икк
меняв некоторые соединения в пей, сохранить ее функционирование). Благодаря этому все к\ соединений с занумерованными элементами, которые порождает каждая минимальная схема, различны. Отсюда и из леммы 1 следует неравенство теоремы.
Легко видеть, что определенные выше операции для логических сетей могут быть распространены и на соединения.
I. Операция объединения двух соединений. Применяется к двум соединениям 5' и 5", которые не имеют общих входов, выходов и элементов. Результат операции имеет все элементы и все связи обоих соединений. Его входами будут входы 5' и 5", выходами — вы-
С* f гг л
ХОДЫ 3 ИЙ .
II. Операция подключения элемента. Берется соединение 5' с р выходами и элемент Р(, причем П{ ^ р. В 5' выбираются п? выходов (приписанные им символы из алфавита Ъ исключаются) и каким-либо образом подключается элемент /'д его выходу приписывается символ из алфавита Ъ, отличный от символов, приписанных другим выходам.
III. Операция разветвления выхода. В соединении 5' берется некоторый выход Zjt1 который присоединен либо к входу, либо к выходу элемента. Берем новый выход г (символ г отличен от символов, приписанных другим выходам) и подключаем его к тон же вершине, что и гН * ?
Лемма 2. Результат применения операций I, II, III к соединениям является соединением.
Лемма 3. Соединение ?, отличное от тривиальной схемы, является схемой тогда и только тогда, когда выполнено хотя бы одно из условий:
1) 5 получается объединением соединений 5' и Б", которые являются схемами-,
2) ? получается из путем подключения элемента и Б' является схемой;
3) 5 получается из 8' путем разветвления его выхода, и 8' является схемой.
Доказательство этих двух лемм очевидно.
Теорема 3. Существует алгоритм, который для каждого соединения 8 выясняет, является ли оно схемой или пет.
Доказательство ведется индукцией по числу d связей соединения S, т. е. по суммарному числу всех входов элементов и всех выходов S. В случае d = i либо S совпадает с тривиальной схемой, либо не является схемой. Пусть теорема верна для всех d — 1, ..к. Покажем, что она справедлива и для d~k-\-1. Рассмотрим соединение S, имеющее к + 1 связь. Очевидно, S отлично от тривиальной схемы 2). Для соединения S возможны два случая:
1) S не получается из соединений с меньшим числом связей путем применения ни одной из операций I—III. Тогда, очевидно, S не является схемой;
2) 5 является результатом операции над соединениями с меньшим числом связей.
В этом случае просматриваем все варианты разложений (их конечное число) и в силу предположения индукции для компонент разложения выясняем, будут ли они схемами или пет. Если найдется разложение, при котором все компоненты являются схемами, то исходное соединение по предыдущей лемме будет схемой. Если в каждом разложении хотя бы одна из компонент не будет схемой, то исходное соединение не будет схемой. Теорема доказана.
Теорема 4. Существует алгоритм, который для каждой системы булевых уравнений строит минимальную схему 2.
Доказательство. Пусть система уравнений имеет следующий вид:
Zl == /i (j?l, • . 3?7l) t
}р (*^1» • • •» Я*т») *
Просматриваем последовательно все соединения со входами аГ|, ..., хп и выходами 2Ь ..., гр с числом элементов
