Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132709), страница 31
Текст из файла (страница 31)
Ч,(0) = Ч,(0) = 0; у" е. Лиаграммвь таабаиивь канонические уравнения, схемы 143 у(») = Ч1(» Ц + Ч2(» Ц; Ч2(») = Ч2(» — Ц; Ч2(») — и(») ~ Чз (» Ц1 Ч,(0) = 1, Ч,(О) = О; 5) У: у(») = х(») 9 Ч1(» Ц Ю Ч2(» Ц Ч1(») = Ч2(» — Ц вЂ” ~ Ч»(» Ц, Ч (») = Ч1(» — Ц -в (») Ч„(О) = Ч,(О) = О; У(») = хт(») Ч,(» — Ц.Ч2(» — Ц фЧ»(» — Ц Чз(» — Ц, Ч,(») =2;(»)»Ч,(» — Ц Ч,(» — Ц, Ч2(») 2 (») Ч2(» Ц Ч,(О) = О, Ч,(О) = 1; у(») = х(»). Чх(» — Ц 'я' Чя(» — Ц, ) ( Ч~(») — Ч (» Ц () Чз(») х(») + Ч2(» «) Ч1(0) = Ч2(0) = 1 у(») = х(») Чз(» — Ц ч х(»)' Ч2(» Ц Ч2(») = х(») Чх(» — Ц Н х(») .
Чз(» — Ц, Ч2(») х(»)' (Ч1(» Ц ' Ч2(» Ц)' „ (О) = 1, Ч,(О) = О; у(») = Чз (» — Ц . Ч2(» — Ц -2 х(») 10) ». Ч2(») = Ч2(» Ц ф Ч1(» Ц Ч,(О) = Чя(О) = 1. 2.5. Для частично определенной д. функции »"(х '): (О., 1)" -+ — » (О, 1)"', отображающей заданные последовательности в заданные, построить диаграмму Мура с возможно меныпим числом вершин; затем полученную диаграмму доопределить до диаграммы Мура всюду определенной о.-д. функции из Р ',, и для этой новой функции Д2 построить каноническую таблицу и каноничоские уравнения: Ц ДОы) = [ОЦ и 1([10]") = 1': 2) ЯОЦ ) = 0" и Д«[10)' ) = [ООЦ 3) Я«ОЦ ) = [110) и 1([010]ы) = [101Ц 4) «'(1[110]") = 10[ООЦы и «'(01[100] ) = [10Ц 5) »(01[10) ) = [100) и ДО«1[110)ы) = 100[ОЦ 6) Я««ОЦ ) = [01Ц и ~(1100 [Ц' ) = [ОПЦ"; 7) »(111[100] ) = 00[ООЦ и Д«[1100]") = 000 [Ц"'; 8) 7"([11000] ) = [010] и 1(1100 [Ц ) = 01[0) '.
144 Гл. 1'г'. Ограниченно-дегаерминирооанные функции 2.6. Подсчитать число различных о.-д. функций из Рг',, у ко- !,! торых приведенная диаграмма Мура получается из указанного ориентированного графа путем приписывания его дугам подходящих меток вида а(Ь), где а и Ь принадлежат множеству 10, 1) (звездочкой обозначается начальное состояние): 1) рис. 4.33,а; 2) рис. 4.33,б; 3) рис. 4.33,а; 4) рис. 4.33,г; 5) рис.
4.33, д; 6) рис. 4.33, е; 7) рис. 4.33, ле, 8) рис. 4.33, з; 9) рис. 4.33, ж 10) рис. 4.33, к; 11) рис. 4.33, л; 12) рис. 4.33, и. О а б в 0 Рис. 4.33 2.7. Ц Локазатгч что приведенные диаграммы Мура различных !л о.-ц. функций веса 2 из Рг'а исчерпываются диаграммами, получающимися из ориентированных графов, изображенных на рис. 4.34, г д Рис. 4.34 у" 2. Лиаараммыс споблицы, канонические уравнения, схемы 145 путем приписывания их вершинам меток О и 1, приписывания их ребрам меток вида а(Ь), где а и Ь принадлежат множеству (О, 1), и выделения подходящих вершин в качестве «начальных» (т.е. в качестве вершин, соответствующих начальным состояниям).
1.1 2) Поде~~~а~~ спело различных о.-д. функций из Рг',„, имесощих вес 2. 2. Операции иад детерминированными функцинми. Пусть д, функция г" задана системой (2) (см. и. 1) и каждая из функций Рс и Сс всюду определенная функция Ь-злачной логики Рс (Ь > 2). Будем рассматривать функцию 1 как элемент множества Р„' . Схема Ху, реализуюиСом функцию (, определяется следующим образом: Еу представляет собой сеть (определение сети см. в гл.
У1), полюсам которой приписаны символы входных и выходных переменныхв а некоторым вершинам, отличным от полюсов, приписаны символы каких-то (вполне определенных и связанных с 1) д. функций (из множества ( ) Р" з). Схему функции у из Рп'ы будем изображать в>1 С>1 Ус уг Х1 хг у 1'нс. 4.35 в виде прямоугольника (рис. 4.35) с и входами (входными каналами) и сп восходами (выходными каналами). Входы изображаются в виде стрелок, исходящих из входных полюсов, а выходы в виде стрелок, заходящих в выходные полюса.
Полюса изображаются в виде кружочков. Если т = 1, то схему Бу, реализующую функцию у, иногда изображают в виде треугольника (рис. 4.36) с п входными и одним выходным полюсами. Считаем,чтовкаждыймомент времени 1 = 1, 2, ... наг-йвходх, поступает входной символ х,(1) б Ес, а на у-м выходе у. выдается значение ус(Г) =Рг(хс(1) " х (1) 41(1 — 1) " Ч.(1 — 1)) Говорят,что выход у зависит с запаздываниям от входах„ если функция Рг (хрб(1), Чс" с(1 — 1)) не зависит существенно от переменной х;(1). Понятие зависимости с запаздыванием можно ввести иначе.
Рассмотрим, например, случай д. функции вида Д(х"'',х"', ..., х„): А, х Аг' х ... х А„— с В и определим зависимость с запаздыванием от переменной хс . Функция с" зависит с запаздыванием от х', если при любых входных словах а, а', ... „а„' (а б А", у = 1, 2, ..., и) в-я буква выходного слова Ь = 1(Б"', а, ..., а„) однозначно определяется в первыми символами слов а'", ..., а„"' и в — 1 первыми символами слова аг" (в = 1, 2, ...).
10 Г. П. Гаврилов, А. А. Сапожепко 146 Гас Л; Ограниченно-детерминированные функции Пусть д. функция 1 задана системой (2) и Еу схема, реализующая эту функцикь Определим три операции над функцией 1 и схемой Еу. 1) Операция Оз -" отождествление двух или болыпего числа входных переменных в функции 1 и отождествление в схеме Еу соответствующих этим переменным входных полюсов. Отождеств- х~ х х1 х„ х1хгхз х х1=хо хз хо о о о о о о у1 у Уз У 91 уз У Уг У Рис. 4.37 Рис.
4.38 ленные полюса рассматрива1отся как один полюс новой схемы. На рис. 4.37 показана схема Ер, которая получена из Еу отождествлением полюсов хз и хг. 2) Операция Оз — удаление некоторой выходной переменной у у функции 1 (что эквивалентно выбрасыванию из системы (2) уравнения у,(1) = Е,(х~"1(1), ц~'~(1 — 1))), и удаление из схемы Ху выходного канала и полюса, соответствующих выходной переменной у (на рис.
4.38 изображена схема Ер, полученная из схемы Ху после удаления выходного канала и полюса у1). Замечание. Если т = 1, то, удаляя переменную у1 (единственную выходную пероменную), получаем автомат без выхода (его вес считаотся неопределенным). 3) Операция Оз введение обратной связи по одной входной и одной выходной переменным. Пусть в качестве входной переменной взята переменная хн а в качестве выходной . — переменная у .
Операцию Оз можно применить к функции 7 и схеме Еу только в том случае, когда выход у, зависит с запаздыванием от входа х,. Канонические уравнения для новой функции 7' получаются исключением из системы (2) уравнения у ф = Г (х'"~(1), с1~'~(1 — 1)) и заменой переменной х,1г) в каждой функции Ра (д ф 1) и О~ на функцию Р,'(х1(1), ..., х, з (1), хны (т), ..., х„(1), аз (1 — 1), ..., У„(1 — 1)), получающуюся из функции гз(х~"1(1), ц~"1(1 — 1)) отбрасыванием несущественной переменной х,(1).
Начальные условия остаются прежними. Схема Еу получается из схемы Еу путем отождоствлсния выхода у с входом х„при этом отождествленные полюса объявляются внутренней вершиной схемы Еу . На рис. 4.39 показана схема Еу , .полученная из схемы Еу введением обратной связи по переменным хз, уь З" в. Лиаераммвь табяиивч канонические уравнения, схемы 147 Замечание 1. Если и = 1, то, х1 г:г хг х вводя обратную связь по переменной хг (и любой выходной переменной), получаем автомат без входи Замечание 2. Применяя пере- Е, у Ед; (' численные выше операции, удобно указывать в скобках (за обозначениями этих операций) те каналы (полюса и переменные), к которым операции применяются. Например, Ог(хы хз), Ог(у,-'), Оз(хго, рг). Рис.
4.39 Опишем еще три операции над д. функциями. 4) Операция 04 --- операция объединения двух (или большего чис- ла) функций. Пусть 1"г б Рн"~' и гг Е Рн'~'. Предполагаем, что эти функции имеют в качестве входных переменные хг, х',, ..., х'„, и х", х~г', ..., х'„', соответственно, а в качестве выходных . - пере- менные уг, уг, ..., у,'„, и уг', уг, ..., у",. Считаем, что все эти пе- ременные попарно различны. Пусть Ед и Еу, — схемы функций уг и уг соответственно.
Тогда схема Еу функции 7, равной объедине- нию функций уг и 7г, будет выглядеть так, как показано на рис. 4.40; У1Уг У Уг У я Х я х г У, У1 я У г Е У1 Рис. 4.40 при этом входными и выходными полюсами схемы Еу являются соответственно все входные и все выходные полюса схем Ед и Ейо Канонические уравнения и начальные условия для функции 7 получаются путом объединения канонических уравнений и начальных условий, задающих функции 1г и 1г. При этом предполагается, что множества фц и ф~~ состояний функций уг и уг не пересекаются. 5) Оиеририя Я операция суперпозиции. Пусть 7г й Рд и д и 1г е Рп с „.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
