Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132701), страница 71
Текст из файла (страница 71)
/(х ) = 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с 3с х(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р) пр)Ю цц (о) оВ), Цц ЦЦ цо) ж о(о) Рис. 0.4.1 17), 25), ЗО), 37) Указание.
Вес функции равен 6. 2Ц, 23), 27) У к аз анно. Вес функции равен 4. 32), 34), 36) Указание. Вес функции равен 5. 39), 40) Указание. Вес функции равен 7. 2.2. Ц Рис. 0.4.2, а. 2) Рис. 0.4.2, б. 3) Эквивалентны вершины 1 и 2. Рис. 0.4.2, в. 4) Рис. 0.4.2, г. 5) Рис. 0.4.2, д. 6) Эквивалентны вершины 1, 2 и 3; рис. 0.4.2, е. 7) Эквивалентны вершины в парах (О, 2) и (1, 3); см. рис. 0.4.2, ж. 8) Эквивалентны вершины в тройках (О, 3, ое) и (1, 2, 4):, рис. 0.4.2, з. 9) Рис.
0.4.2, и. 10) Рис. 0.4.2, н. 1Ц Рис. 0.4.2, ж 2.3. Ц Добавить дугу (1, 0) с меткой 0(0). 4) Добавить дугу (О, Ц с меткой 0(Ц и дугу (3, 0) с меткой ЦО). 7) Добавить дугу (2, 3) с меткой ЦО). 2.4. Ц Вес равен 1. 2), 5) Вес равен 4. 3), 7), 8) Вес равен 2. 4), 6), 9), 10) Вес равен 3. 2.5. Ц Подходящая диаграмма изображена на рис. 0.4.3, а. 2) Рис. ОА.З, б. 3) Рис. ОА.З, в. 4) Рис. 0.4.3, г. 5) Рис.
0.4.4, а. 6) Рис. 0.4.4, б. 7) Рис. 0.4.4, в. 8) Рис. 0.4.3, г. 352 Ответы, указания, решения ЦЦ ЦЦ 0<0) <0) 0Ж Цо) 0Р) ЦЦ <0) 0<Ц ЦЦ 0Ц0) 3 0 3 е Рис. 0.4.4 2.6. Ц Число различных диаграмм Мура, получающихся из данного ориентированного графа, равно 32. Приведенными являются 24 диаграммы; они соответствуют различным о.-д.
функциям из Рг ',„. дг 2) Всего 64 диаграммы Мура, 16 диаграмм не являются приведенными, цз 48 соответствуют различным о.-д. функциям веса 2 из Р, *„. 3) Всего 32 диаграммы, 24 приведенные, и все они задают различные о.-д. функции из Р, 4) 16 различных диаграмм, приведенных 12, и все они соответствуют гл различным о.-д. функциям из Р, *„. 5) 512 различных диаграмм, 480 приведенных (они соответствуют разным о.-д, функциям веса 3 из Р, *, ).
гл 6) 256 различных диаграмм, 240 приведенных (все они соответствуют разным о.-д. функциям нз Рг ' „). нг 7), 8) 512 различных диаграмм, 432 приведенных (все они соответствуют разным о.-д. функциям веса 3 из Рг '„). дз 9) 512 различных диаграмм, приведенных 336. Число разных о.-д. функ- дг ций из Р, '„, задаваемых этими приведенными диаграммами, равно 168.
10) 64 различные диаграммы, привеценнвгх 60, и все они соответствуют разным о.-д. функциям веса 3 из Р ' цг 1Ц 4096 (= 2'г) различных диаграмм; приведенных 4032 (они задают попарно различные о.-д. функции веса 4 из Р, ', ). нз 12) 512 различных диаграмм, приведенных 504 (они соответствуют разным о.-д. функциям веса 4 из Рг '„„). 63 2.7.
2) 144 о.-д. функции. 2.8. Ц дЯ = дЦ1 — Ц их®дел — Ц, дг(1) = хЯ дэба — Ц, дгф = т11)дг(Е Ц, дцб) = 1, дг(0) = О. Гл. 1У. Оераниченно-детерминироеанные функции 353 Вес суперпозиции фг(фг) равен 2, она может быть задана следующими каноническими уравнениями и начальными условиями: у(1) = х(1) г Ч(1 — Ц, Ч(1) = х(1), Ч(0) = 1, т.е. она «функционирует» так же, как функция )ь 2) Указание. Вес суперцозиции равен 3. 3) Суперпозиция является функцией веса 1. 5) Суперпозиция фг (фг) имеет вес 2 и может быть задана следующими каноническими уравнениями и начальным условием: у(1) = Ч(1 — Ц, Ч(1) = х(1) — э Ч(1 — Ц, Ч(0) = О.
6) Указание. Вес суперпозиции равен 4. 7) Указание. Суперпозиция имеет вес 2. 8) Указание. Вес суперпозиции равен 5. 2.0. Ц Указание. Получается о.-д. функция веса 2. 2) У к а з а ни е. Получается функция, порожденная отрицанием. 7) а) — в) У к а з а н не. Получается фунхция веса 2. 8) а) Указание. Получается функция веса 3. б) Указание. Получается функция веса 4. 2.10.
Ц Вес равен 1. 2) а) Вес 2. 6) Вес 1. 3) а), в) Вес 1. 6) Вес 2. 4) а), 6) Вес 4. 5) а) Вес 2. 6) Вес 1. 6) а), в) Вес 1. 6) Вес 2. 7) а) Вес 4. 6), л) Вес 2. в), г) Вес 3. (В д) эквивалентны вершины в парах (00, ОЦ и (10, 1Ц.) 2.11. Ц а) Вес равен 4. 6) Вес 2. 2) а), 6) Вес 3. 3) а) Вес 1, 6), в) Вес 2.
4) а) — в) Вес 2. 2.12. Ц, 4) Вес равен 4. 2) Вес 2. 3) Вес 3. 5) Вес 7. 2.13. Ц Указание. Воспользоваться схемой для функции фг из примера 10, 6). 12) Указание. Вес функции равен 3. 15) Канонические уравнения и начальные условия для некоторого доопределения функции можно записать в следующем виде: у(1) = х(1) Чг(1 — Ц, Чг(Е) = х(1) %(1 — Ц Ч (1 — Ц, Чг(г) — х(1) 'Чг(1 Ц ' Чг(1 Ц (0) = (О) = О. 2.14. 3) у(1) = Чг(1 — Ц Ч,(1 — Ц, Чг(1) = (1), Чг(Ц = Чг(1 — Ц, Чг(0) = Чг(0) = 0; 7) уг(Х) = хз(1) ° Ч~ (Х вЂ” Ц у Чз(1 — Ц, уз(1) = хг (1) . Чз(1 — Ц Чг(1) = хг(1) Чг(1 — Ц М Чз(1 — Ц, Чг(Ц = хг(1), Чз(1) = ' з(1) Чг (0) = Чг(0) = Чз(0) = О. 23 Г.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
