Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132701), страница 70
Текст из файла (страница 70)
2) ПоложимТ((1, 3)) = Т, о)Х((0, Ц (2) (3)) = оИг о11((0, 3) (1 2)) = ='опг; в) уо(х) ф Т, с оуг и ~ ~уз; д) шах(х, у) с ТО'Мг и ф %г,' е) х уеТ, ф'Иг и Рог)йг. 22.3) 8=(Ц, Йг=ЦО), (1,2)). 4) К = (2),подходяшее разбиение подобрать нельзя.
8) К = (0), Йг = ((О, 1, 4), (2, 3)). П) Е = (О, Ц, гСг = ((О, Ц, (2, ..., й — 1Ц. 12) Е=(0, й — Ц; Р=((0,2), (Ц) при й=З и Р=((О,й — Ц, (1, 2, ..., й — 2)) при й ) 4. 2.3. 2) 2ь — 1. 3) Если Е = И, то )(Т(Е))~"~! = йь . Если 1 < гп = )Е( < й — 1, то ((Т(е))1"г) = гп"' й~ 2.4.
2) В Рг сушествуот 4 различных класса типа ог)1(В), если считать и все множество Рз. В ЕЙ их 14, а в Рз их 51. 3) Пусть (1г, гг,, г ) набор чисел из множества (1., 2....., з). Всего таких наборов о". Упорядочим их в доксикографическом порядке и пере- нумеруем, приписав номера от 1 до з". Набор (1, 1,..., 1, Ц будет иметь номер 1, набор (1, 1,..., 1, 2) номер 2, набор (1, 1,..., 1, 2, Ц номер з ф 1 и т.д.
Если набор (гг, гг, ..., г,) имеет номер ш, то 344 Ответы, указания, дешевев число )Е„) (Е, ) °... ° )Еы! обозначим через 4 . Число функций в множестве Рь(Хо), сохраняюгцих разбиение В = (Еы Ез, ..., Ев), равно )Рл( ' )8„) '.... )Е„( ', где т = в" и суммирование ведется Оом и) по всем наборам длины в", составленным из чисел, принадлежащих множеству (1, 2, ..., в).
2.5. Ц Пусть 4,„обозначает число (Е„( .... )Е,„), где щ -. номер набора (и, ..., Ьв) в лексикографическом упорядочении множества всех наборов длины и, состоящих из чисел 1 и 2 (как в задаче 2.4, 3), если в = 2). Число функций из Рь(Х"), входящих в Т(К)~%(В), при и ) 1 равно 1~ с й — ~ )еоо( ' ...ЦЕ,„) ", где Е~ = Е, Ез = Ее'18, 1=)Е), 02* ° о ) т = 2" и сумма берется по всем наборам длины 2' — 1, составленным из чисел 1 и 2. Если п = О, то таких функций нет. 2) ((%(В)1Т(Е))Ю~! = ~Еь'1Й~ = й — 1, где 1 = (Е). Если и ) 1, то )(11(В)1Т(е))" ! = (й — 1) ~ )Е„) ' -... ~Е,,) ' (1, т, 11 и е( такие Оз "оО же, как в задаче Ц).
3) й,если п=О,и 1' йь ' ф(й — 1)" ~ ~Е,о~'.. ~Ко,/",если и)1. 02». о ) 2.0. 2) (2!)(й — 3)5 3) х —',, хз х4 б) хауз 7) хуз 4- ту+ ь — г 9) (й — Ц(1 — (х-~-2)ь ') = ~) ( . )2'х~ *=о ь — 3 10) 1 — (х — хз — 2) ' = ~( — Ц'~ ( )2'х~ '~ '(1 — х)~ =а 2.8. Ц достаточно реализовать полиномом функцию 21о(х), ибо 21 (х) = 2 1о (х — 1) (1 = 1, 2, 3), 21а (х) = 2 -~- х -~ хе = 2 -т Зх -~- Зхз = 2 -~ х -т +2х'+ Зхз = 2+ Зх+ 2хз+ хз.
2) Если ((х) б Рв и 1'(Е4) С (О, 2), то 1(х) можно представить в з виде 1 Ь, ° 21,(х), где 6, б (О, Ц (1 = О, 1, 2, 3). Если 1" (Ее) С (1, 3), то =о рассмотреть функцию д(х) = Йх) 2.9. Функции 1(х) — уз(х) и 1" (х) — 1~(х) принимают значения только из множества (О, 2). 2.10. б4. ВРе справедливысоотношения2хз = 2х = 2х иЗх = 2х+ х .
2.11. Ц Сравнить друг с другом функции х, хз и х из Ра. 2) В Рв выполняется соотнозпение Зх' = Зх. 3) Либо 6=2 и о=2,5,либо 6=4 и а=1,4. 2.12. Ц, 2), 4) Не представима. 3), 5) Представима. 2.13. 2) Т((1, 2)). 3) аМ((0, Ц, (2, ..., й — Ц). 5) Т((0, й — Ц). 9) Т((1, й — Ц). 13) а)4((0), (1, 2, ..., й — Ц). 15) Т((1, й — 2)).
Гас Пй й-заочные яогвви 345 2.14. Ц Такой подсистемой является множество (уо(х), х + у). 2) (О, х "; у, х у) С Т((0)), (уо(х), уг(х), , уа г(х)) С Т((0, Ц), (1, 2...., й — Ц С Т((1, 2...., й — Ц). 2.15. Ц АгЗ,(г) С Т(Жу„.г,(г)), г = 1, ..., й — 2. 2) АгЗ(0, й — 1, 7о(х), Уа г(х)). 2.16. Ц Полна. 2)-4) Не полна. 2.17. Ц Полноту в Яа данной системы можно доказать так: индук- цией по г (г > Ц установить, что любая функция у из оя, удовлетворяю- щая условию д(х) = х при х > г, порождается функциями из множест- ва (6ог (х), ..., 6о, (х)); затем положить г = й — 1.
2) Так как йо (6, аг(йы(х))) = йо, . г(х) (г = 1, 2, ..., й — 2), то дан- ная система порождает каждую функцию из задачи Ц, 3) Принять во внимание, что йь,рг(х -> (й — Ц) -~- 1 = 6 зид ег(х) (г = =0,1,2,...,й — 3). 2.18. Ланная система порождает множестно оа. Используя функ- цию х -~ус(х), можно построить любую функцию, выпускающую ровно одно значение (из Еа). Затем, предполагая, что имеются все функции, выпускающие не более г значений (1 < г ( й — 2), продемонстрировать, (г) как строится произвольная функция из Рг, выпускагощая г 4- 1 значений. 2.19. Ц, 4), 13) Породить систему Россера — Туркетта.
2), 1Ц Пороцить систему Поста. 3) Если й нечетное, то породить систему Поста. При четном й породить систему Россера. Туркетта. 5), 8) — 10)., 12)., 15) Породить заведомо полную систему (уо(х), х Ч- д) см. задачу 2.14, Ц. 6) Полноту этой системы можно установить методом, подобным методу доказательства полноты системы Поста. 7)., 14), 16) Породить систему (х, гпш(х, у)).
2.20. 2) Функции х+ у и ху+ 1 существенные. Строим функции х, 6ог(х) и х-с ус(х); угОг(х)) ы Ог х. 0 э'-1 вя 1, х 1+ 1 = х, уг(И) = = уз(х 4-2) = уо(х), х-~- (уо(х)) = х 4-уо(х) (((хо- Ц -р Ц з-... -~. Ц = х — 1 (единица прибавляется й — 1 раз), уо(х — Ц = уг (х), 6ог (х) = х + уо(х) + +Ог(х))'-~" +Ог( ))'. о — г ра* 8) Исходная функция, очевидно, существенная. Обозначим ее через ф(х, у).
Имеем ф(х, х) = х, ф(х, х) = х уо(х — х) -~ (У вЂ” уг(х))уо(х) 4- 4-х.уо(И) = эг г(х)., эг г(вы г(х)) = О, ф(0, х) =ус(х) + х., ф(х, 0) = = йог(х) Палее применяем теорему С. Пикар. 2.21. Ц, 3), 5), 8), 10) Полна при нечетных й и не полна при четных й. 2), 4), 6), 7), 9), 14) Не полна. 1Ц Полна при четных й и не полна при нечетных й. 12), 13) Полна при й = 3, не полна при й > 4. 15) Полна. 2.22. 2) При й простом достаточно построить систему (уо(х) г х + у) "- см. задачу 2.14, Ц. Имеем х — х ч- 1 = 1, 1г — 1 = О, х — 0 -о 1 = х 4- 1, х — (у-ОЦ4-1=х — у, 1 х =х, х .х =х, ..., хь х =х' (й — 1 четное число, ибо й простое число, не меньшее 3), 1 — х~ = уо(х), 0 — х = -х, х — (-у) = х -~- у.
346 Ответы, указания, решения 9) При 1о простом строим функции 1, х + у, х у. Имеем х ° х — хг = О, 0 Е 0 + 1 = 1, х -> 0 -Н 1 = х -'; 1, (х + Ц + 1 +... + 1 = х — 1 (единица прибавляется к — 1 раз), х -Н (у — Ц -Н 1 = х+ у, х(х+ у) — х = х у. 2.23. 2) Рассмотреть систему Поста. 4) Добавляя, например, функцию х, легко получить систему Поста. 7) Непосрелственно применить критерий полноты класса полнномов в Рю 2.24. Ц При 1' = 4, 6 можно рассмотреть функцию 7(х + 1, х).
3) При й = 4 можно рассмотреть любую из функций (7(0, х))г, (1"(х ~- 1, х))г нли 1 — 1(2, ), а р й = 6 функцию 1 — 1"(4, ). 2 25. Ц (1 — 1, уо(х), х — 'у). 2) (уо(х), х — 'уг). 3) ( х, ппп (х, у), х 4- у). 4) Если к нечетное число, то базисами являются, например, подсистемы (х+ 2, шах((х,у)) и (х+ 2, х — у). Если й четное число, то базисом является множество (й — 1, х+ 2, х — ' у). 5) (уо(х)г х+ У ). 2.26. Учесть, что (О, 1,..., к — 1, зя г(х), ппп(х, у), шах(х, у)) С С ЧХ((0, .1, ..., /о — 2), (й — 1)), ппп(У,(х), Л~ г(х)) = 0 (О < г < го — 2) и гпвх(,уо(Уо(х)),,уо(х)) = к — 1. 2.28. 2) Из задачи Ц вытекает, что число таких предполных классов в Рь не больше, чем число всех подмножеств множества Р .
Но ~Р ~ = к. '. Ю 01 г. (гг ьв Значит, мощность множества всех подмножеств из Р~ равна 2г 2.29. 2) Обозначим функцию уг (х) уг(у) через оз(х, у). Имеем Зг(х х) = 0 Зг(0; х) = Ог(х, 0) = Зг(0, 0) = О. Значит, в ггг содержится только одна функция, зависящая не более чем от одной переменной, и зта функция -.- тождественный О. 2.32. Подсчитать число несугцественных функций в Ря'О и полученное выРажение вычесть из зо . Число несУщественных фУнкций в РоЕ ~ Рава — 1 но (к1) п+ ~ ( — Ц' (1,.) (К вЂ” г) ,=1 Глава 1У 1.1.
Ц, 3), 4), 9), 1Ц, 12) Является. 2), 5) -8), 10) Не является. 13) Является, так как при 7 < 1 ( 13 выполняются неравенства 1 ( < 201 — 1г — 90 ( й 14) Не является, ибо у(9) = х(10). 12. Ц Не является, так как 1(0") = 0"', но 7(01 (0)") = 1 ', те. первый символ выходного слова не определяется однозначно первым символом входного слова. 2) Является; 7"(х ) = х(Ц И(2).,.
2(1)... 3) Не является. Рассмотреть 1(0 ) и 1(0(Ц ). 4)г 7), 10), 12) Является. 5), 6), 8), 9), 1Ц Не является. Гл. Л'. Оераниченао-део>ерминироеанные функции 347 13) Является; /(х ) = 1х(Ц 1х(3) 1х(5)... 14) Является; /(х ) = х(Ц Ох(З) Ох(5)..., ибо 1/3 = О, (ОЦ = 0,010101...
15) Является; /(х ') = О, так как 1/7 = О, (ООЦ = 0,001001001... 16) Является. 1.3. Ц Можно; д(х ) = 0 '. 2) Можно; д(х ) = у(Цх(2)...Я(1)... 3) Можно; д(х ) = Ох . 4), 5), 9) Можно. б), 8) Нельзя; рассмотреть входные слова х> — — 1 [0] н хз — — 1". 7) Можно; д(х ) = 0[х(Ц Зсх(2)] 10) Можно; д(х ) = Ох(Ц у(З)... у(1),..., где у(1) = = х(1 — Ц 6> х(Ц х(2) 10 1. 1А. Ц г(/) = 1, г(д) = 4. 2) г(/) = 1, г(д) = 5. 3) г(/) = 4, г(д) = 5.
4) г(/) = 2, г(у) = 3. 5) г(/) = 2, г(д) = 3, ибо 2/3 = 0,(10) = О, 101010 ... б) г(/) = >(д) = оо,так как 1/о>2 ††иррациональноечис его двоич- ное разложение является непериодической дробью. 9) г(/) = 2, г(д) = 4. 1.5. Ц Пусть оо, е>, о>, е, ..., е, >, о, .> е, -- вершины и ребра ориентированной цепи Я, начинающейся в корне дерева и заканчивающейся тем ребром, где изменена метка. Если вершина дерева не принадлежит этой цепи, то после изменения метки на ребре е, она (и растущее из нее поддерево) останется в том же классе эквивалентности, в котором нахо- дилась раньше.
Новые классы эквивалентности могут возникнуть только при «распределенни» вершин, содержащихся в цепи Я. Следовательно, вес первоначальной функции может измениться не более чем на 11 Лости- жимость указанной оценки вытекает, например, из рассмотрения дерева, соответствующего функции /(х" ) = 0 2) ]г(/) — г(д)[ < 21 — 1. 1.6. Ц, 2), 4) — 6), 8) — 10) Эквивалентны. 3), 7) Не эквивалентны.
1.7. Ц а) Не эквивалентны. 6) Эквивалентны. 2) а), в) Не эквивалентны. 6) Эквивалентны. 3) а), 6) Эквивалентны. в) Не эквивалентны. 4) а), в) Эквивалентны. 6) Не эквивалентны. 5) а), в) Не эквивалентны. 6) Эквивалентны. 6) а), в) Эквивэлонтны. 6) Не эквивалентны. 7) а) Эквивалентны. 6) Не эквивалентны. 8) а), в) Не эквивалентны. 6) Эквивалентны. Указание, /(х ) = 01[1100]"'. 9) а) Не эквивалентны. 6), в) Эквивалентны. Указание.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
