Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1055357), страница 34
Текст из файла (страница 34)
Как уже указывалось в п. 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(х). Палее строим функцию, порожденную отрица- нием; 14(х) = ф1(х, 1 — 1(х)) = 1,(х) (использована операция Я); потом подставляем в функцию фг вместо переменной хг функцию Щхг) (операция Я) и применяем операцинз обратной связи к функ- ции гг(х1, уи(хг)) по переменным тг и у1. Получаем функцию уг(4) = х1(4) д(г — 1) Чхг(4)ч'д(1 — Ц = = х,(г).
у(г — 1)5гх \г). у(1 — ц = у(г — 1), д(г) = х (5) (х (5) ч'д(г — 1)) = х,(1), д(0) = О, г'5(х1): 15(х1) 1Р1(х1) у" Р. 27иаераммвь гпабяицеь канонические уравнения, схемы 173 Таким образом, система функций (уы 7з) порождает полную в Ркв систему (~ы ~нз(х), ~р (х)). Следовательно, система Я, уз) полная. Пример 12.
Доказать, что система (~ы уз) не полна в Рх „ относительно совокупности операций б = ~0ы Оз, Оз,. О», о'), если х г у (И) х1 (1) хз (е) у(1) = х,(1) Ч д(1- 1), ,Г2 Ч(') хг(~) ' хз (1) ~ д(О) = О. Р е ш е н и е. Покажем, что в замыкании системы (7ы уз ) относи- тельно совокупности О содержатся только такие функции, которые в момент времени 1 = 1 при подаче на входы нулей вьгдают на любом выходе О.
Очевидно, что зто так для исходных функций ~~ и Предположим, что сформулированное утверждение верно для всех тех функций из замыкания (назовем их Оапусгпимыми), которые могут быть получены из функций б и уз с использованием операций из б в суммарном количестве, не превосходящем числа 1 (1 ) О), и докажем его справедливость для функций, требующих для своего построения (из функций ~~ и 5з с помощью совокупности операций О) самое ма- лое 1+ 1 (суммарного) числа операций. Рассмотрим пять случаев. 1) Функция 1 получается из некоторой допустимой функции 1' с помощью операции Ом Пусть у . - произвольный выход функ- ции ~' и ~' = ~'(хы ..., х„) (и ) 2). Предположим, что функция 7" строится из функции 1' посредством отождествления перемен- ных х„=...
= хв = и (р ) 2), т.е. )(и, хы .,., кн У, хц Ы, ..., Я,„ы х,„+ы ..., х„) = =У( о ., хв,— в; х, хе,-~-ы .; хе„— >, х, хм--~, ., хн). Так как ~'(Оа, ..., Оа",,) = ОЬ (для всякого 1), то ..., Оа") = ОЬ и Значит, утверждение справедливо и для функции у. 2) Функция 1 получена из некоторой допустимой функции ~' с помощью операции Ох. В этом случае утверждение очевидно, так как «функционирование» любого невыброшенного выхода осталось неизменным.
3) Функция 7' получена из допустимой функции ~' с помощью операции обратной связи (операция Оз). Предположим, что обратная связь была введена по входной переменной х„и выходной перемен- ной у „, и рассмотрим произвольный выход ув О Ф,1о) у функции 1 Если в канонических уравнениях, задающих функцию 7', у„(1) = Ру,( (1), ", „- (1): .+ (1), ", .
(1), Ч(1 — 1)) 174 Гв. 1 р'. Ограниченно-дегаернинированныг функции и у (г) = Р (х1г), с1(1 — 1)), у ф фо, то функционирование выхода у описывается соотношением у,(1) = 7г,(х~(1), ..., х„с(1), Е„(х~(1), ..., х„. с(1), хм+с(1),... .х.И), Ч~1- 1)), т.„м, х.~1), цИ - 1)) Поэтому у, 1г) = г) (О, ..., О, Едв (О, ...,. О, О,..., О, с1(0)), О, О, с1(0)) = = Е,(О, ..., О, О, О, ..., О, ц(О)) = О. Следовательно, утверждение справедливо и для функции ) .
4) Функция 1" получена из допустимых функций ~' и 7о с помощью операции объединения (операция 04). Утвержденис в этом случае очевидно, так как функционирование каждого выхода (у любой из функций 1' и 1 ) остается неизменным. б) Функция у' есть суперпозиция ~'(~о) допустимых функций ~' и уо по переменным х' — у", ..., х' — у", где т', входные переменныс функции ~', а у" -- выходные переменные функции ув. Очевидно, что функционирование каждого выхода у" функции 1, являющегося выходом функции уо (т.е.
для ф ~ 1, ..., р), остается неизменным. Рассмотрим произвольный выход у'. функции 7'. Если в канонических уравнениях для функции 1' выход у' описывался соотношением (1) — йд(х~(1), ..., хр(1), хр ~ с(1), ..., хв, (1), с1 (1 — 1)), то в канонических уравнениях суперпозиции 1'(уо) ему отвечает соотношение у, (1) = г (гс (х (г), с1 (г — 1)), ..., г (х 1г), Ч (г — 1)), трез Р), ", *„, (1), Ч Р 1)) Поэтому при хо(1) = 0 и х„'„с(1) =... = х'„,(1) = 0 имеем у,'(1) = г,'(г,"(хо(1), с1о(0)), ... Ер (х (1), с1 (0)), хр,,(1), ..., х„,(1), с1 (0)) Хв (Р~ (О с1 (0)) Рр (О с1 (0)) 0 ..
0 с1 (0)) = ~,'(О, ..., О, О, ..., О, сг'(0)) = О. Значит, утверждение справедливо и для функции 1. Итак, неполнота системы (уы уз) (относительно совокУпности операции Ю) установлена. 2.17. Доказать полноту системы ( уы 5г) в Рг относительно совокупности операций ~Оы Ог, Оз, Ою о'), сели; У усв) х1(1)' хг(1) в 3 1 у (1) — х~(1). хгЯ Ч д(1 1) тг Ч(1) хс(~) х2~1)) у(о) = о; 1" 2. 2»иооераммы, ноаблииео, наноничесиие уравнения, схемво 175 2 ) 71. у(») = х1(») — 1 хг(»), » ~ )1, у(») = (х1(») — 1 хг(»)) Ч(» — 1), Уг Ч(») х1(»)) ' хг (») Ч(0) = 0; 3) (1. 'у(») = х1(») оо'хг(»), » > 1, у(») = х1(») оо' Ч(» — 1), 1 2 ° Ч(») х1 (») ~В х2 (») о Ч(0) = 0; 4) У1.
у(») = х(»), » > 1, у(») = х1(»)' хг(»)оя хз(») Ч(» 1) Ч(») = хг(»). хг(»), Ч(0) = О; О) 71: у(») = Х!(») ' Хг(»)' Х1(») о» ХЗ(») "Хг(»)' Хз(»)» ~ 31о у(») = Ч(» — 1), Ч(») = т1(») йЭ хг(»), Ч(0) = 0; 6) Л: у(») = х1(») хг(»), » > 1о ~ ~ ~ ~ ~о ~ ~ ~ ~ ~ ~ ~ ~~ ~~ ~ ~ ~ ~ ~~ ~ ~ ~ ~ ~ ~ ~ | ~ ~ | ~ ~ ~ ~ ~ ~ ~ ~ ! у(») =(х (») -+х (»)) ЧЧ(» — 1), Ч(») = х (») — + хз(»)о Ч(О) = 1; 7) »1. .у(») = х1(») -+ хг(»), » > 1о Гг задается диаграммой Мура, изображенной на рис. 4.67, а о(ц '(') цо) о 0(0) а 0 * 1 1ЦЦ ОЦО) 10(1) б оо(о) 10(0 ' 1цц 10(ц 0 *Оо(Ц,ОЦ1 ОЦ1) 1цц Рис. 4.67 6) 71. .у(») = х1(») хг(»), » > 1, »2 задается диаграммой Мура, изображенной на рис.
4.67, б; 9) 11. у(») = х1(»)оо'хг(»), » > 1, 52 задается диаграммой Мура, изображенной на рис. 4.67, в: 10) 11. .у(») = х1(») — 1 хг(»), » ) 1, у1(») = х1(») * (») 1»Ч(» — 1), у2(») хг(»)' Ч(» 1)о Ч (») — Х2 (») о Ч(о) =О:, 176 Гж 11', Ограниченно-денгернинированные функции 11) 71..
У(1) = У(1), е > 1, У1(З) = х1 (З) Уг(З) В хз(1) Е Ч(4 — 1), уг(З) = х (З) Е Ч(З вЂ” 1), Ч(З) = х (1) ц(0) = 0,: 12) 21. У(1) = хг(1) хг(й), У > 1, уг(З) = х1(З) Уг(З) У ц(З вЂ” 1),. Уг(е) х1(е) " Ч(з 1) Ь: Ч(З) = х1(Е), Ч(О) = О; 13) (1. .У(з) =Уз(1).У2(г), 1 > 1, у(е) = х1 (1) ' Ч1(Х вЂ” 1) У х2(з) ' Ч2(е — 1), Ч1(З) х1(З)' Ч1(1 1) ч хг(З) Ь Ч2(З) — * (З) ' Ч1(е 1) ч Ч2(1 1) Ч1(0) = цг(0) = 0; 1 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ! ~ ~ ! ! ~ ~ 2 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ! у(У) = ц(С вЂ” 1), у(1) = У1(1) ч' хг(1)Ч Уз(1) ' Ч(1 14) у ц(З) = У(З), у ц(З) = У1(З)1ухз(З), Ц(О) = О, Ч(О) = О; у(З) = ц(1 — 1), у(з) = хд(з)1гхг(з) ц($ 16) Л: ц(У) = : (1) Чз 2(1) Ь: ц(1) = Ч(1 — 1) ц(О) = О, ц(О) = 1.
— 1), — 1), 2.18. Доказать, что функция г является шефферовой в Рг относительно множества операций Сг = (01, 02, Оз, О~О Я); у(1) = У1(1)Ч У2Я 11Уз(з) ° Ч(1 — 1), 1) 7: Ч(1) = Уз(1).У1(1), ц(о) = о; у(З) = У1(З) хг(З)дУз(И) Ч(З вЂ” 1), 2) г': Ч(З) = х1(З) 1 (хг(С) -2 хз(С)), Ч(0) = 1; у(З) = т1(1) уг(И) хз(З)12Ч(1 — 1), 3) 1: Ч(4) = х1(з). хг(з), Ч(О) = О; У(1) = У1(З) 'хг (1) У Ц1 (е — 1) ' Чг (е — 1), 4) 7": Ч1(1) = хг(1) Уз(З), Чг(1) = хг(З) хз(С) ~/Ч1(Š— 1), ц(0) = О, цг(0) = 1; 2" х.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
