С.В. Яблонский - Введение в дискретную математику (1060464), страница 50
Текст из файла (страница 50)
сопоставлена система уравнений, которая по существу определяется системой булевых функций, входящих в их правую часть. Пример 1. а) Для схемы Е! (рис. 11) имеем систему, состоящую из одного уравнения х! л! !йУ1 ~/У! !йл! или х! л!+ ил(той 2). б) Для схемы Ел (рис. 12) аналогично получаем Л!Л! !l Хлт!. 3 а м е ч а н и е. Схему из Ф. 3. Е (л„..., х„; х„..., лл) можно рассматривать как соединение элементов г!.
Каждый элемент Е! является элементарным преобраэователем, который преобразует входной набор (о„..., ол1) в выходное значение 1л(о„ ..., о, ). В таком случае, если на входы схемы Х подать набор (а„ „ л ал), то, продвигаясь 344 ч. ч. некотогьге пР!тложеппя к кпеквпетпки от входов и выходам, оп будет переходить в набор ((в ..., у,), характеризующий состояния выходов. Оказывается, что "(, =),(ао ..., а.), '(, =),(а„..., а.), т. е. преобразование, описываемое даппымп уравнениями, соответствует нашему интуитивному представлению о функцпонпрованпп схемы пз Ф. Э.
Обозначим через 9 класс всех схем из Ф. Э. над )г. Пусть Я. — подкласс всех схем из Ф. Э. над г', у которых: 1) имеется ровно одни выход; 2) разветвления имеются только на входах. Очевидно, что Х, ж 6., а Е, Ф Я, над базисом г (см. рпс. 11, 12). Обозначим ЯИ класс формул над системой 4) (~~(х„..., х, )). Оказывается, что между классами Я„п 6й существует вполне определенная связь, которая может быть математически строго сформулирована.
Более грубо эта связь выражается следующим образом: каждой схеме Е из б, можно однозначным образом сопоставить формулу 6 из ~йй таю что по формуле 6 исходная схема восстанавливается в некотором смысле однозначно с точностью до символа, приписанного выходу. Данное утверждение мон но пропллюстрировать на примере. Рассмотрим схему Е, (см. рнс.
11). Очевидно, что Е, ы 6,. Этой схеме соответствует формула 6, гдв 6 (х! А зт2) Ч (Х! Ь У1) (см. процесс построения соответствующих уравнений). Очевидно, что эта формула позволяет восстановить структуру исходной схемы Х. Доказательство утверждения несложно. Для этого нужно сравнить определенпе схемы из Я, и формулы над соответствующей системой. В силу сказаппого схемы пз 6, поясно рассматривать как формулы илп, точнее, каь геометрические аналоги формул. Заметим, что если схема Е содержит элемент ро который па выходе имеет разветвлсние, то его можно заменить па группу элементов Гь у которых на выходах отсутствуют разветвления (см.
рпс. 15), и прп этом функционирование схемы не изменится. Эта замена по- гч. г. Сйнтез схем пз Функцпонлльньгх эле»1ентов 345 вволяет преобразовать схему Х в схему Х', фупкцпонированне которой оппсывается теин же уравнеяпямп, но пмеет разветвления только на входах. Таким образом, функциональные возможпостп класса 6 схем Х пад заданным базисом совпадают с функцноиальпымп возможностямп подкласса его всех схем, у которых разветвлскня могут быть только на входах. Каькдая схема Г кз указанного кг подкласса представляет собой «склейку» схем пз 6, своимп входами. Отсюда функциональные возможности класса 6 оп- гь ределяьотся фупкцпональпыми Рвс.
15 возможностями подкласса 6„ т.е. возможностямп 6Е. Мы доь:авали следующую теорему. Теорема 1 (о полноте). Для того чтобы ольг произвольной системы булсеых уравнений вида г, 7,(х„..., х.), г, = )»(х„..., х„), существовала схема Х(х„..., х.; г„..., г„) в исходноль базисе Ф. Э., реализуьоиьая зту систему уравнений, необходимо и достаточно, чтобы система $ 55ункпиьй ь'," была полной. Мы виднм, что связь классов 6, и 6«ь позволяет свести псследованне проблемы полноты класса 6 к проблеме полноты для формул.
Дальнейшее изложение связано с рассмотрением классов 6 схем из Ф. Э., для которых система ьР полна, $2. Проблема синтеза схем пз Ф. Э. Проблема синтеза схем из Ф. Э. состоит в следующем. Задан базис т функциональных элементов и взята произвольная система оулевых уравнений г, =),(х„..., х„), г»=/,(х„..., х„). Требуется построить схему "'(х„..., х„; г„..., гр) из данных Ф.
Э., реализующую эту снстему уравнений. 34б ч ч. некОтОРые пРилОжения.к киБеРнетике Как мы видели выше, решение проблемы синтеза существует, если система $ фувкций Д полна. Поскольку уже в случае реализации булевых функций формулами имеется много решений, то для данной системы булевых уравиевий (при наличии полноты системы $) можно построить много схем из Ф. Э., которые реализуют эту систему ураввенпй. Ввиду этого задача синтеза требует уточнения, которое позволило бы осуществлять выбор в определенном смысле оптимального решевия. Последнее может быть сделаяо следующим образом. Рассмотрим функционал г'(Х), определенный для всех Е из ю, скажем, как число влемеитов в схеме Х. Число Ь(Х) будем называть сложностью схемы.
Будем дополнительно требовать, чтобы сиитезируемая схема Е имела минимальную сложность. В дальнейшем такие схемы будем зазывать минимальными. Следовательно, теперь проблема синтеза состоит в построении минимальных схем. Ближайшая цель изложения состоит в описании алгоритма для построения минимальных схем. В связи с этим введем одно понятие и докажем три леммы. Пусть аадано я входов хй, ..., х;„, р выходов з;,, ..., х;„и г элементов Ро ..., г;, которые будут изображаться так, как это указано на рис. 16. дгздм дмгздм ,вггмздлж ''(-(Ф 9 Рвс. 16 Определение. Соединением О' данных входов, выходов и элементов называется геометрическая фигура, состоящая иа этих объектов и обладающая следующими свойствами: 4) каждый вход элементов подключен либо ко входу, либо к выходу элемента; 2) каждый выход подключен либо ко входу, либо к выходу злемеита, Гл.
г. синтез схем пз Функцпонлльных элементОВ 347 Замечание. Очевидно, схема 2(х,,, ..., хоо гел ... ..., г;„) из Ф. 3. является соединением. В то же время существуют соедянеяия, не являющиеся схемами из Ф. 3. (см. рпс. 17). Д сии а (. Число Бв(п, р, Ь) соединений с данными входами хй, ..., х~,данными выходаии гд, ..., г7„и содержащих Ь Ф. Э., занумерованных числами от 1 до Ь, не превосходит ~л(л+ Ь) где т гоах и,.
~лЙг Д о к а з а т е л ь с т в о. Каждый из Ь занумерованных элементов можно выбрать г способами, а каждый из его хг~ Ряс. $7 входов можно подключить либо к одному из входов тьн ...,хьо либо к выходу одного из Ь элементов, т. е. вход элемента может быть подключен и+ Ь способами. Всего для элемента имеется не более г(и+Ь)" возможностей. Очевидно, что каждый из выходов г>„..., г>р может быть подключен и+ Ь способами. Поэтому Бе(п, р, Ь) < ~л(я+ Ь)""+Р.
'Теорема 2. Число 8,(п, р, Ь) минимальных схем иг Ф. Э. с данными входами х<,,...,хчо данными выходами г,„...,г; и содержащих Ь Ф. Э., удовлетворяет неравенству Бв(п, Р, Ь) ( — т" (и + Ь) "+Р, Д о к а з а т е л ь с т в о. Очевидно, что в минимальной схеме на выходах разных элементов получаются разные функции от переменных хги ...,х~„(иначе один из таких элементов можно было бы удалить из схемы, и, из- 343 ч. ч пекотогьга пкнлон(кп11я к к!гвезнктнкк испив некоторые соединения в пей, сохранить ее функционирование).
Благодаря этому все Ы соединений с аапумероаанными элемеитамп, которые порождает каждая минимальная схема, различны. Отсюда н пз леммы 1 следует неравенство теоремы. Легко видеть, что определенные выше операции для логических сетей могут быть распространены и на соединения. 1.
Операция объединения двух соединений й. Применяется к двум соединениям Я' и Ю", которые не имеют общих входов, выходов п элементов. Результат операции имеет все элементы н все связи обоих соединений. Его входамп будут входы Я' и Я", выходами — выходы Я' и Я". 11. О п е р а ц и я и о д к л 1о ч е н п я э л е м е н т а. Берется соединение Я с р выходами и элемент Гь причем ги < р. В Я' выбираются п, выходов (приписанные им символы из алфавита Я исключаются) и каким-либо обрааом подключается элемент Г;, его выходу приписывается символ из алфавита Я, отличный от символов, приписанных другим выходам.
1П. Операция разветвления выхода. В соединенин К берется некоторый выход з;,, который присоединен либо к входу, либо к выходу элемента. Берем новый выход з (символ г отличен от символов, приписанных другим выходам) и подключаем его к той же вершние, что и г;,. Лемма 2. Результат применения операций 1, П, 111 к соединениям является соединением. Лемма 3.
Соединение Я, отличное от тривиальной схемы, является схемой тогда и только говда, когда выполнено хотя бы одно из условий; 1) Ю получается объединением соединений Я' и Я", которые являются схемами; 2) 8 получается из Я' путем подключения элемента Рь и Я является схелюй; 3) д получается из Я' путем разветвления его выхода, и Я' является схемой. Доказательство этих двух лемм очевидно. Теорема 3. Существует алгоритм, который для каэедого соединения д выясняет, является ли оно схемой или нет.
гл. х сннтиз схим нз функциональных влнмвнтов З4В Д о к а з а т е л ь с т в о ведется индукцией по числу й свяаей соединения Я, т. е. по суммарному числу всех входов элементов и всех выходов Я. В случае а =1 либо Я совпадает с тривиальной схемой, либо пе является схемой. Пусть теорема верна для всех а=1, ..., Х. Покажем, что она справедлива к для а 1+1. Рассмотрим соединение 8, имеющее 1+ 1 связь. Очевидно, б отлично от тривиальной схемы (а *-2). Для соединения Я возможны два случая: 1) Я не получается иа соединений с меньшим числом связей путем применения ни одной нз операций ? †1.
Тогда, очевидно, о' не является схемой; 2) Я является результатом операции кад соединениями с меньшим числом связей. В етом случае просматриваем все варяанты разложений (их конечное число) и в силу предпололгения индукцни для компонент разков~ения выясняем, будут ли опп схемами или нет. Если найдется разложение, прн котором все компоненты являются схемами, то исходное соединение по предыдущей лемме будет схемой. Если в каждом рааложении хотя бы одна на компонент не будет схемой, то исходное соединение не будет схемой.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
