Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1055357), страница 30
Текст из файла (страница 30)
17. Ограниченно-детерминированные функции 32) уф = х(Ц при 1=1, х(2) — > х(Ц при 1 = 2, х® — + (х(1 — Ц вЂ” > х(1 — 2)) при 1 > 3; О, если 1=1, 33) усг) = х(1 — Ц вЂ” ~ х®, если 1 четное, хф в ином случае; 34) уф = х(Ц, если 1 = 1, х(1 — Ц, если 1 > 3 и нечетное, у(» — Ц в ином случае; О, если 1=3з — 2 и в>1, 35)уф= 1, если 1=3з — 1 и в>1, х(1) в ином случае; 1, если 1=3з — 2 и в>1, 36)у®= х(1 — Ц, если 1=3з — 1 и з>1, у(1 — Ц -О х(1) в ином случае; О, если 1= 1, 37) уф = х1г), если 1= Зз — 2 и в > 2, х(1 — Ц у(е — Ц в ином случае; 1„если 1=4з+1 и в>0, хф, если 1 = 4з + 2 и в > О, 38) у(1) = хф, если 1 = 4в+ 3 и з > О, 0 в ином случае,: хф, если 1=4в+1 и в>0, х(1 — Ц, если 1 = 4в + 2 и з > О, ЯС вЂ” Ц, если С=4з-~-3 и з>0, у(1 — Ц.
хф в ином случае; ЗО) у~1) = О, если 1=4з+1 и в>0, х(1 — Цйхф, если 1=4в-~-2 и з>0, у(1 — ЦОвхЯ, если 1=4з+3 и в>0, х(1 — Ц 6Э у(1 — Ц в ином случае. 40) уф = 2.2. Для каждой из диаграмм построить приведенную диаграмму: Ц рис. 4.31,а; 2) рис. 4.31,б; 3) рис. 4.31,в; 4) рис. 4.31,г; 142 Га. 17. Ограниченно-детерминированные функции 0(0) 0 Цо) 2 Цо) Ц1) 0(Ц 0 0(1) 4 г 0(1) е 1 0(0) 2 0(1) Рис. 4.32 4) рис. 4.32, г; т = 2; 5) рис. 4.32, д; т = 3; 6) рис. 4.32, е; т = 3; 7) рис.
4.32, ж; т = 4; 8) рис. 4.32,з, т = 4. 2А. Найти вес о.-д. функции 7' из Рз ', заданной каноническими ц1 уравнениями: У(1) т(1) — > Ч1(1 — 1) Чг(1 — 1), Ч1(1) = Ч1(1 — 1) т Ч2(1 — Ц, Ч2(1) Ч2(1 1) + Ч1(1 1)п Ч,(0) = Ч,(0) = 1; у(1) = и(1) ео Ч1(1 — 1), Ч1(1) — х(1)' Чз(1 1) Ч2 (в) — Чз (1 1); Ч,(0) = 1, Ч,(О) = 0; У(1) = Ч,(1 — 1), Ч (~) — Ч (~ — 1) Ч (1 — ) Ч2(1) к(1), Ч,(0) = 0, Ч,(О) = 1; У(1) = х(1) и' Ч1(1 — 1), Чз(1) =х(1) ЕЧ,(1 — 1), Ч,(1) =*(1) Ч,(1 — 1).Ч,« — 1),.
Ч,(0) = Ч,(0) = 0; у" е. 2«иаграммвь таабаиивь канонические уравнения, схемы 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" и ((1[10)' ) = [ООЦ 3) Я«ОЦ ) = [110) и 1([010]ы) = [101Ц 4) «'(1[110]") = 10[ООЦы и «'(01[100] ) = [10Ц 5) »(01[10) ) = [100) и 7(011[110)ы) = 100[ОЦ 6) Я««ОЦ ) = [01Ц и ~(1100 [Ц' ) = [ОПЦ"; 7) »(111[100] ) = 00[ООЦ и 1(1[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. Применяя пере- Е, у Ед; (' численные выше операции, удобно указывать в скобках (за обозначениями этих операций) те каналы (полюса и переменные), к которым операции применяются. Например, Ог(хы хз), Ог(у,-'), Оз(хго, рг).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
