Гаврилов Г.П., Сапоженко А.А. - Задачи и упражнения по дискретной математике (1048833), страница 31
Текст из файла (страница 31)
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г е Рп с „. Суперпозипией 1г(Я функций 1г и 1г называется такая фуНКцИя 1 б Ря С я, ЧтО г(Хы) = гг(гг(Х' )) Прн ЛЮбОМ ВХОДНОМ СЛО- ве х из А' . Пусть 1, б Р" он' (г = 1, 2), и им отвечают схемы Ед и Еее.
(Считаем, что входные и выходные переменные и состояния го* 148 Рт 1У. Ограниченно-деенерминированныв функции фУнкций уз и уз такие же, как в пРедыдУщем пУнкте.) Можно ввести такую суперпозицию этих функций; отождествим, .например, входной полюс х" ,схемы Ху, с выходным полюсом у,', схемы Хй, полюс и.", П П Х 1 Х 1 — 1е1 х 2 я, о а о П Уз У~ Уе о П У г Рис. 4.41 с полюсом у~+э и т.д., наконец, полюс и'„' ~ с полюсом у„'„; получим схему Ху (рис.
4.41), у которой: а) входными полюсами будут все входные полюса схемы Хд и входные полюса схемы Хе„не участвовавшие в указанной выше процедуре отождествления; б) выходными полюсами являются все выходные полюса схемы Хуа и те выходные поливов схемы Хе, которые не были отождествлены ни с одним входным полюсом схемы Хуа. Отождествленные полюса объявляются внутренними вершинами схемы Хе. Схема Хе называется суперпозицией схем Хд и Хеа (по переменным у,'е — тд', у,'е — тз, ..., у', — к",). Если функция ~з задается системой Уз Ф = Й(т',(1), ..., и'„, Я, д,"11 — 1), ..., д'„,(1 — 1)), у', (1) = Р'„'„(т~ (1), ..., и',, (1), дз(1 — 1), ..., д,', (1 — 1)), д,(1) С,<т',<1), ...,,'„(1), д',(1 — Ц, ..., д',, <1 — Ц), (4') д„',Д = а'„,( ',~1),...., '„,~1).
д,'~1 — 1), ..., д„',(1 — 1)), д',(б) = д,'„..., д.'„, (б) = две,. у" 2. У»нограммвь тпобяицвь канонические уравнения, схемы 149 а функция уя системой .1'(») = »о(х1'(»), ..., х." (»), Чо(» - 1), ..., Ч,". « - 1)), и,".,(») = ",('Г(»):, '".,«): ЧГ(» — 1),, Ч,",« — 1)): Ч,"(») = С,"(",(»), ...,, '„', «), Ч,"(» — 1), ..., Ч,'.',(» — 1)), (4о) Ч'„',(») = О,"е(х" (»), ..., х'„',(»), д "(» — 1), ..., д,",(» — Ц), Ч" (6) = Чом "" Ч,",(6) = Чо'„, то функции у, реализуемой схемой ууч соответствует такая система: у,'(») = р,'(х',(»), ..., х„',(»), Ч,'(» — 1), ..., Ч„'(» — ц), у,'(») = Р (х', (»), ..., х'„н (»), Ч,'(» — 1), ..., Ч,'„, (» — 1)), уо(») = ~~'Ж„,, ~' „, ьы(»), ..., х„,(»), Ч»(» — 1), ..., Чее(» — 1)), '„',(»), Ч,(» — 1), ..., Ч,,(» — 1)), Ч'«) = О'(х'(»), ", х'.,(») Ч'« — 1)," Ч'„(» — 1И, (5) д„ (») = О„,(, (»), ..., х„,(»), Ч (» — 1), ..., д„ (» — 1)), Ч,(») = а,"(К'„, ..., Г' „х'„'„, „,(»),...
..., х'„',(»), Ч,(» — 1), ..., Ч„« — 1)), дев(») = а %+1 . гт хт — ны(») ..., х!'„(»), Чз(» — 1), ..., Ч„(» — 1)), Ч1(6) Ч01 ' ' Чс ( ) ЧОе1 Чз (6) Ч01 Че (6) ЧОее где Р" = Г'(х~ (»), ..., х'„, (»), чд(» — 1), ...., ч,', (» — 1)), у = » -ь 1, ..., эм. 6) Операция Оз -- операция разветвления (некоторого выхода о.-д. функции). Пусть 1 . функция из Р„', и Е» " реализующая ее схема.
Результатом применения операции О; к выходу у. функции » и схемы Е» являются функция у' и схема Е» такие, что: а) канонические уравнения, задающие функцию »', получаются из канонических уравнений, описывающих функцию у, заменой уравнения у (») = »с (х»"~(»), ц»'~(» — 1)) совокупностью уравнений уч(») = = Р' (х~ "~(»), с»»"~(» — 1)) (в = 1, ..., О) (если выход у разветвился на и выходов у', ..., у',„); 150 Гж 17. Ограниченно-део>ерем>ворованные функции б) схема Еу получается из схемы Еу разветвлением канала (и полюса) у, на соответствующее число «одинаково работая>щих» х„ х> У> У> У У> У Ул У>.
Рис. 4.42 каналов у>ы ..., у'„каждый из которых реализует ту же функцик>, что и канал у в схеме Е> (рис. 4.42). Из определения операций О>, Оз, Оз, 04, Ов и Я немедленно вытекают следующие утверждения: а) если 1 = 1, 2, 3, то вес функции )о, полученной из функции 1 г помощью операции О, не превосходит веса функции 1 (здесь> естественно, предполагается, что у функции 1' имеется хотя бы одна выходная переменная, иначе ее вес был бы неопределенным); б) вес функции 1, полученной из функции 1> и уг с помощью операции 04 (операция объединения), равен произведению весов функций 1> и 5г, в) вес функции 1', полученной из функции 1 с помощью операции Оз (операция разветвления), .равен весу функции 1; г) вес фУнкции 1, полУченной из фУнкций 1> и уз с помощью операции Я (о>>грация суперпозиции), не превосходит произведения весов функций )> и )з.
Справедливы и такие предложения: Ц если целые числа г> и гя удовлетворяют неравенствам 1 < ( г, < гг, то сУществУют о.-д, фУнкции 1> и уз> веса котоРых Равны соответственно г> и гз, и при этом функция 1> получается из функцииуз с помощью опорации О, (> = 1, 2, 3); 2) если целые числа го, г> и гз удовлетворяют неравенствам 1 < го < г> гз> то существуют о.-д. функции д>, 1'> и 6з, веса которых равны соответственно го, г, и гз, и при этом функция )о есть суперпозиция функций 1> и )г.
Нетрудно показать, что операция Оз иороомдается операциями О>, Оз и 04, а именно, если о.-д. функция )» получена из о.-д. функции 1 с помощью операции Оз, то функцию 1' можно реализовать над множеством 11) (т, е, используя, вообгце говоря, несколько экземпляров функции )) с помощью операций О>, Оя и 04. у 2. Яиаграммвп хаайяииеи канонические уравнения, схемы 151 Элементом единичной задержки (или, короче, единичной задержкой) в множестве Ря „называется о.-д, функция уе (х), задаваемая системой < у(1) = д(4 — 1), О(1) = х(1), д(О) = О. (6) На «языке последовательностей» единичная задержка описывается следующим соотношением: Справедливо следующее утверждение; всякая о.-д.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
