Гаврилов Г.П., Сапоженко А.А. - Задачи и упражнения по дискретной математике (1048833), страница 26
Текст из файла (страница 26)
б) х~з = 1110 х~ = 1011101 в) те = 11О, хе = 00101; 0 при 1=1, х(Ц -+ у(1 — 1) при з > 2: а) хз = 011, хе ~— — 1111; б) хзз — — 01111, хе —— 00111; в), = 0100, = ШО10; 7) у®= 0 при З= <'), 1=2,3,..., 1 в остальных случаях: а) хз = 101 хз = 110 б) хвз = 0101, хг — — 11011; 117 у д Отобраокенин носледооательноснеей 8) у(б) есть ~-я цифра после запятой в двоичном разложении числа 9/20: а) х< = О, хз е= 001110:, б) хе = 101, хз~ = 1001011; в) х4 =1101, х;" = 00100; 9) у(й) есть 4-я цифра после запятой в двоичном разложении числа 23/28: а) х~1 = 1, хза = 0110; б) хд — — 10, ха = 00110; в) хз = 110 хо = 111101111. ( х(б), если х(1) + х(2) +...
+ хЯ < б/2, 10) у®=4 (1 в ином случае: а) х~ — — 10, ха а—— 0011; б) х~~ = 111, хз — — 01111; в) х4 = 1101, ха = 10010; (О, если х(1) + х(2) +... + х([(4+ 1)/2)) < 4/3, 11) у(1) = ' 11 в ином случае: а) х з = 10, х 4 = 0110; б) х з = 110, т з = 001; в),' = 100101, т 3 = 010101; 1, если б=1 Š— 4 (б) или если 4 > 2 и ~(1 — х(4)) г < 4. х(1), х(е) 4 х(4 — 1) в ином случае: а) х~~ = 01, ха з= 11; б) х~ ~= 101, х~ ~= 0011; в) х „' = 011101, х, '= 000111; 1, если 1=1 е -1 или если 4 > 2 и 1 х(4) > 1+ ~~~ (1 — х(г)) е, 13) у(б) = 0 в ином случае: ) -з 011 -з 101, б) -з в) х" = ИОО1, = 1ОПО. 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, 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) есть 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.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
