Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132709), страница 71
Текст из файла (страница 71)
Обозначим ее чеРез ф(х, У). Имеем ф(х, х) = х, ф(х, х) = х Уо(х — х) -~ (У вЂ” 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. Ц Указание. Лля любой остаточной функции 1з функции уа имеем у(Ох(2)... ) = у(Ц... и 1в(1х(2)...) = у(Ц... 2) Указание. Всякая остаточная функция Зз функции ув, отличная от самой функции Д, обладает следуюшим свойством: ~о(Ох(2)... ) = 1х(2)... 5) У к аз ан не. Если ш остаточная функция функции 1в, то уз(0 ) = 0". Сравнить с ~~ (О ). 6) Указание.
При в ) 2 остаточнал функция у функции зв, порожденная словом х'", удовлетворяет условию Зз(Ох(2)... ) = ~р(1х(2)...). 1.9. 2) Можно взять остаточную функцию функции ув, порожденную произвольным словом длины 2. 5) Исследовать остаточную функцию функции ув, порожденную словом хэ = 11. 6) Рассмотреть остаточную функцию функции ув, порожденную словом хз = 011. 8) ув(х7 ) = 00)011Ц, Уг(х ') = )110Ц". 1.10. Ц, 2), 4), 5), 1Ц, 12), 20) О.-д.
функция веса 2. 3), 7) 10), 2Ц О.-д. функция веса 3. 6), 18) О.-д, функция веса 4. 13), 16) Функция не является ограниченно-детерминированной. 14), 19) О.-д. функция веса 5. 1ог) Вес функции равен 7. 17) Вес функции равен 21. 1.11. Ц Порождается булевой функцией д(х) = 1. 2), 3) Порожденной не является. 4) Порождается булевой функцией д(х) = х. 5) Является порожденной. 6), 7) Порожденной не является. 8) Порождается парой булевых функций: дз(х) = 0 и дз(х) = 1. 9) Порождается парои булевых функций д1(х) = х и дг(х) = х. 10) Порожденной нс является. 1Ц Порождается булевой функцией д(хц хз) = хз — э хз. 1.13. Ц а) У функции 1(х ) попарно неэквивалентные остаточные функции исчерпываются функциями г" (хч ), уя.
(х ) Н = 1, ..., Ц, где х' произвольное входное слово длины ~,'. Вес каждой из этих 14-1 функций равен 1-'; 1. 2) б) Указание. Если х" входное слово длины в ) 1, то уя*(х ) = 1 3) а) Соответствуюшая остаточная функция веса г (г = 3, ..., 14-2) порождается входным словом 1' "~~ (если г =14-2, то слово пустое). Гж Л'. Ограниченно-детерминированные функции 349 б) Один из бесхонечных классов эквивалентности состоит из функций, тождественно равных О, а другой из функций вида 1: у(1) = х(1) 3с 8с х(2) 3с ... ус х(1), 1 > 1. 4) а) См, задачу 3), б).
Представители бесконечных классон эквивалентности такие же. 5) а) Элементы одного бесконечного класса эквивалентности порождаются словами вида 0 х' (е ) 0), а другого - словами вида х'", отличными от 0"' (ги = 1, ..., 1), и еще словами х(хг, где х,' слово, отличное от 0', а хг -" произвольное слово длины и ) 1. б) Кроме остаточных функций из двух бесконечных классов эквивалентности у функции 1(х ) имеются еще остаточные функции, порождаемые словами 0' (е = О, 1, ..., 1 — 1).
Эти функции попарно не эквивалентны, и если з~ > ег, то 15., является остаточной функцией функции 15. в) Следует из а) и 6). 1.14. 1), 2), 4), 5) Два бесконечных класса эквивалентности и один одноэлементный. Вес функции 1 равен 3. 3), 8) Три бесконечных класса эквивалентности и адин одноэлементный. 6), 7) Три бесконечных класса эквивалентности. 9) Семь бесконечных классов эквивалентности и три одноэлементных. 10) Четыре босконечных класса эквивалентности и три одноэлементных.
1.15. 1), 11) Автономнвл функция веса 2. 2), 3) Автономная порожденная функция. 4) Автономная функция веса 3. 5) Автономной не является. 6) Автономная функция бесконечного веса. 7) Автономная функция веса 21. 8)-10) Автономная порожденная функция. 1.17. 2) Рассмотреть функцию 1(х ) = Ох . Ее вес равен 2. Вершина ранга 2, соответствующая входному слову 1 = 11, не эквивалентна корню дерева (вершине ранга 0), так как 11 (х ') = 1х' . 1.19. 1) Мощность гиперконтинуума (2 ). 2) Мощность континуума (с). 3) Множество счетно-бесконечное. 4) Мощность континуума. 5) 2' .
6) 4' 7) Мощность континуума. 8) Множество счетно-бесконечное. 9) Мощность континуума. 10) Мосцность каждого из множеств равна с. 2.1. 1) у(1) = д(1 — Ц -Э х(1), С1(1) = х(1), д(0) = О. 2) 11(1) = д(1 — 1), д(1) = х(1) ! 9(Х вЂ” 1), д(0) = О. 3) Диаграмма Мура изображена на рис. 0.4.1, а. 4) Р(1) = х(С) чг(1 — 1) э дг(С вЂ” 1), чг(1) = чс(С вЂ” 1) Ечг(С вЂ” 1), 9г(с) = (с) 9г(1-1) и (в(1 — 1) -9 (с-1)), Ог(о) = Ог(0) = о 5) Рнс. 0.4.1, б. 6) Рис.
0.4.1, е. 7) Рнс. 0.4.1, е. 8) Рис. 0.4.1, д. 9) Рис. 0.4.1, е. 10) Рис. 0.4.1, ха 12) Рис. 0.4.1, з. 13)-15), 22) Указание. Вес функции равен 2. 16), 18), 19), 24), 28), 35) У к аз ание. Вес функции равен 3. 350 Ответы, унвзвннж решенвя 0(Ц о(о) цо) Цц о о о(ц цо) 1 о(ц 3 0(ц цц цц о(ц о(о) ЦЦ '(') ' ЦЦ Цо) 2ЦЦ 4 д ЦЦ 0„, 0,0, 0(ц о 1р) пр)Ю цц (о) оВ), ЦЦ ЦЦ цо) ж о(о) Рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
