Гаврилов Г.П., Сапоженко А.А. - Задачи и упражнения по дискретной математике (1048833), страница 32
Текст из файла (страница 32)
функция из Рь может быть реализована схемой над таким множеством, которое содержит: !) схемы, реализующие элемент единичной задержки; 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) Ч,(О) = О построить канонические уравнения и диаграмму Мура.
Найти вес этой суперпозиции. Решение. Канонические уравнения для суперпозиции 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, Ч,(О) = О.
Отсюда следует, что вес функции 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. Зля суперпозиции 1' = Л(уг) Рис. 4.50 о.-д. функций 7з и 1г из Рг, построить канонические уравнения и приведенную диаграмму Мура: Уз(Г) = хг(Г) -+ Ч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. Ограниченно-дегаерлеинирооанные функции (При выписывании этих функций мы воспользовались эквивалентными соотношениями для функций алгебры логики: т -+ у = и 'ч' у и и ~В у = тд Чиу.) Схема из функциональных элементов, реализующая систему функций (*), имеет пять входных каналов (по переменным иы из, хз, дз Рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
