С.В. Яблонский - Введение в дискретную математику (1060464), страница 49
Текст из файла (страница 49)
н. ф. типа ХТ являются локальными и произведем оценку их параметров. В алгоритме Квайна сначала выявляются ядровые конъюнкции. Для этого необходимо знать окрестности первого порядка конъюнкций в сокращенной д.н. ф., и запоминать отметки: если конъюнкция не ядровая, то отметка О, если — ядровая, то отметка 1. Для принятия решения о возможности удаления конъюнкции надо опять знать ее окрестность первого порядка и посмотреть, покрывается ли она отмеченными конъюнкциями нз этой окрестности. Таким образом, мы имеем локальный алгоритм с параметрами и = 1, Р— 1. В алгоритме построения д. Н.ф. типа ХТ сначала определяют, является ли данная конъюнкция регулярной.
Для этого нужно сравнивать пучки, проходящие через точки данной грани (конъюнкции) и пучки, проходящие череа точки из окрестности 1-го порядка данной грани и не лежащие в ней, т. е. оперировать с окрестностями 2-го порядка. Регулярная грань помечается символом 1, 336 ч ч нвкотогык пгилояглппя к пппкгпзтш'и грань, не являющаяся регулярной,— О. Затем пропсходит принятие решения: удаляются граню с пометкой 1 (регулярные). Итак, в этом случае мы имеем локальный алгоритм с параметрами и = 2 л о = 1.
На основании обсуждеппй мы видим, что локальные алгоритмы охватывают многие известные классы алгоритмов. С другой стороны, локальные алгоритмы с параметрами и и о являются алгоритмами с ограниченной трудоемкостью. Глава 2 СИНТЕЗ СХЕМ ИЗ ФУНКЦИОНАЛЬНЫХ ЭЛЕМЕНТОВ В современной технике управляющих и вычислительных устройств важное место занимают дискретные преобразователи, т. е. устройства (см.
рис. 1), которые обладают некоторым числом входов и выходов. Наборы и сигналов, поступающие на входы и возникающие ка выходах, прпнадлежат известным конечным м- г мнолсествам. Устройства осущеРис» 1 сталя»от преобразования входных наборов сигналов в выходные. Интересным подклассом дпскретных преобразователей является класс устройств, в которых время преобразовании существенно малб по сравнению с длительностью сигналов (или устройства, временем преобразования в которых можно пренебречь). Математической моделью таких устройств являются так называемые схемы нз функциональных элементов. $ 1.
Понятие схемы из функциональных элементов Определение понятия схемы из функциональных элементов (Ф. Э.) можно разбить на два этапа. На первом этапе раскрывается структурная (схемная) часть этого понятия, на втором — функциональная. 1 в так. Определение схемы из функциональных элементов с точки врения ее структуры. Этот этап, в свою очередь, разбивается на ряд пунктов.
1'. Имеется конечное множество г" объектов 7» (1 1,,, г), называемых алел»енгпми. Каждый эле- Гл х синтез схех! пз Фупкцпопллы!ых элементов ят мент Р, имеет и, входов и один выход. Элемент Р! графически язображается так, как указано на рис. 2. 2'. Исходя пз элементов, по индукции определяем понятие логической сети (геометрическое определение). Логическая сеть Е будет я! определяться как объект ! с — л— (см. рис. 3), в котором вмс- дкедм ется некоторое число и входов я некоторое число р выходов. а) Базис индукции.
О на изолн ованная ве ши- да меда! д р Р на называется (триеиальной) логической сетью. По определещпо, оиа является одновременно входом и выходом (см. рис. 4). Здесь и далее на рисунках входящая стрелка обозначает вход, исходящая стрелка — выход. б) Индуктивный переход. Эта часть основана на использовапии трех операций. 1'. Операция объединения непересекающихся сетей.
Пусть Х' и Х" — две непересекающиеся Р Рлс. 2 Рас. 3 Рвс. 4 1 1 1 1 1 В 1йт 1 1 1 1 Рис. 6 Рвс. 5 сети (беа общкх элементов, входов и выходов), имеющие соответственно и и лг входов и р и о выходов (см. рис. 5). Теоретико-множественное объединение двух непересекающихся логических сетей Г и Е" есть логпческал сеть Ео входами которой являются все входы сетей Х' и Х ', выходами — все выходы сетей Х' и Х". Сеть Е, имеет л+ лг входов и р+ о выходов (см.
рпс. 6). П'. Операция присоединения элемента Р<. Пусть логическая сеть 2.' и элемент Р, (рис. 7) таковы, что и, Кр и в л,' выбрано и, попарно различных выходов 333 ч. ч, некОтОРые пРплон!еппя к кпвеРпетпки )йз ! ! ! г! ! ! ! 1 ! ! Рзс. 8 Рис. 7 покером ). Тогда фигура Х, называется логической сетью, получеяиой путем расщеплеиня выхода ). Входами з.» являются все входы з.', выходамн — все выходы логической сети Х' с яомерами 1, ..., ) — 1, )+», ..., р и еще два выхода, возникших из выхода с вомером ) сети 2".
Следовательно, и» имеет и входов и р+ 1 выход. 5з' Рве. 10 Рис. 9 3'. Пусть заданы алфавиты перемеииых Х 1х») и 2 - »з») з) . Рассмотрим логическую сеть з., имеющую и входов и р выходов. Схемой из функциональных злементое иазывается логическая сеть, входам и выходам которой прпппсаиы раз- ') Здесь слизал 1з») обозвачзет множество всех л», где иидеке ! пробегает иатуральвый ряд !илв его подмножество).
с померамп)„)»,... » У РТогда фигура з» пазывается логической сетью, являющейся результатом подключения элемента Р» к логической сетп Г. Входами Е» являются все входы з.', выходами — все выходы сети з,', кроме выходов с номерами )„..., )п„а также выход элемента Р,. Логическая сеть з.» имеет и входов и р — и,+1 выходов. Ш . Операция расщеплеи и я в ы х о д а. Пусть в логической сети У.' (рис. 8) выделеи выход с гл.
т. спнткз схим из фгнкцпональньгх элиьткнтов ЗЗЭ личные буквы и;,, ..., х;„и г;,, ..., г; соответственно пэ алфавитов Х н 2 (см, рпс. 9). Полученную таким образом схему будем обозначать через 2 (х;,..... х~„1 г;,, ..., г;„). Приведем примеры схем. 1. Пусть множество Е состоит пз трех элементов (см. рпс.
10). Тогда фигура Е„пзображенпая на рпс. И, будет схемой, так как она может быть построена с использовани- Ет лг ит ла 2з Рис. И Рис. 12 ем и" при помощи операций 1' — 111'. Этапы этого построения изображены в табл. 1. 2. Фигура Х„изображенная на рис. 12, будет также схемой (см. табл. 2). В дальнейшем мы встретимся с примерами схем, у которых вход является одновременно н выходом и у которых возможно несколько выходов. 11 этап. Определение функционирования схеьты. 4'. Пусть Х(хо .. „х„; г„..., гя) — схема из функциональных элементов*).
Сопоставим ей систему уравнений ') Беа ограничения общности можно считать, что номера переменных образуют иачальиые отрезки иатуральвого ряда. 340 ч. т. некотОРые пРиложения к киВеРнетике Таблица 1 Логвчесасл сеть Логвческая сеть Способ полтчеввя Способ полтчевва Берутсл две трпввальиые логические соти (Базис иидукции) К 1 примеилстси операция 1 К выкопали 2 и 3 сети 1П подключают але- меиты )х~ В П производит разветвлеиие выходов 1 и 2. Операцив П1 (2 рава) и )з(х„.. ч х„), называемую также проводимостью дахяой схемы. Для етого каждому элементу р, нз множества г' ставится в соответствие логический оператор )~ (..., ..., ...), имеюп(ий пч мест и задаваемый булевой функцией ге,.
(у„..., 3„,). Далев цо индукции определяется проводимость схемы. а) Базис и нду кции. Схема з. — тривиальная схема (см. рис. !3). В этом случае уравнение имеет вид з1 хп и проводимость есть тождественная функция. К выходам (1, 2) и (3„4) сети 1'т' подключают злемевты 8г Операция П (2 раза) (функций) алгебры логики Л (х, ..., х,), Операции П (2 раза) К выходам 1, 2 сети т' подьлючзют злемовт Ч. Операция П гл. г, синтзз схим из фкнклггоняльных алнмзнтов 341 Таблица 2 Л гпчеснея сеть Логнчгсеая сеть Способ получения Способ получения ггве г г г гг ге г, гг г, гг б) И н д у к т и з н ы й п е р е х о д.
Пусть г.' и Х"— две схемы, сети которых не пересекаются и входам и ле г - леем гг .. ° гд гл,г ... гл,у Ркс. 14 Ркс. 13 выходам которых приписаны, соответственно, различ- ные буквы (см. рис. (4). Пусть также схемам Х (х„..., г„; гм .. ч гг), Х" (х„и..., т„„; гге„..., г +е) '1Е 1! Берутся четыре трп виальные логиче скис сети К выходам (2, 3) сети !! подключают элемент л,. Операция И К выходам (1, 2) и (3, 4) соти 1Ч поя ключают злеиюпы Ч Операции 11 (2 рава) иг (! ПП' г К ! применястсн операпия ! (3 раза) В Ш проивзодят раэветвление выхода 2.
Операция 1П К выгодам (1, 2) сетгг гг подключают влемеггг бг Операция 11 в42 ч. т. нвкотовыв пенно~кения и кпвхвнвтпкн соответствуют системы уравнений г! =Л(хь ° . ° > лв)з з.+~-1я~~(г.н, ° ", гм-), (в) ... „...,,, (ее) гз ~~(хо ..., х ), гз+з 1э+е(ге+о ' ' ~ впаяю) 1. Схеме Е,(хо ..., х.+, г„..., г,+,), являгощейся объединением двух данных схем, поставим в соответствие систему уравнений, представляющую собой объединение уравнений (е) и (~»): ~1 (гп ° ° гн хл~ м ° ° ° ~ ха<.~) гР 1Р (лм ' '~ лю лВ~'» ''~ за+~~)к Ф гр+~ ® 1р+1(х1 ° ° ° 1 гиви гаям ° ° 1 хл~-т)~ Ф гр+ц ~ 1р+ р (г» ° ", хл1 хв+м ° "у хв+ж) Здесь ~„ ...,~р не зависят существенно от переменных Ф Ф л.„, ..., х.+, а 1„+» . °, 1„+ц — от переменных ло ..., л„ и Р 11 1» ° з 1Р 1ю /Р+1 1Р+Ь ' '1 1Р+Ч 19+Ч' 11.
Пусть схема Хг(хм .„л,; гм ''~ Йг м гз1+м ° ° 1 г!в м Йз +» ' ° 'з гю гР+1) $ получена из схемы Х'(хо ..., х„; г„..., гт) путем присоединения к выходам г;, ..., г~„(я, < р) элемента Рь и полученному новому выходу приписана буква гт+,. Тогда сопоставим этой схеме систему 'уравнений, получающуюся кз (в) вычеркиванием 1» ., )в, строчек с добавлением строки г,~, ~эф, (х„..., х„), ...~,„(х„..., т,)).
гл. а сппткз схим пз функппопллы1ых элкмкптов 842 Получим в1 11 (х„..., лл), х11-1 111-1 (~1! ° ° ! хл)! а;,+, 1;,+, (х„..., х„), 1! -1 (~! ° ° ° ~л)! С1л +! 11л Е1 (~!! ° ° .! Лл) л1 л! СР 1Р (Х1, ° ! лл), ар+1 ~1Л!(111(Х1! !Л!)! ° "!11л(Л1! ",! Хл)). П1, Пусть схема Хл(хо ..., х„; з„..., г„х,+!) получена из схемы Х'(х„..., я„; х„..., сл) расщеплением выхода с номером 1 на два выхода, и полученным выходам приписаны соответственно буквы х! и гл+,. Тогда этой схеме поставим в соответствие систему уравнений $! 1!(х!! . ° .! хл)! л1-! 11-! (~!! ! ~л) ! э!=1(х ° ° ° л ) л1+ = 1!!!(л ° ° ° л ) хл = 1, (л„..., т„), эл1, 1,(хо ..., х„). Таким обраэом, каждой схеме из Ф. 3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
