Гаврилов Г.П., Сапоженко А.А. - Задачи и упражнения по дискретной математике (1048833), страница 70
Текст из файла (страница 70)
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)), (уо(х), 21(х), , уа 1(х)) С Т((0, Ц), (1, 2...., й — Ц С Т((1, 2...., й — Ц). 2.15. Ц А11,(1) С Т(ЖУ„.г,(1)), 1 = 1, ..., й — 2.
2) А11,(0, й — 1, 7о(х), Уа 1(х)). 2.16. Ц Полна. 2)-4) Не полна. 2.17. Ц Полноту в Яа данной системы можно доказать так: индук- цией по г (1 > Ц установить, что любая функция у из огэ удовлетворяю- щая условию д(х) = х при х > г, порождается функциями из множест- ва (6ог(х), ..., 6о, (х)); затем положить 1 = й — 1. 2) Так как йо (6, аг(йы(х))) = йо, .1(х) (г = 1, 2, ..., й — 2), то дан- ная система порождает каждую функцию из задачи Ц, 3) Принять во внимание, что йь,рг(х -> (й — Ц) -~-1 = 6 зид ег(х) (1 = =0,1,2,...,й — 3).
2.18. Ланная система порождает множестно оа. Используя функ- цию х -~ус(х), можно построить любую функцию, выпускающую ровно одно значение (из Еа). Затем, предполагая, что имеются все функции, выпускающие не более 1 значений (1 < 1 ( й — 2), продемонстрировать, (1) как строится произвольная функция из Рг , выпускагощая 1 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ог(х) и х-сУо(х)1 УгОг(х)) ы Ог х. 0 э'-1 вв 1, х 1+ 1 = х, Уг(И) = = уз(х 4-2) = уо(х), х-~- (уо(х)) = х 4-уо(х) (((хо- Ц -р Ц з-... -~. Ц = х — 1 (единица прибавляется й — 1 раз), уо(х — Ц = 71(х), 6ог(х) = х + уо(х) + +01(х))'-~" +Ог( ))'. 1 — 1 ра* 8) Исходная функция, очевидно, существенная. Обозначим ее чеРез ф(х, У). Имеем ф(х, х) = х, ф(х, х) = х Уо(х — х) -~ (У вЂ” 11(х))Уо(х) 4- 4-х.уо(И) = эг 1(х)., 11 1(вг. 1(х)) = О, ф(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, 11 — 1 = О, х — 0 -о 1 = х 4- 1, х — (у-ОЦ4-1=х — у, 1 х =х, х .х =х, ..., хь х =х' (й — 1 четное число, ибо й простое число, не меньшее 3), 1 — х Ь вЂ” 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"', но е(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 — Ц >9 х(Ц х(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), в) Эквивалентны. Указание.
/(х ) = 11 [010] 10) а) Эквивалентны. Указание. /яз(х(Цх(2)...) = я(Ця(2)... я(1), где я(1) = х(1), если 1 л- 0 л- х(Ц +... -~- х(1) < (1 + 2)/2 = 1/2 -~- 1, 1 в ином случае, / я 4 (х (Ц х(2)... ) = о (Ц о(2)... о(1) ..., где о(1) = х(1), если 0+ 0-Ь 1-~-1+х(Ц+... + х(1) < (1-Ь4)/2 =1/2+ 2, 1 в ином случае.
348 Ответы, указания, решения 10) б) Эквивалентны. в) Не эквивалентны. Рассмотреть функции 7"-4 и 7"-» на слово 0 1 г 1Ц а), б) Не эквивалентны. в) Эквивалентны. 12) а) Не эквивалентны. 6), в) Эквивалентны. Указание. Если х(1 — Ц = О, то неравенство ~~> (1 — х(1))1 (1 ° х(1) =1 выполняется только тогда, когда все х(г) при 1 = 1, 2, ..., 1 — 2, 1 равны 1. 13) а), б) Не эквивалентны. Рассмотреть остаточные функции на слове 0)Ц в) Эквивалентны. 1.8.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
