Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132701), страница 33
Текст из файла (страница 33)
Найти вес о.-д. функции, получающейся из о.-д, функции 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 ' (Хг Ч Чг)~ Чг — — тг ГЬ'к ч Чг — — лг ~Э лг Чг, Ч. = (Хг хг е9 Чг) хг = (тг Чг) хг Теперь для получения канонических уравнений, описывающих работу схемы Еу, нужно учесть время и начальные условия; Уг(г) = лгй)' иг(г) Чг Чг(е — 1): угу) Чг(1 1)' (иг(1) " Чг(1 1))~ Чг(1) = тгф ЧЗЯ21г) Чг(1 — 1), Ч212) = (иг® Чг(г — 1)) тг(г) Ч,10) = Чг(0) = 0.
Пример 10. Выписать канонические уравнения для функций, реализуемых схемами, изображенными на рис. 4.60. (Схемы, изображенные на рис. 4.60, а и, соответствуют пп, а) к) решения.) Решение. а) Схема реализует функцию Ял) = уи192 (и)), где уи(2) о.-д. функция, порожденная функцией У из Рг. На «языке 2" Я. Анаграммы, епабаииеь канонические ураенения, схемы 163 (е) х(1) х(1) х(1) и)2 (1) у(1) о у(1) о у(1) Рис.
4.60 последовательностей» функция Ях) описывается следующим соот- НОШЕНИЕМ: 11(Хы) = 1Х(1) Х(2)... Х(1)... ИСХОдя ИЗ НЕГО МОЖЕМ СраЗу написать канонические уравнения: у(1) = 0(1 — 1) д(1) = х(1), а(О) = О. 11* 164 Гж 1г'. Ограниченно-детер)нинированные функции Приведем еше одно решенис этой задачи. Ясно, что данная схема является суперпозицией двух схем, одна из которых реализует единичнУю задеРжкУ У),(т), а дРУгаЯ фУнкцию 1и(2). Канонические уравнения этих функций можно записать в следующей форме: дз(1) = Ч~(1 — 1), дз)'г) = г)1), Ч) (х)) Чз(1) = х)1), 1и12)) е12)1) = О, Ч,<О) = О.
Ч,(О) = О. Значит, канонические уравнения суперпозиции 12(т) = 9-,(у)Г(в)) имед(1) = Чз(1 — 1); Чз )1) = х(1) Ч2Я =О, Ч,(О) = Ч,(О) = О. Вес функции 12(х) равен 2 (переменная Чз является «фиктивной»), и поэтому «приведенные» канонические уравнения для нее выглядят У(1) = Чз(1 — 1) ~,(*): Чз(1) = тЮ Чз(О) = О. (Эти уравнения с точностью до обозначения переменных такие же, как и выписанные выше.) б) Очевидно, что данная схема реализует функцию 12(т) = = 12)1 — (и)); где Л(х) о.-д, функция из примера а). Следовательно, 12(х ) =1т — «единичная задержка с начальным выходом, равным 1», и д(1) = Ч(1 — 1), 12)и) ° Ч)1) ~'1): Ч<О) = О.
в) Схема реализует функцию 1"з(х) = )р Я (и)). Значит, 1"2(х' ) = = 01т(1) х(2)... х(1)... Далее, так как функции у)з и ~з задаются следуюшими каноническими уравнениями: У211) = Чз(1 У2 (1) Ч2 )1 1) ~ у)~(и1)) Ч1)1) из(1) 11)кг)' Ч2М х2)1) Ч (О) = О, Ч2(0) = О, то имеем У(1) Чз (1 у ( )), )11(1) = Ч2(1 1) Ч2(1) = х(1), Ч,(0) = Ч2(0) = О. г) Данная схема реализует о.-д. функцию )*) = г )г - е )*) - ) )и) и рвз 2" х.
Анаграммы, хаабяииеь канонические уравнения, схемы 1бб — задержку на и тактов. Очевидно, что уо~ (х ) = 00... Ох". Канон рве нические уравнения этой функции выглядят так: у(1) =у (1 — 1), Ч1 (1) — Чз (е 1) у — (1) = Чн(1 — 1), Чн(1) = хИ), у2(0) = уз(0) = ... = ун(0) = О. д) Обозначим функцию, реализуемую этой схемой, через ув(х). От переменной и она зависит несущественным образом. Для получения ео канонических уравнений возьмем единичную задержку с двумя выходами, у и уы и введем обратную связь по переменным х и уы Канонические уравнения единичной задержки с двумя выходами у и у1 выглядят так у(1) = у(1 — Ц, уз(1) = Ч(1 — 1), Ч(1) =*(), ' д(0) = 0. Вводя обратную связь по каналам и и уы имеем у(1) = д(1 — 1),. А(х): у(1) = Ч(1 — 1) а(0) = 0.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
