Введение в дискретную математику - Яблонский С.В.
Скачать (прямая ссылка):
21 “А(агц .. ., *„),
2,-1 Л-1 (^1, Я-П),
ъ = !Аз ......*«),
21+1 /1+1 * • *1 агй) >
2р /р (-Т[, ? . 2п) )
2рм = /1(^1, *«)•
Таким образом, каждой схеме из Ф. Э. сопоставлена система уравнений, которая по существу определяется системой булевых функций, входящих в их правую часть.
Пример 1. а) Для схемы 21 (рис. 11) имеем систему, состоящую из одного уравнения
21 = X! & х2 V#! <& хг или 2! = + аг2(тос1 2).
б) Для схемы 2г (рис. 12) аналогично получаем г 1 = х1х1 V хгх3.
Замечание. Схему из Ф. Э. 2(.г1, х„; 21, 2Р)
можно рассматривать как соединение элементов Ри Каждый элемент /ц является элементарным преобразователем, который преобразует входной набор (щ, . ..,сц) в выходное значение /“(Он ..., В таком случае, если на входы схемы 2 подать набор (се!, ..ап), то, продвигаясь
1. V. пьпи-1Ш'ЫЕ ш'ШШЖЕШШ К КИБЕРНЕТИКЕ
от входов к выходам, оп будет переходить в набор (То • ? ч Т»)» характеризующий состояния выходов. Оказывается, что
^1 = Л(«I, а»),
Кр “/р(оС|, ..ая),
т. е. преобразование, описываемое данными уравнениями, соответствует нашему интуитивному представлению о функционировании схемы из Ф. Э.Д
Обозначим через © класс всех схем из Ф. Э. над Л Пусть ©о — подкласс всох схем из Ф. Э. над у которых:
1) имеется ровно один выход;
2) разветвления имеются только на входах.
Очевидно, что 2, е ©0) а 2г ^ ©„ над базисом ^
(см. рис. И, 12), Обозначим ©^ класс формул над системой = 1/1 (Жц
Оказывается, что между классами ©0 и ©$ существует вполне определенная связь, которая может быть математически строго сформулирована. Более грубо эта связь выражается следующим образом: каждой схеме 2 из ©0 можно однозначным образом сопоставить формулу 51 из ©5р так, что по формуле 91 исходная схема восстанавливается в некотором смысле од позначно с точностью до символа, приписанного выходу.
Данное утверждение можно проиллюстрировать на примере. Рассмотрим схему 21 (см. рис. 11). Очевидно, что 2! ^ ©о. Этой схеме соответствует формула 91, где 9( = (:г, & х2) V (.т 1 & х2)
(см. процесс построения соответствующих уравнений). Очевидно, что эта формула позволяет восстановить структуру исходной схемы 2.
Доказательство утверждения несложно. Для этого нужно сравнить определение схемы из ©о и формулы над соответствующей системой.
В силу сказанного схемы из ©0 можно рассматривать как формулы или, точнее, как геометрические аналоги формул.
Заметим, что если схема 2 содержит элемент который на выходе имеет разветвление, то его можно заменить на группу элементов у которых на выходах отсутствуют разветвления (см. рис. 15), и при этом функционирование схемы не изменится. Эта замена по-
ГЛ. 2. СИНТЕЗ СХЕМ ИЗ ФУНКЦИОНАЛЬНЫХ ЭЛЕМЕНТОВ 345
8ВОЛЯЄТ преобразовать схему 2 в схему 2', функционирование которой описывается теми же уравнениями, но имеет разветвления только на входах. Таким образом, функциональные возможности класса © схем 2 над заданным базисом совпадают с функциональными возможностями подкласса его всех схем, у которых разветвления могут быть только на входах.
Каждая схема 2' из указанного подкласса представляет собой «склейку» схем из ©о своими входами. Отсюда функциональные возможности класса © определяются функциональными возможностями подкласса ©«,
т. е. возможностями (?ф. Мы доказали следующую теорему.
V Теорема і (о полноте}. Для того чтобы для произвольной системы булевых уравнений вида
2! ад),
Iр (*^і) ? • ч зд) і
существовала схема 2 (яг,, , хп\ Zp) в исходном
базисе Ф. 5., реализующая эту систему уравнений^ необходимо и достаточно, чтобы система їр функций была полной.
Мы видим, что связь классов ©о и позволяет
свести исследование проблемы полноты класса © к проблеме полноты для формул.
Дальнейшее изложение связано с рассмотрением классов © схем из Ф. Э., для которых система їр полна.
§ 2. Проблема синтеза схем из Ф. Э.
Проблема синтеза схем из Ф. Э. состоит в следующем. Задан базис Р функциональных элементов и взята произвольная система булевых уран пений
2і =}і(зси хп),
%р т ? /р • * *, •Ї'їі) .
Требуется построить схему 2(Я|, ..., хп; гі( ..., гр) из данных Ф. Э., реализующую эту систему уравнений.
346
Ч. V. НЕКОТОРЫЕ ПРИЛОЖЕНИЯ К КИБЕРНЕТИКЕ
Как мы видели выше, решение проблемы синтеза существует. если система $ функций /] полна. Поскольку уже в случае реализации булевых функций формулами имеется много решений, то для данной системы булевых уравнений (при наличии полноты системы ф) можно построить много схем из Ф. Э., которые реализуют эту систему ура в пей ий.
Ввиду этого задача синтеза требует уточнения, которое позволило бы осуществлять выбор в определенном смысле оптимального решения. Последнее может быть сделано следующим образом. Рассмотрим функционал ?(2), определенный для всех 2 из ©, скажем, как число элементов в схеме 2. Число Ь (2) будем называть сложностью схемы. Будем дополнительно требовать, чтобы синтезируемая схема 2 имела минимальную сложность. В дальнейшем такие схемы будем называть минимальными. Следовательно, теперь проблема синтеза состоит в построении минимальных схем.
