Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132701), страница 34
Текст из файла (страница 34)
Таким образом, (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 ( Х)]с = М.
Как уже указывалось в п. 2 (перед примером 5) всякое множество о.-д, функций из Ря,, состоящее из элемента единичной задержки и функций, порожленных функциями из некоторой полной в Рь системы, образует полную в Рям систему относительно со- 172 Гж Ре'. Ограниченно-денгерыинированные функции вокупности операций (01, Ог, Оз, 04, о'). В частности, в Рг „пол- на система (ги(х), 1 чи(х, у),. г р,, (х, у), чг (х)), где ги(х), ~~о (х, у) И везер(Х, У) -- О.-Д. ФУНКЦИИ, ПОРОЖДЕННЫЕ СООтВЕтетВЕННО ОтРИЦа- нием, дизъюнкцией и конъюнкцией.
В множестве Рг., сущоствуют базисы относительно совокупности операции (01, Ог, Оз, 04, о'), состоящие из одной функции. Пример такого базиса дает множество (Уо(хг, хг,. хз, ггг(154))), где 1рг эле- мент единичной задержки из Рь „„, а функция А ость о.-д. функция, порожденная функцией 1пах (х1 х4 + тг (1 — хв), хз) + 1 (здесь сумма, разность и произведение берутся по гпо<1 Й). Полнота конкретных систем в Рв, доказывается обычно мето- дом сведения к заведомо полным системам (в частности, строятся элемент единичной задержки и функции, порожденные функциями из некоторой полной в Рь системы). Пример 11.
Показать полноту системы функций (г1, фг) в Рг относительно совокупности операций (01,. Ог, Оз, 04, Я), если 11. 'у(1) = х1(г) хг(г), Е 3 1; у1(1) = х1(1) Ч 17(С вЂ” 1), уг(1) = х1(С) д(г — 1) Ч хг(Е), Ч(5) = х1(1). Хг(1), у(0) = О. Решение.
Попытаемся построить единичную задержку и функ- цИЮ (в1(Х) фуНКцИЮ, ПОрОждЕННуЮ тОждЕСтВЕННОй ЕдИНИцЕй. Этп- го для обоснования полноты системы (71, уг) будет достаточно, так как система (х . у, 1) полна в Рг. Отождествляя переменные в функции 11 (операция 01), получа- ем о.-д. функцию, порожденную тождественным нулем: 71(х, х) = = 7во(х). Затем, удаляя выходную переменную уг у функции уг (опе- рация Ог) и беря суперпозицию Ях) = 7г(7во(х), (во(х)), имеем у1(г) =Ф-1), Уз (х) ч (') д(о) = о, т.е. гз(х) — гв1(х).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
