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