Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132701), страница 32
Текст из файла (страница 32)
", х"..,(»), Ч1(»-1) ". Ч" (»-1)) дев(») = а %+1 . гт хт — ны(») ..., х!'„(»), Чз(» — 1), ..., Ч„(» — 1)), Ч1(6) Ч01 ' ' Чс ( ) ЧОе1 Чз (6) Ч01 Че (6) ЧОее где Р" = Г'(х~ (»), ..., х'„, (»), чд(» — 1), ...., ч,', (» — 1)), у = » -ь 1, ..., лм. 6) Операция Оз -- операция разветвления (некоторого выхода о.-д. функции). Пусть у . функция из Р„', и Е» " реализующая ее схема. Результатом применения операции О; к выходу у. функции » и схемы Е» являются функция у' и схема Е» такие, что: а) канонические уравнения, задающие функцию »', получаются из канонических уравнений, описывающих функцию у, заменой уравнения у (») = »с (х»"~(»), ц»'~(» — 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) схемы, реализующие функции, порожденные функциями из некоторой полной в Ре системы. Иными словами, любое множество о.-д. функций из Ря „, состоящее из элемента единичной задержки и функций, порожденных функ- ЦЦ 00) ЦЦ ЦО) 0 0(Ц Ц2) 2(2) ЦЦ Ц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.,»»иаераммы, н1абаииы, канонические уравнения, схемы 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) = хо(1)Ч х;Ы ~Ч,(1-1), Ч(0) = 1, Уг (1) хг (1) Ю Чг (1 1) ~ Чг(1) = хг(Ц) У Чг(г 1) Ч,(О) = О построить канонические уравнения и диаграмму Мура. Найти вес этой суперпозиции.
Решение. Канонические уравнения для суперпозиции 1 = уз(уг) по указанным переменным получаются подстановкой правой части соотношениЯ Уг(1) = хг(Ц 9 Чг(1 — 1) вместо пеРеменной х1(1) в канонических уравнениях для функции 11 и добавлением к получившимся выражениям уравнения Чг(1) = хг(1) дЧг(1 — 1) и начального условия Чг(О) = О. Имеем уз(1) = хо(Е) Ф (1 — 1) У (хг(1) ЧЗ Чг(1 — 1)), Ч1(1) = хв(1) Ь' хг(1) Ю Чг(1 — 1) '' Ч„(1 — 1), Чг (1) хг (") ' Чг (У 1) Ч,(О) = 1, Ч,(О) = О. Отсюда следует, что вес функции 1 не больше 4 (так как каждая пеРеменнаЯ Чы Чг пРинимает два значения, а именно О и 1). Исходя из этих 10(Ц уравнений и начальных условий стро- 1 01(Ц 110 * им диаграмму Мура (рис. 4.50).
При- 10 00(0) 00(Ц 01(0) веденная диаграмма, соответствующая 10(0) 10(ц 01(0) полученной диаграмме Мура, содержит 1ЦЦ 11(0) вершины 01, 10 и 11. Следовательно, 00(Ц вес суперпозиции 1 равен 3. 00 01 2.8. Зля суперпозиции 7' = Л(уг) Рис. 4.50 о.-д. функций 7з и 1г из Рг, построить канонические уравнения и приведенную диаграмму Мура: Уз(Г) = хг(Г) -+ Ч1(Г Ц Уг(Г) = хг(1) у Чг(1 — 1), 1) Л: Чз(1) =* Ф, гг' Чг(~) хг( ) ф Чг(И вЂ” 1), Ч,(О) = 1, Ч,(О) = О; уз(г) = Чз(г — 1) Уг(Ц = Чг(1 — 1), 2) )м Чг(Е) = Ч1(1 — 1) — э х1(1), уг. Чг(1) = хг(1), Ч,(О) = О, Ч,(О) = 1; уз(г) = хз (е), Уг(1) = Чг(1 — 1),. 3) гз.' Чз(е) = Чз(1 1) гг.
Чг(1) хг(1) Чг(1 1) Ч,(0) = 1, Ч,(О) = О; 12. 27иддераихдьд, идабаииьд, канонические уравнения, схеддм 155 у д(4) = ' (1). Ч (Д вЂ” 1) 4) Уд Чд(1) = Чд(Д вЂ” 1),. Чд(О) = О, дг: уг(1) = 1,. уг(С) = хг(4) 01 уг(Х вЂ” 1), Д > 2; 5)1. уд(д) = хд(д — 1) -+ уд(д — 1), д > 2, < Уг(Д) — Чг(1 1) д хг(Д) ,дг Чг(х) = хг(Д), Ч,(О) = 1; 6) функция 1д задается диаграммой Мура, изображенной на рис. 4.51, уг(Д) хг(1) ~ Чг(Д 1)) .дг Чг(1) хг(") + Чг(~ 1) Ч,(О) = 1; 7) функции дд и дг задаются диаграммами Мура, изображенными 0(0) о(ц о(ц, Цц 0(Ц ЦЦ 0 1 0 1 ( ) 0(0), ЦЦ а б Рис.
4.52 Рис. 4.51 н а рис. 4.52, а, б соответственно; уд(1) = уд(2) = О, Уд(4) = Уд(4 — 1) -+ Уд(4 — 2), Д > 3, .дг. уг(1) = О, уг(2) = 1, Уг(Д) = хг(Д) — д дг(4 — 2), Д > 3. 2.9. Построить канонические уравнения и приведенную диаграм- му Мура о.-д, функции, получающейся из функции д" введением об- ратной связи по переменным х,, уд: ддд(г) = хд(д) — д Ч(х — 1), 1) Уг(") = хд(')'хг(') 6~ Ч(" 1), Ч(1) = (1) Дд* (4) Ч(4 — 1), Ч(О) = О, уд(1) = хд(Д) д7 ха(С).
Ч(Д вЂ” 1), уг(1) = хд(Д) бдЧ(4 — 1), Ч(д) = хд(д). хг(д) дд Ч(д — 1), Ч(О) = О, 1=2, 2=1; »=1, 1=2; а) 1 = ф = 1; б) 1 = 2, ф = 1; 1=1, 2=2; 7) 7": а) 1= 2, ф= »й(») Уг(») Ч1(») Ч2 (») Ч1(0) 8) 7": а)1= 2.10. Найти вес о.-д. функции, получающейся из о.-д. функции г" введением обратной связи по переменным х» у". У1(») = т»(») ' тг(») 1 Ч(» 1) у2(») тг(») "Ч(» 1)~ Ч(») = Х1(») — 1 хг(»)., Ч(0) = 1, 1=1, 2=2; 3) ( 4) У" 5) У" Гт Гг'. Ограниченно-детерминированные функции уг(») = хг(») — ~ Ч(» — 1), у2(») к1(») ' Ч(» 1) чо гг(»)~ Ч(») — тг(») 1 Ч(» 1) Ч(0) =1., уг(») = х1(») Ч(» — 1) Миг(»), У2 (») и2 (») Ч(») = (и1(») — > хг(»))1»Ч(» — 1), Ч(0) = 0, У1(») = Ч(» — 1), Уг(») = и1(») ЧЗ (*2(») у Ч(» 1)), Ч(») = Ч(» 1) + т1(»)' г:2(»), Ч(0) = 0, У1 (») (тг (») + т1 (»)) + Ч(» 1) Уг(») = хг(») Ч(» — Ц уз(») = У1(») (и2(») — + Ч(» — 1)), Ч(») = х1(») Ч(» — 1), Ч(0) = 1,.
У1(») = и1(»), У2(») = Хг(») Ю Ч(» — 1), уз(») гг(») "Ч(» 1) Ч(») = Х1(») ч хг(»), Ч(0) = 0, 1; б) 1 = 1, ф = 2; в) г = 1, ф = 3;. = ' (») 1Э Ч (» — 1) Чг(» — 1) = хг(») — + Ч2(» — 1). = Ч1(» — 1)»В Чг(» 1), = 21(») СУ Ч1(» — 1), = Ч,(0) = 0, 2; б) 1 = 2, ф = 1, 153 Х'в. !»г. Ограниченно-денгерминированные функции 2.11.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
