Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1055357), страница 33
Текст из файла (страница 33)
= (Хг хг е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. Таким образом, (4(и) = ~но(х) (здесь У=о(х) о.-д. функция, порож- денная тождественным нулем), т. е. 14(х ) = 0 е) Функцию, реализуемую этой схемой, обозначим через уе(и) (переменная х фиктивная). Лля получения канонических уравнений функции 1е(х) достаточно взять схему из примера а), развствить ее выход на два (у и у1) и ввести обратную связь по переменным и и ды у(е) = Ч(1 1) уз(1) = Ч(1 — 1), у(2) = (2), у(0) = 0, у(1) = д(1 — 1), Ь (х): Ч(1) = ЧИ вЂ” 1), д(0) = 0. На «языке последовательностей» функция 5(х) описывается соотношением уо(х ) = [10) ж) Функцию, реализуемую данной схемой, обозначим через Д(х) (переменная х фиктивная).
Для нахождения ее канонических уравнений можно взять канонические уравнения для функции во (1и(х)), 166 Гл. 11'. Ограниченно-детерминированные функции разветвить ее выход на два (у и уз) и ввести обратную связь по переменным х и уы Выполним зти шаги: у(1) = ЧИ вЂ” 1), уо Ег ( )). Ч(1) =х11), Ч<0) =0,. у(е) = Ч(е 1) у Ю=Ч(1 — Ц Ч(1) = Р) Ч(0) = 0, уФ = Ч(1 — 1), Ь(х): Ч(1) = Ч(1 — 1), Ч(0) = 0. На «языке последовательностей» имеем Д(х хм) = )ОЦ з) Канонические уравнения функции Ях), реализуемой этой схе- мой, получаем из канонических уравнений функции 5(х) (см. при- мер б)), применяя операции разветвления и обратной связи (как в примере ж)).
Имеем у11) = ч11 — 1), у,® = Ч(1 — 1), Ч11) = Ф Ч(0) = 0, у(1) = Ч(1 — 1),. ~г(х): Ч(1) = Ч(1 — 1), Ч(0) =0., у(1) =Ч (1 — ~), Чз18) = Чз(е Ц Чз® = Ч1(Х вЂ” 1), Ч,(0) = Чз(0) = 0, Ув (х) . 'г.е.. 18(х ) = [0110) т.е. Ут(х) = Ун1(х) или Яхй ) = 1" (переменная х фиктивная). и) Обозначим о.-д.
функцию, реализуемую данной схемой, че- рез 18(х) (х фиктивная переменная). Действуя так же, как в при- меРе з), но использУЯ пРи этом фУнкцию 18(х) (из пРимеРа в)), уз(1) = Чз(е — 1), Чз'") Чз(1 1) Ч811) = х(1), Ч,10) = Ч810) = 0, 1" 8. 27иаграммы, гаабяииеь канонические уравнения, схемы 167 к) Для построения канонических уравнений функции (д(х), реализуемой данной схемой, можно поступить так: напишем канонические уравнения для суперпозиции )яод()и(х), 1р1(х1)) 1де ххчя(и у) о.-д, функция, порожденная дизъюнкцией; затем разветвнм выход на два (у и У1), а потом применим операцию обратной связи по переменным х1 и уз. Выполним эти шаги: т. е.
у(1) = х(1), у(2) = х(1) Ух(2), ..., У(1) = х(Ц Чх(2)Ч ..Лх(1)... 2.13. Для функции ~ из Рд д построить схему над множеством, состоящим из элемента единичной задержки и функций, порожденных дизъюнкцией, конъюнкцией и отрицанием: у(1) =' (1)~4(1 — 1), У(1) =х(1) б Ч(à — 1), 1) ~; У(С) = х(1) 11(1 — 1), 2) 7' е1(1) = х(1) ф д(1 — 1), у(0) = 1:, у(0) = О; 3) функция 7" задается канонической таблицей (табл. 4.7) и начальным условием а(0) = 1; Таблица 4.7 Таблица 4.8 4) функция а(О) = О; 5) функция рис. 4.61, а; 6) функция рис.
4.61, б; 7) функция рис. 4.61, в; У1(1) = (1) У ЧИ вЂ” 1), Ч(~) х1 ( ) а(О) = О, у(1) = х(1) У д(1 — 1), Ь ( ): ч(1) = (г) 4(1 — 1), 4(0) = О, задается канонической таблицей (табл. 4.8) и задается диаграммой Мура, изображенной на задается диаграммой Мура, изображенной на задается диаграммой Мура, изображенной на 168 Гаь 1'е'. Ограниченно-детерминированные функции 1(О) о(о) о 1 0(1) об) „Цо) б 16 О(1), ЦО) Рис.
4.61 8 ) функция у задается диаграммой Мура, изображенной на рис. 4.61, г; 9) функция 1 задается диаграммой Мура, изображенной на рис. 4.61, д; 10) функция ф задается диаграммой Мура, изображенной на рис. 4.61, е; (д(1) =О, ) ф' ) у(1) = х(1 — 1) Ч д(С вЂ” 1), С > 2; 12 ) ф' '( у(1) = у(1 — 1) — > х(1 — 2), 1 > 3; у(1) =О, 13) з": У(2) = 1, у(1) = х(1 — 2) <3 у(1 — 1), 1 > 3; 14) 1"; ( у(21) = х(21 — 1), 1 > 1, ) 0 н остальных случаях; ( у(21 — 1) = х(21 — 1), 1 > 1, ' ~ у(21) = х(21 — 1) ~Э х(21), 1 > 1; У1(1) = х1(1), 16) 1: У2(1) = хз(1), д~(1) = х1(1) — ~ хг(1 — 1), 1 > 2., уг(1) = хз (С) — > т1 (1 — 1), 1 3 2. 2.14. По схеме, реализующей функцию Р из Рг, построить канонические уравнения, каноническую таблицу и диаграмму Мура: Ц рис.
4.62, а, 2) рис. 4.62, б; 3) рис. 4.62, в; 4) рис. 4.62, г; 5) рис. 4.63, а; 6) рис. 4.63, б; 7) рис. 4.63, в; 8) рис. 4.63, г. у" Я. Анаграммы, тпаблииы, канонические уравнения, схемы 169 х11) х(е) а б в Рис. 4.62 гЖ г(е) г(1) г(Е) хе Рис. 4.63 1" 2. ХХиавраммьь гааблицм, канонические уравнение схемы 171 2.15. Построить схему, реализующую ту же о.-д. функцию, что и заданная схема, но содержащукв меньше элементов единичной задержки. Схема должна строиться над множеством, состоящим из элемента единичной задержки и функций, порожденных дизьюнкцией, конъюнкцией и отрицанием: 1) рис.
4.64, а: 2) рис. 4.64, б; 3) рис. 4.65, а: 4) рис. 4.65, б; 5) рис. 4.66, а; 6) рис. 4.66, б. 2.16. В схеме, реализующей функцию Х из множества Р",', (и. > > 1), содержится р (р > 0) единичных задержек ув . 1) Показать, что вес функции Х не больше 2". 2) Привести примеры схем с р единичными задержками, реализующих функции веса г, где: а) г = 1, р > 1; б) г = 2", р > 1; в) г = 1, 2, 3, 4 и р = 2. 4.
Замкнутые классы н полнота в множествах детерминированных н ограниченно-детерминированных функций. Пусть ЛХ некоторое множество д. (или о.-д.) функций и О какая-либо совокупность операций, не выводящих за пределы множества всех д. (или о.-д.) функций. Иными словами, если о Е Ю, то, применяя о к произвольным (или допустимым) д. (или о.-д.) функциям, мы получаем снова д. (или о.-д.) функции.
Замыканием [М[п множества М относительно совокупности операций О называется множество, состоящее из множества М и таких д. (или о.-д.) функций, которые могут быть получены из функций множества М с помощью операций из б, .причем операции можно применять любое конечное число раз. Операция получения множества [М[с из М называется операцией замыкания. Множество М называется функциональна замкнутым (или, короче, замкнутым) классом относительно совокупности операций Ю, если [М[с = ЛХ.
Пусть М замкнутый относительно совокупности операций б класс д. (или о.-д.) функций. Подмножество А из М называется функционально полной (или, короче, полной) системой в М относительно совокупности операций б, если [А[с = ЛХ. Множество А д. (или о.-д.) функций называется аепривадамай системой относительно совокупности операций 11, если, каково бы ни было собственное подмножество В из А, выполняется строгое включение [В)п с [А[с. Базисом замкнутого класса М относительно совокупности операций Ю называется всякая полная и неприводимая система из М. Множество А, содержащееся в замкнутом классе М, .называется првдполиым классам в М, если оно не является полной системой в М, но для всякой функции Х из М'1А выполняется равенство [А 0 ( Х)]с = М.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
