Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132709), страница 32
Текст из файла (страница 32)
Суперпозипией 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) На «языке последовательностей» единичная задержка описывается следующим соотношением: Справедливо следующее утверждение; всякая о.-д.
функция из Рь может быть реализована схемой над таким множеством, которое содержит: !) схемы, реализующие элемент единичной задержки; 2) схемы, реализующие функции, порожденные функциями из некоторой полной в Ре системы. Иными словами, любое множество о.-д. функций из Ря „, состоящее из элемента единичной задержки и функций, порожденных функ- Ц1) 00) ЦЦ ЦО) 0 0(Ц Ц2) 2(2) Ц1) Ц2) 2(2) 0(1 (3) 0(0) 3(3) к=4 Рис.
4.43 циями из некоторой полной в Рь системы, образует полную в Рь „„ систему относительно совокупности операций (Оы Оз, Оз, Ое, Я у (хн) = Ох~. Анаграммы Мура единичных задержек для к = 2, 3, 4 изображены на рис. 4.43. Вес единичной задержки из множества Рь равен к. Схему, реализующую единичную задержку, будем изображать так; р,:* -~~ Д--О.—., 152 Рт 17.
Ограниченно-денгерминированные функции Пример 5. Найти веса о.-д. функций, получающихся из о.-д. функции 1 с помощью операции отождествления, примененной к всевозможным парам входных переменных хы хг и хз. УИ) = ЧЬ вЂ” 1) — > (хг(1) ''хг Я'дхз(1)), Ч11) = х(1) хг(1) хз(1) — > Ч(1 — 1), Ч(О) = О.
Решение. Полагая хг = хг, получаем функцию У(1) = ЧИ вЂ” Ц вЂ” > (хгр)'и'хз(1И, Лг: Ч(1) = 1 Ч(О) = О. Диаграмма Мура этой функции изображена на рис. 4.44. Вес функции 1'гг равен 2. Полагаем хг — — хз. Приходим к функции 1(1) =1, Лз ЧЯ х1(4)' хг(1) 1 Ч(1 1)~ Ч(О) = О.
Вес этой функции равен 1. Диаграмма Мура функции угг и ее приве- денная диаграмма представлены на рис. 4.45. Положим теперь хг = хз. Получаем функцию у(1) =1, ггз Ч(1) = 1 Ч(О) = О. Вес функции Угз равен 1. Диаграмма Мура и приведенная диаграмма изображены на рис. 4.46. 10~) ООП 00(Ц ОНО) в 0110) 10(Ц 1ЦЦ 1ДЦ 1ЦЦ Рис. 4.44 Рис. 4.45 00 Ц 016) 10(Ц 1ДЦ 1ДЦ Рис. 4.46 Пример 6.
Построить канонические уравнения и диаграммы Мура для о.-д. функций, получающихся из функции З" 2.,»»иаераммы, тпабаииы, канонические уравнения, схемы 153 У1(») Ч(» 1): У: уг(») = х1(») Ч(» 1), Ч(») — х1(») ' Ч(» 1) ч х2 (») Ч(О) = О введением обратной связи по парам переменных (х1, у1), (хг, у1) и (хг, уг).
Найти веса полученных функций. Решение. Вводим обратную связь по переменным х1 и У1. Пля получения канонических уравнений результирую1цей функции надо 0(0) 00) ЦО) ЦО) о о(0) Цо) о Рис. 4.47 Рис. 4.48 вместо х1(») в уравнениях уг(») = т1(») Ч(» — 1) и Ч(») = х1(») Ч(»вЂ” — 1) 1» хг(») подставить правую часть соотношения у1 (») = Ч(» — 1).
Получаем уг(») = О, 111 Ч(») х2(»): Ч(О) = О. Анаграмма Мура и приведенная диаграмма этой функции изображены на рис. 4.47. Вес функции »11 равен 1. Вводя обратную связь по переменным хг и у1, получаем функцию уг(») = х1(») ' Ч(» 1): ,»21 Ч(») х1(»)' Ч(» 1) 1' Ч(» 1) х1(») "Ч(» 1)> Ч(О) = О. Ее диаграмма Мура представлена на рис. 4.48. Вес функции »21 равен 2. Вводя обратную связь по переменным хг и уг, имеем У1(») = Ч(» — 1) 122 Ч(») 'с1(») Ч(» Ц: Ч(О) = О.
Анаграмма Мура и приведенная диаграмма функции»22 изображены 0(Ц 01 :1» ЦЦ ЦЦ Рис. 4.49 на рис. 4.49. Вес функции равен 1. Эта функция автономная (порож- денная константой 1). 154 Гж 1У. Ограниченна-дегнерлеинированные функции Пример 7. Лля суперпозиции (з(Я по переменным уг — х1 о.-д, функций У,(1) =хо(1) Ч,(1-1) дх,(1), уз: Чз(е) = хо(е)о х (г) 'о Ч1(1 Ц Ч(0) = 1, Уг (1) хг (1) Ю Чг (1 1) ~ Чг(1) = хг(Ц) У Чг(1 1) Ч,(О) = О построить канонические уравнения и диаграмму Мура.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
