Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1055357), страница 32
Текст из файла (страница 32)
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. Найти вес о.-д.
функции, получающейся из о.-д, функции 1 с помощьк> операции отоясдествления входных переменных х, и х, (операция 01): 1) У: а) 1 = 1, у = 2; б) 1 = 2, у = 3; 2) 1: а) 1 = 1, 1 = 2; б) 1 = 2, 1 = 3; 3) ф: 1, 1 = 2; б) 1 = 1, 1 = 3; в) 1 = 2, ф = 3; а) 1= У1(») = х1(») — 1 (хг(»)1» хз(»)) Ч(» — 1), уг(») Ч(» 1) е х1(») хг(»)~ Ч(») = Ч(» — 1) У хг(»). хз(»), Ч(0) = О,.
4) 1 а) 1 = 1,,1 = 2; б) 1 = 1, 1 = 3; в) 1 = 2, г = 3 2.12. Найти все суперпозиции»"1(»"2)., если: 1) ф1.' У1(») = х1(»)'~Ч1(» — 1), Уг(») = хг(»)'Чг(» 1) Ч1(») = х1(») У Ч1(» — Ц, 12: Чг(») = хг(») Чг(» — 1) Ч,(О) =О, Ч,(0) = 1; 3) ф1: у(») = х1(») -+ хг(») Ч1(» — 1), Ч1(») = хг(») — ~ хз(»)' Чг(» — 1) Чг(») = х1(») хг(») У Ч1(» — 1), Ч1(0) = Чг(0) = О, у(») — х1(») 1» хг(») ' Ч1(» 1)", Ч1(») Чг(» 1) + Ч1(» 1)~ Чг(») =* (») У-хз(») УЧ1(»-1) Ч,(0) = Чг(0) = О, У1(») — х1(») ' х2(») е Ч(» 1) уг(») = х1(») . хз(») — 1 хг(»), Ч(») = хз(») '» Ч(» — 1) Ч(0) = 1, у (») =Ч (» 1) 2) 11.
Ч1(») = х1(») Ч1(» — 1), 12 Ч,(О) =1, У1(») = х1(») — + Ч1(» — 1), Ч (») =Ч1(» — 1) Ч1(0) = О, У (»)=Ч (» — Ц, Чг(») = хг(») У Чг(» — 1) Ч,(О) =О; 1" х. Анаграммы, н)абянцы, канонические уравнения, схемы 159 функция уг задается диаграммой Мура, изображенной на рис. 4.53; цб) () 0" цц 1 0 0(0)ц1 0(0) а б Рис. 4.53 Рис. 4.54 0(Ц 0(1) 0(1) цо) Ц1) цц Рис.
4.55 4) функции )"1 и )2 задаются диаграммами Мура, изображенными на рис. 4.54, а, б соответственно; 5) функции 11 и уг задаются диаграммами Мура. изображенными на рис. 4.55, а, б соответственно. 3. Реализации ограниченно-детерминированных функций схемами. Понятие схемы, реализующей о.-д, функцию, и определение соответствующих операций над схемами даны в и. 2. В настоящем пункте представлены некоторые задачи, относящиеся к схемам, реализующим о.-д. функции из множества Рг, .
Пример 8. Построить схему, реализующу)о о.-д. функцию у из Рг од над множеством, состоящим из элемента единичной задержки и функций, порожденных дизъюнкцией, конъюнкцией и отрицанием: У1(е) = х1(е)'Ч1(1 1)1) хг(е)'хз(е) Уг(1) Чг(е 1) е х1(1) )) хзФ~ Ч1(х) = Ч1(1 — Ц ей Чг(1 — 1), Чг(2) = х1(2).хг(Г) Ч1(2-1), Ч,(0) = Ч,(0) = 0. Решение. Сначала строим схему из функциональных элементов над множеством, состоящим из дизъюнкции, коныонкции и отрицания, для следующей совокупности булевых функций: у1 = х1 Ч1')) хг хз, Уг=Чгчхзчхз, Ч1 Ч1 'Ч2 ))Ч1'Чг; Ч2 — х1 х2 ' Ч1. 160 Гл.
17. Ограниченно-дегаерлеинирооанные функции (При выписывании этих функций мы воспользовались эквивалентными соотношениями для функций алгебры логики: т -+ у = и 'ч' у и и ~В у = тд Чиу.) Схема из функциональных элементов, реализующая систему функций (*), имеет пять входных каналов (по переменным иы из, хз, дз Рис. 4.56 и уз) и чотыре выходных (по переменным уы дз, у' и у' ). Обозначим эту схему через Е*. Она представлена на рис.
4.56. Светлыми кружочками на ней обозначены входные и выходные полюса, а темными кружочками - внутренние полюса. Функциональныс (логические) элементы, реализующие дизъюнкцию, конъюнкцию и отрицание, изображены в виде треугольников с двумя (для дизъюнкции и конъюнкции) или одним (для отрицания) входными каналами.
У каждого функционального элемента один выходной канал. Около выходных полюсов элементов указаны булсвы функции, реализуемые такими подсхемами схемы Е', у которых входы совпадают с входами схемы Е*, а выходами являются данные выходы элементов. В треугольниках, соответствующих элементам, реализующим конъюнкцию, изображен знак ег; элементы, реализующие отрицание, помечены знаком 1. Лля получения схемы Еу, реализующей о.-д. функцию у, достаточно к выходам д' и а' схемы Е* присоединить последовательно у 2. 11иаераммвь тааблиивь канонические уравнения, схемы 161 элементы единичной задержки (опсрация супсрпозиции) и затем ввести обратную связь по парам каналов уха — е71 и дз — е7з, где да выходной канал элемента единичной задержки, подсоединенного к выходу у,'.
схемы Е*. Схема Ху приведена на рис. 4.57. (Нули около элементов единичной задержки, поставлены нами для того, чтобы лишний раз напом- ! (1 — 1) Рис. 4.57 нить, что в момент времени 1 = 1 выходные символы этих элементов равны О.) Пример 9. По схеме Еу, реализующей функцию 1 (рис. 4.58), построить канонические уравнения, задающие эту функцию. Рис. 4.58 11 Г. П. Гаврилов, А.
А. Свиоженио 162 Гл. 17. Ограниченно-деигерминированные функции Решение. Удаляя из схемы Ху задержки, получаем Еу схему из функциональных злементов, изображеннукв на рис. 4.59, с дополнитвльными выходными (Ч~г и Чг) и входными (Чг и Чг) полюсами. Рис. 4.59 Выписывая функции проводимости для каждого выходного полюса, имеем Уг лг 'хгч'Чы У2 Ч1 ' (Хг Ч Чг)~ Чг — — тг ГЬ'к ч Чг — — лг ~Э лг Чг, Ч.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
