Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1055357), страница 71
Текст из файла (страница 71)
Если х" входное слово длины в ) 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 Г. П. Гаврилов, А. А. Сапоженко 354 Ответы, указвннто ретленвв 2.15. Ц Реализуемая схемой о.-д.
функция может быть описана следующими каноническими уравнениями и начальным условием: у(1) = х(1) 4(1 — 1), 4(1) = (1), д(0) = О. Новая схема изображена на рис. 0.4.5, а. 2) у(1) = 2(е) у 4(1 — 1): г1(1) = 1 д(б) = О. Схема с выходом у(1) = х(1)у(1 — 1) приведена на рис. 0.4.5, б. 2.16. 2) а) Можно взять схему, изображенную на рис. 0.4.6, а. Она реализует функцию 1нв(х), порожденную тождественным путем. б) См., например, схему на рис.
0.4.6, б. Она реализует функцию угг(угг(... грг(х)... )). в) Пля*т = 1 и т = 4 соответствунлцие схемы приведены в задачах а) х (1) р раз р раз у(1) у(1) Рис. 0.4.6 Рис. 0.4.5 и б). Лля т = 2 подходит любая схема из задачи 2.15, а для т = 3 схемы из задачи 2.13 (см. 12), 14), 15)). 2.17. 1), 2) Единичная задержка строится из уг отождествлением поременных. 3) Получить из уг функцию уив(х), порожденную тождестненным путем, и подставить ее подходящим образом в уз. 4) Рассмотреть функции грг (х) = уз(х, х, х), багз(х) = ггг (тг(х)), грз(вг) = гз (грг (х) х грз (х)) и грг (х у) = г г (х у Згг (х)) 5) Рассмотреть функции фгг(х) = уз(х, х), згг(х, у) = уг(х у~ Фг(х)) и УЗЗ(х) = 12(х, УЗг(х)).
Гж Л'. Оераниченна-детперлинираеанньге функции 355 6) Единичная задержха и функция, порожденная стрелкой Пирса, стро- ятся так: угг(х) = зг(х, х, х), угг(х) = Ых, Згг(х)), Згз(х, у) = Ых, Рг(гу)): р4(х) = 74(х, х), угз(х) = гг(рг(х), уг4(х),х), фа(х) = Згг(рз(угг(х))). 7) Нужные функции получаются так: уч(х) = г)(х, х), фг(х) = = Узза( )) 8) Из функции 74 получить функцию 7" — 4(х), порожденную тождествен- ной единицей, и подходящим образом подставить ее в уг. 9) Из 1'4 получить функцию 1"ва(х) и подставить ее в уг.
10) Построив из уг функцию 7" — а(х) и подставляя ее в уг, получаем (на одном из выходов) функцию ув а(х). Затем надо рассмотреть функ- цию 6(Уиа(х), х). 11) Вводя обратную связь по переменным хз и уг в функции уг, полу- чаем функцию, порожденную конъюнкцией. Затем надо построить функ- цию уна(х) и рассмотреть супарпознциго уг(14(х), 74(х), )на(х)). 12) Подставляя в зг подходюцим образом функцию зг (х, х), получаем функцию уи4 (х). Задержку можно построить, вводя обратную связь в функ- ции уг по переменным хг и у . 13) Из гг построить уна(х).
Затем подставить ее в уг вместо перемен- ной хг. 14) Рассмотреть функцию <рг(х) = гг(х, х., х)., Згг(х) = 74(агг(х)) и угз(х, у) = Дх, у, х'). 15) Рассмотреть функции 14(х, 14(х, х)) и уг(хг, хг). 2.18. 1) Полагая хз = хг, получаем функцию, порожденную штрихом Шеффера. Затем построить функции уна(х), )нг(х), ут(х) и рассмотреть суперпозицию (Ци~ (х), уиг(х), зпа(х), зк(х)). 2) З'(хг, хг, хз) = зя, а —, (хы хг): значит, Ц)П г Циа(х), звг(х), Ук(х)). Палее, 1аг(х) = зя(1'(зи~(х), х, зиа(х))).
3) Если хг = хг, то У(хг,хм хз) = 1" †,з,к,(хг,хз). Строим уиа(х) и унг(х), затем задержку р,(х) = 1'(х, уиа(х), 1=4(х)). 4) Полагая хз = хг, получаем функцию зт, лт (хг, хг). Кроме того, р,(х) = 7(Уи,(х)., х, Уиа(х)). 5) Полагая хз = хг, получаем, что на одном выходе функции 7(хг, хг, хг) реализуатся функция 1 — „(хг), а на другом функция 1„, з (хм хг). Затем стРоим ун а(х), увг(х) и задеРжкУ Угз(х) = ук(7(ун1 (х), уиг(х), 7 — (х))) (по выходному каналу уг). 2.10. Ц Можно удалить )иа(х) (она получается из агг(х) с помощью операций объединения, отождествления входов и обратной связи; см. при- мер 10, д) в и.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
