Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132709), страница 35
Текст из файла (страница 35)
(или о.-д.) функций, которые могут быть получены из функций множества М с помощью операций из б, .причем операции можно применять любое конечное число раз. Операция получения множества [М[с из М называется операцией замыкания. Множество М называется функциональна замкнутым (или, короче, замкнутым) классом относительно совокупности операций Ю, если [М[с = ЛХ. Пусть М замкнутый относительно совокупности операций б класс д. (или о.-д.) функций. Подмножество А из М называется функционально полной (или, короче, полной) системой в М относительно совокупности операций б, если [А[с = ЛХ.
Множество А д. (или о.-д.) функций называется аепривадамай системой относительно совокупности операций 11, если, каково бы ни было собственное подмножество В из А, выполняется строгое включение [В)п с [А[с. Базисом замкнутого класса М относительно совокупности операций Ю называется всякая полная и неприводимая система из М.
Множество А, содержащееся в замкнутом классе М, .называется првдполиым классам в М, если оно не является полной системой в М, но для всякой функции Х из М'1А выполняется равенство [А 0 ( Х)]с = М. Как уже указывалось в п. 2 (перед примером 5) всякое множество о.-д, функций из Ря,, состоящее из элемента единичной задержки и функций, порожденных функциями из некоторой полной в Ря системы, образует полную в Рям систему относительно со- 172 Гж Ре'. Ограниченно-денгерыинированные функции уг(4) = х1(4) д(г — 1) Чхг(4)ч'д(1 — Ц = = х,(г). у(г — 1)5гх \г). у(1 — ц = у(г — 1), д(г) = х (5) (х (5) ч'д(г — 1)) = х,(1), д(0) = О, г'5(х1): 15(х1) 1Р1(х1) вокупности операций (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.
Получаем функцию у" Р. 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), Ч(») = х (») — + хз(»)о Ч(О) = 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" х. 27ииграммы, иуаолииы, канонические уравнения, схемы 177 уг(1) = х1(1) уг(2- 1), Уз(у) = х1(Г)' дг(у 1) у хз(у) ' чз(у — 1), д~(2) = х1(у) хз(1), Ч2 (е) Ч1 (1 1) д,(О) = дз(О) = О. 5) Х: 12 Г.
П. Гаврилов, А. А. Сапожонка 2.19. Из системы А, полной в Рз,„относительно множества операций (01, 02, Оз, 04, Я), выделить собственную подсистему, полную в Рз, относительно тех же операций (и состоящую из возможно меньшего числа функций); 1) А = <Х= (х) Хи (х): Х' (х у): Ххэ е1к(х у 2) 1ру(х))' 2) А = (Хио(х), Х, у(х, у), Х, у(х, у), 1рз(Хи(х))); 3) А = (Х=г(х), Ххоуу(х, у), Ххоу(х, у), 1р (Х» (х, у))); 4) А = (Х=— о(х) Хх(х), Хх.у(х, у), Хауз(1ру(х), .Ху(у))); 5) А = (Х=1(х), Х .у(х, у), Х, (х, д (у)), .Щр (Ху(у)))). 2.20. Выяснить, содержится ли функция Х (из Рз' ) в замкну- 1.1 том классе А (здесь О = (01, 02, Оз, 04, о), 01 = (01, 02: Ою о)): 1) Х = Хио(х), А = [Хи(х), ру(Ху(у))1; 2) Х = Хнг(х), А = [Хи(х), 1ру(х)),; 3) Х = Х вЂ „.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
