Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132709), страница 72
Текст из файла (страница 72)
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, и все они соответствуют д1 различным о.-д. функциям из Р, *„.
5) 512 различных диаграмм, 480 приведенных (они соответствуют раз- ным о.-д, функциям веса 3 из Р, *, ). гл 6) 256 различных диаграмм, 240 приведенных (все они соответствуют разным о.-д. функциям нз Рз ' „). н1 7), 8) 512 различных диаграмм, 432 приведенных (все они соответству- ют разным о.-д. функциям веса 3 из Рз '„).
дз 9) 512 различных диаграмм, приведенных 336. Число разных о.-д. функд1 ций из Р, '„, задаваемых этими приведенными диаграммами, равно 168. 10) 64 различные диаграммы, привеценнвзх 60, и все они соответствуют разным о.-д. функциям веса 3 из Р ' цз 1Ц 4096 (= 2'з) различных диаграмм; приведенных 4032 (они задают попарно различные о.-д. функции веса 4 из Р, ', ). нз 12) 512 различных диаграмм, приведенных 504 (они соответствуют разным о.-д.
функциям веса 4 из Рз '„„). 63 2.7. 2) 144 о.-д. функции. 2.8. Ц дЯ = дЦ1 — Ц их®дз14 — Ц, д1(1) = хЯ дзИ вЂ” Ц, дзф = таз)дз(е Ц, дцб) = 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 Ц ' Чг(1 Ц (0) = (О) = О. 2.14. 3) у(1) = Чг(1 — Ц Ч,(1 — Ц, Чг(1) = (1), Чг(Ц = Чг(1 — Ц, Чг(0) = Чг(0) = 0; 7) уг(Х) = хз(1) ° Ч~ (Х вЂ” Ц у Чз(1 — Ц, уз(1) = хг (1) . Чз(4 — Ц Чг(1) = хг(1) Чг(1 — Ц М Чз(1 — Ц, Чг(Ц = хг(1), Чз(1) = ' з(1) Чг (0) = Чг(0) = Чз(0) = О.
23 Г. П. Гаврилов, А. А. Сапоженко 354 Ответы, указвннто ретленвв 2.15. Ц Реализуемая схемой о.-д. функция может быть описана следующими каноническими уравнениями и начальным условием: у(1) = х(1) у(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, д) в и. 3). 2) Можно удалить два первые функции, так как г -4я(х., х) = уиг(х), згг(гт(ги 4(х))) = ун а(х), я(х, 4=а(х)) = г — (х), г я(х, у) = г„л„(З а(х, у), гз-, (х, у)) и у„из(х, у) = 1 — (у,,я(х, уу(у))). 3) Можно удалить две первые функции, так как: а) уг(~, я(х, х) = угз(х); б) из уй с помощью опералнй объединения, отождествления входов и обратной связи строится 1' — а(х); в) ) нз(ггиа(х), У) = ггУ(У): г) гг з,я(х, У) = ~к(У,,нк(гг — (х), УЦ; д) ~„ъя(х, у) = 1 — (1„, а,г (1 ау(х, у), 1таз(х, у)).
356 Ответы, указания, решеннв 4) Можно удалить )к(х), ибо 1 чЯеег;(уна1х)) гу (У)) = уу(У). 5) Можно удалить первую и третью функцию, так как: а) с помощью операций объединения, отождествления входов и обратной связи из последней функции системы А получается функция упг(х); б) из 1",.у У(х, У) и 1" — е (х) можно пОстРоить всЯкУю поРожденнУю фУнкцию из Рг. в; в) уг1х) = )т11к(уг 11 — (У вЂ” (х))))). 2.20. 1) Содержится, ибо Згг(х) = ЗггЦ~к(ут(х))) и увв(х) есть в Еэг,(х))ео, о, о,1. 2) Содержится. 3) Содержится, ибо у,,в(х, унв(х)) = ут (х), а уле(х) есть в ~Фг(х))<оь о„оП 4) Содержится.
Указание. Вводя обратную связь во второй и третьей функциях, получаем уг(х) = )01) и бг(х) = )10) . Затем надо воспользоваться г'гчг(х У). 5) а) Не содержится. Указание. Установить, что каждая функция из А «сохраняет» множество последовательностей е' = 1о" = огог... ое... ~ Ззе (ге ((1 > ев) ~ ~ (о = О)))Ч ЗП ГУ1 ((1 > 1 ) ~ <о = 1)))). б) Содержится. У к а з а н и е. Рассмотреть функцию, получающуюся из функции угг(уг,(ут (х))) введением обратной связи.
2.21. 1) Добавить 1',„Е „0(х, у, г). 2) Добавить з"„(х, у). 3) Добавляя только одну функцию из В, систему до полной расширить нельзя. Указание. Замкнутые классы, получающиеся при этом, состоят из функций, сохраняющих множество последовательностей 1е, описанное в ответе к задаче 2.20, 5), а). Значит, в них не содержится, например, функция 1(х) = )01)"'. При обосновании свойства сохранения множества Ъ' в случае рассмотрения операции обратной связи удобно использовать представление о.-д.
функции ек которой применяется операция обратной связи) в виде канонических уравнений. 4) Добавить |, к1х, Згг(гу)). 5) Добавить 1" —,(1гг(гу)). Глава У 1.1. 1) а) Т(Р) = 1 . 6) Т(Р) = 1. в) К слову 1в не применима. 2) а) Т(Р) = 1з01. 6), в) Т(Р) = 1г. 3) а) ТЕР) = 10 1г01'. 6) Т(Р) = 10 1з.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
