Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1055357), страница 26
Текст из файла (страница 26)
1.8. Доказать, что д. функция /1 11, х4з = 0101; (/4 б Рз ) не является остаточ(здесь, как обычно, считаем, что ной функцией д. функции /о Е Рз „ /о = /о(х ') = у' = у(1)у(2)... у(1) и /4 = /4(хм) = у = у(1)у(2) .. " у(б)" ): 1) Уо: ) )'у(1) = х(1), <уИ) = х(1) Е*(1), у(1) = О, у(б) = х(4), 1 > 2. /у(1) =1, 4>2, ' <у(1)=х(1)еех(4), ~>2; у(1) = О, у(~) = х(1) 4 х(1 — 1), 4 > 2; у(1) = *(1), у(4) = х(4) -4 у(1 — 1), 1 > 2; 3) Уо.
у(1) =х(Е), 4>1, 8) у(б) есть ~-я цифра после запятой в двоичном разложении числа 9/20: а) х< = О, хз е= 001110:, б) хе = 101, хз~ = 1001011; в) х4 =1101, х;" = 00100; 9) у(й) есть 4-я цифра после запятой в двоичном разложении числа 23/28: 118 4 ) Уо: у(С) = у(С вЂ” 1) -+ х(С вЂ” 1), С > 2, у(1) = 1, у(С) = х(С вЂ” 1), С > 2; 5) ф /у(С)=О, С=1,2, у(С)=х(С) у(С вЂ” 1), С>2, "' )у(С)=1, С>3; 6) Уо: у(С) =х(С), С=1,2, у(С) = у(С вЂ” 2) в у(С вЂ” 1), С > 3, | ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ! ~ ! ~ ~ | ~ ~ ~ ~ ! ! ~ ~ | ~ ~ ~ ~ ~ ~ у д(1) =х(С), С=1,2, у(С) =1, С>3. 1.9. Доказать, что д.
функция ~с является остаточной функцией Д. фУнкции Хо Е Рг а (считаем, как обычно, что Се = 1о(х ) = = уы = у(1) у(2)... д(С)... и (~ = С~(х' ) = дм = у(1) у(2)... у(С)...) 1) Уо Л 2) Уо Л 3) Уо Л 4) Уо Л 5) Уо Л 6) Уо Х'т !7, Ограниченно-детерминированные функции < д(1) = х(1), у(С) = х(С вЂ” 1) х(С), С > 2, < у(1) = О, у(С) = х(С вЂ” 1) в х(С), С > 2; < у(Ц =О, у(С) = у(С вЂ” 1) в х(С), С > 2, у(1) = х(1) у(С) = х(С) Н у(С вЂ” 1), С > 2; < у(1) = 1, у(С) = х(С вЂ” 1) Юх(С), С ) 2, с у(1) = х(1), у(С) = (х(С вЂ” 1) в х(С)) в х(С вЂ” 1). х(С), С > 2; < у(С) = х(С), С= 1, 2, 3, у(С) = у(С вЂ” 3) в у(С вЂ” 1), С > 4, с у(С) — О, С вЂ” 1, 2, у(С) = 1, С > 3; < у(С) =х(С), С=1,2, у(С) = у(С вЂ” 2) в х(С), С, > 3, < у(С)=х(1), С=1,2, у(С) = х(С) — э у(С вЂ” 2),. С > 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-я цифра после запятой в двоичном разложении 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'(х ) = у(1) д(2)... д(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) с ~ 32 у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 Е Рз*о и 1: д(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 определяется следующим образом: Х(х ) = [О ...
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, у функции Г существует единственная остаточная функция веса г.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
