Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1055357), страница 70
Текст из файла (страница 70)
Затем, предполагая, что имеются все функции, выпускающие не более г значений (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), в) Эквивалентны. Указание. /(х ) = 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) б) Указание.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
