Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132709), страница 27
Текст из файла (страница 27)
С > 3; < у(С) = 1, С = 1, 2, у(С) = (д(С вЂ” 2) -+ х(С вЂ” 1)) в -в х(С вЂ” 2). х(С вЂ” 1). х(С), С > 3, 119 у д О~пображеаил лоследоеительнос(аей у(1) = х(1), у(2) = х(1) -~ х(2), у(1) = (х(1 — Ц вЂ” э х(1 — 2) х(1)) (у(1 — 2) — + — > х(1 — 2)х(1 — 1) х(1)), 1 > 3; Д: у(1) есть 1-я цифра после запятой в двоичном разложении 2,13, у(1) есть 1-я цифра после запятой в двоичном разложении 1/3; Д: у(1) есть 1-я цифра после запятой в двоичном разложении 7/60, у(1) есть 1-я цифра после запятой в двоичном разложении 13,115 7) числа числа 8) числа Л числа 1.10. Выяснить, является ли функция 7' Е гз л о.-д.
функцией, и наити ее вес ) (1 при 1=1, (х(1 — 1) при 1 > 2; 1) у(1) = 3у1в )х(1) при 1=1, (у(1 — 1) при 1 > 2; х(1) при у(1 — 1) з х(1) при 1 > 2; 5 у ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ | ~ | 1 приз=1,2, т(1 — 2) при 1 > 3; б у ~ ~~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ | ~ ~ | х(1) при 1 = 1, х(1) 6~ х(2) Ю... Ю х(1) при 1 > 2; ж т= '"'" '=' <ъ~1 — Д вЂ” 21 при 1 > 2; /х(1) при 1 = 1, 2, (х(1).х(2) ... х(1 — 1) при 1 > 3; 9) у(1) = 10) у(1) = х(2[(1 — 1) /2) + 1), 1 > 1; ( х(б), если 1 нечетное число, 11) у(1) = ' 1х(1), если 1 четное число; х(1), если 1 = 1, 12) у(1) = 1, если 1 --- нечетное число и 1 > 3, х®2) — з у®2), если 1 — — четное число: 10 при 1= 1, (х(Х) при 1 > 2; Гх(1) при 1 = 1, й) у(и) =~ 10 при 1>2; 4.
Выявление свойства ограниченной детерминированности функции. Порожденные и автономные функции. Строение классов эквивалентности. Мощности некоторых множеств отображений. 120 Рп. !7. Ограниченно-детерминированные функции у,(Ц =О, уг(Ц = 1, 20)1ЕР,'„и 1: (1) (1 Ц 1>2 уг(1) = у1(1 — Ц, .1 > 2; у1(Ц вЂ” Х1(Ц' хг(Ц~ 20 УбР' и уг(Ц = х, (Ц ч хг(Ц, у1(1) = хг(1) Ч хг(1) М уг(1 — Ц, 1 ) 2, уг(1) = Х1 (1) .,(1) у,(1- Ц, 1 > 2.
11усть 21(Х1,хг, °, Хп) Уг(Х1 хг~ ° ~хп); ° ~ гт(Х1,Х2, ..., Хп) функции вида Еь х Еь х... х Еь — 1 Е1, где к > 2 и 1 > 2. и рпз Оператор 1рй е у из Р",', „(т.е. угу, е, е = (х, ..., Х„,) = = (у-', уг~,..., у~у)) называется оператором (или функцией), по- рожденным (порожденной) функциями 11, 12, ..., 1„„если для всякого 1 ) 1 = 11(Х1(1) хг(1); ..., Хп(1)), 1'= 1, 2, ..., оь является ли порожденной функция 1 Е Рг „, если: у(Ц =1, у(1) = х(1) в у(1 — Ц, 1 ) 2; и < у(Ц =О, у(1) = х(1 — Ц вЂ” г у(1 — Ц, 1 > 2; и ~ у(1) = х(1), если 1 = 2в — 1, в ) 1, у(1) = х(2) — 1 х(1 — Ц.
Х(1), если 1 = 2в, в > 1; рм(1) Выяснить, ЦгеР' 2) г Е Рг 'п 3) г е Рг' ~ О, если 1 .- нечетное число, 13) (1)=1 (х(1,12 -Ь Ц, если 1 четное число; 14) () 1 при 1=1,2, у(1 — 2) ~В х(1 — Ц при 1 > 3; О, если 1=1, 15) у® = х(Ц ~Ву(1 — 2), если 1 нечетное число и 1> 3, х(1 — Ц, если 1 - четное число; )1 при 1=1, <х(<1/2)) -+ х(1) при 1 > 2; 16) у(1) = О, если 1=1,2,...,1, у(1 — Ц, если 1 > 1+ 1, 1 > 1; < 18) у(1) есть 1-я цифра после запятой в двоичном разложении числа 7/15; 19) у(1) есть 1-я цифра после запятой в двоичном разложении числа 11 124; у 1.
Отоброжения носледоеительностец 121 4 еР" и 4) 1 Е Р2'л и 1: е(у(1) = (1 — 1) оЗ х(1) о, у(1 — 1) 1 > 2. 5) 7(хн) = 1(х(1).х(2) — 1 х(2))... (х(1) х(2) -+ х(2))... (т.с. при 1 = 1 «выход» совпадает с 1, а при 1 > 2 — с х(1) х(1) — е х(1)); 6) 1(х") = у(1) у(2)... У(1)..., где у(1) есть |-я цифра после запятой в двоичном разложении числа 1/7; 7) зс(х ) = у(1) у(2)... 1У(1)...
где у(1) есть 1-я цифра после запятой в двоичном разложении числа 1/5; у„(1) = О, Р 2 . у (1) 2,л у (1) — у (е Ц > у (1 1) е ) 2. уз(2) = х(1) — 1 уэ(1 — 1), 1 ~ )2; У1(1) = х(1), 9) 1 Е Р2' И 1: У1(1) (У1(1 1) е Уз(1 1)) 1Х(1) с 3 2~ у2(с) Х(1),. с ~ 31~ у1(1) = уз(1) = х(1)~ 10) Х Е Рэц и У: У1(1) = У1(1 1) ц1х(1) т 3 2' У2(~) У2(~ 1) ~ У1(~ 1), ~ ~ 32' 1У(1) = х1(1) — е хэ(с), если 1= 2з — 1, е > 1, 11) 1 Е Рз*о и 2: у(1) = ~1(с) ~2(с) Ю х1(1) Ь 1, если 1 = 2з, е > 1. 1.12. Из определения порожденной функции (см.
предыдущую задачу) следует, что вес порожденной функции равен 1. Доказать, что справедливо и обратное утверждение: если 1 Е Рл в и вес функции 1 равен 1, то существует функция Ух А — э В, порождаюп1ая функцию 1, т.е, Дх' ) = у ' = у(1) у(2)... У(1)..., где у(1) = оо(х(1)) при всяком 1 ) 1, х(1) Е А и у(1) Е В. 1.13. 1) Функция 1 из Р2 определяется следующим образом: 1(х ) = [О ...
01 , где 1 -- произвольное фиксированное целое число., не меньшее 1. Показать, что: а) у функции 1' вес каждой остаточной функции равен 1+ 1; б) каждый класс эквивалентности остаточных функций у функции 7 является счотно-бесконечным множеством.
2) Пусть 2"(х ') Е Р2 „и 2"(х") = 0... 0[1['', где 1 произволь- 1 ное фиксированное целое число, не меныпес 1. Показать, что; а) для каждого г, удовлетворяющего неравенствам 1 < г < 1+ 1, у функции 1 существует в точности 2' е»1 остаточных функций веса г:, 122 Гж 17. Ограниченно-дегнернинированные функции б) функция 1 имеет только один бесконечный класс эквивалентности остаточных функций и его элементы -- порожденные функции.
3 ) Пусть ((х ) Е Рз и зе(х ) = у(1) у(2)... у(1)..., где О, если 1<1<1, у(1) = х(1) х(2).... х(1), если 1 > 1+ 1, и 1 -- произвольное фиксированное целое число, не меньшее 1. Доказать, что: а) для каждого г, удовлетворяквщего неравенствам 3 < в < 1+ 2, у функции 1 существует лишь одна остаточная функция веса г; б) функция з" имеет ровно два бесконечных класса эквивалентности остаточных функций, причем элементы одного из них являются порожденными функциями, а другого функциями веса 2. 4) В задаче 3) изменим только одно условие: если 1 < 1 < 1, то у(1) = 1. Обозначим новую функцию через 1"ы Доказатгн что: а) у функции г1 в точности два бесконечных класса эквивалентности остаточных функций, и элементы одного из них являются функциями веса 2, а другого порожденными функциями; б) остальные классы эквивалентности остаточных функций функции 1'1 конечные, и при 1 > 2 среди них ровно 1+ 1 одноэлементных классов; в) вес фУнкции уз Равен 21+ 1.
5) Функция д' из Рз определяется следуквщим образом: О ... 0(1), если х = 0... 0 х(1+ 1) х(1+ 2) .. 1(хч' ) = 0" в ином случае, произвольное фиксированное целое число, нс меньшее 1. Доказать, что: а) функция 1 имеет ровно два бесконечных класса эквивалентности остаточных функций, и элементы каждого из них . - порожденные функции; б) остальные классы эквивалентности у функции г" одноэлементные: в) для каждого г, удовлетворяющего неравенствам 3 < г < 1+ 2, у функции Г существует единственная остаточная функция веса г. 1.14. Выяснить, сколько у функции г" Е Рз конечных и сколько бесконечных классов эквивалентности остаточных функций, выписать явно (в какой-либо форме) все остаточные функции (по одной из каждого класса эквивалентности) и найти их веса: ('у(1) = О, ) ~' (у(1) = х(1) Юх(1) Ю1, 1 > 2; ( у(1) = 1, 2) 1: у(1) = х(1).х(1), г > 1; 3) 1: '( (1) (1) ~ (1 1) 1 > 2 123 у Д Отобрадсения последовательностей 4 ( у(Ц = х,(Ц, ) ~' [ у(1) = у(1 — Ц, 1 ) 2; *) д ' [ у(1) = х(1) — «у(1 — Ц, 1 ) 2; 6) ((хч ) = [010) ; [ОЦ", если х = 0 [ОЦ'1х(21+2)х(21+3)..., если х ' = = Оз'1х(21+ 2) х(21 + 3)...
и 1 > 1, [ОЦ х(2/+Цх(21+2)..., если х =0«Я '1х(21+ Цх(21+2)... и 1 >1., 7) ((х ) = х в ином случае; 8) «е(х") = [Ох(Ц); 9) ((хм) = [х(Ц х(2) Ц"; ( у(Ц = у(2) = О, ) (' [у(1) = х(1 — 2) 6«х(1)., 1> 3. (у(Ц =О, ) «з,д У ~у(й) у(1 Ц 1) 2. (у(Ц =1 )У ад,( [у(1) х(2) х(1 Ц «х(е Ц 1)2.
3) ( Е Рз"„' и (: у(1) = х(Ц ... х(1) — «х(Ц х(1), 1) 1; у(с) = х(Ц вЂ” «(х(с) — «х(Ц), если 1 = Зв — 2, в > 1, и (; у(1) = у(1 — Ц вЂ” «(1 — Ц х(й) если 1 = Зв — 1, .з > 1, у(1) = у(1 — 2) 6«у(1 — Ц, если 1 = Зв, в > 1; 4) ( е Ра'~ (у(Ц = О: ~' '[ у(1) = х(2) -+ (х(Ц вЂ” «х(1)), 1 ) 2; у(1) = 1, если 1 = 2' (ъ' = О, Ц 2,... ), 6) ( Е Р,'д и (; у(1) =у(Ц |Зу(2) ЕВ... Фу(Х вЂ” Ц в ином случае: 1.15. Функция 7' из Рд л называется автономной (или константой, или функцией без выхода), если она принимает постоянное значение (на множестве А"'), т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
