Гаврилов Г.П., Сапоженко А.А. - Задачи и упражнения по дискретной математике (1048833), страница 30
Текст из файла (страница 30)
х(е) при Ь > 2; 1 при 1=1, 2, хЯ -в х(2) при 1 > 3; 4 д 1 ~ ~ ~ ~ ~ ~ ~ ~~ ~ ~ | | ~~ !~ х(1) при С = 1, 5) д(г) = х(1 — 1) ~3 х(1) при 1 > 2; (х(1) при 1 = 1, 2, 6) д(Ц = ~х(1 — 1) при 1 > 3; х(2), если 1= 2, 7) дФ= 1 в остальных случаях: (х(1) -+ х(1), если 1 = 1, 2, 3, 8)дф= ~ О в ином случае; х(1) при 1 = 1, О)дФ= д(1 — 1) ч' х(е) при 1 > 2; < х(1), если 1= 1, 2, 1О) д(1) = д(1 — 2) Юд(1 — Ц, если 1> 3; ~ 11)д®= ' * О, если 1=1 и 1=3, х(1), если 1 = 2 или 1 > 4; 12) дф = х(1) при 1 = 1, д11 — 1). х(1) при 1 > 2: á 13) д(1) = 1 при 1=1, х(1 — 1) Ч х(1) при 1 > 2; 14) д(1) = х(1) при Х = 1, д(1 — 1) Ю х(1) при 1 > 2; á у" 2.
Лиаграммьь хаайяииьь нанвнинееиие уравнения, схемы 139 ( х(х), если 1 нечетное, 15) у[1) = [ О, если 1 четное; т(х), если 1 нечетное, 10) у[1) = у[1 — 1) Юх(1), если 1 четное: х[х), если 1 нечетное 17) у(1) = < х(1) — > у(1 — 1), если 1 четное; 18) 1(ты) = Ох(2) [1]; 19) ~(х~) = т(1) х(2) [0]~; 20) Х[т5ы) = Ох(1) [01]'; 21) ~[ты) = [х(1) О]"'; 0"', если хы = 0', 22) Х[т' ) = 0' [1]'", если х ' = 0'1х(1+ 2) т(1-р 3)...
и 1 > 1 1"', если х = 1т(2) х[3)...; если хы = 0 ' или х' = 1', 23) х (х") = 1' [0]~,. если х~ = О'1х(1+ 2) х(1+ 3)... или т~ = 1'От[1+ 2) х[1+3)..., где 1 > 1; 24) у(1) есть 1-я цифра после запятой в двоичном разложении числа 5/7; 25) у[1) есть (1+ 1)-я цифра после запятой в двоичном разложении числа 1/9; 26) уф есть (1+ 2)-я цифра после запятой в двоичном разложении числа 11/15; 27) у(1) есть [х+ 1)-я цифра после запятой в двоичном разложении числа х[1)/5; 28) у[1) есть [1+ 2)-я цифра после запятой в двоичном разложении числа Зх[1) /7; 29) у(1) есть |-я цифра после запятой в двоичном разложении чис- ла (х[1) + 1)/3; е ~ ~ ~ ~ ~ ~ ~ ~ ~ ~~ ~ ~ ~ ~ ~ ~ ~ ! ~ ~ ~ ~ ~~ | т(1) при 1 = 1, 30) у(1) = х[1) х(2) при 1 = 2, [у(1 — 2) ах[1)) х(1 — 1) при 1 > 3; т(1) при 1 = 1, 31) у(1) = х[1) + х[2) при 1 = 2, х(1 — 2) Е х[1 — 1) Е т[1) при 1 > 3; 140 Го. 17.
Ограниченно-детерминированные функции 32) уф = х(Ц при 1=1, х(2) — > х(Ц при 1 = 2, х® — + (х(1 — Ц вЂ” > х(1 — 2)) при 1 > 3; О, если 1=1, 33) усг) = х(1 — Ц вЂ” ~ х®, если 1 четное, хф в ином случае; 34) уф = х(Ц, если 1 = 1, х(1 — Ц, если 1 > 3 и нечетное, у(» — Ц в ином случае; О, если 1=3з — 2 и в>1, 35)уф= 1, если 1=3з — 1 и в>1, х(1) в ином случае; 1, если 1=3з — 2 и в>1, 36)у®= х(1 — Ц, если 1=3з — 1 и з>1, у(1 — Ц -О х(1) в ином случае; О, если 1= 1, 37) уф = х1г), если 1= Зз — 2 и в > 2, х(1 — Ц у(е — Ц в ином случае; 1„если 1=4з+1 и в>0, хф, если 1 = 4з + 2 и в > О, 38) у(1) = хф, если 1 = 4в+ 3 и з > О, 0 в ином случае,: хф, если 1=4в+1 и в>0, х(1 — Ц, если 1 = 4в + 2 и з > О, ЯС вЂ” Ц, если С=4з-~-3 и з>0, у(1 — Ц.
хф в ином случае; ЗО) у~1) = О, если 1=4з+1 и в>0, х(1 — Цйхф, если 1=4в-~-2 и з>0, у(1 — ЦОвхЯ, если 1=4з+3 и в>0, х(1 — Ц 6Э у(1 — Ц в ином случае. 40) уф = 2.2. Для каждой из диаграмм построить приведенную диаграмму: Ц рис. 4.31,а; 2) рис. 4.31,б; 3) рис.
4.31,в; 4) рис. 4.31,г; 142 Га. 17. Ограниченно-детерминированные функции 0(0) 0 Цо) 2 Цо) Ц1) 0(Ц 0 0(1) 4 г 0(1) е 1 0(0) 2 0(1) Рис. 4.32 4) рис. 4.32, г; т = 2; 5) рис. 4.32, д; т = 3; 6) рис. 4.32, е; т = 3; 7) рис. 4.32, ж; т = 4; 8) рис. 4.32,з, т = 4. 2А.
Найти вес о.-д. функции 7' из Рз ', заданной каноническими ц1 уравнениями: У(1) т(1) — > Ч1(1 — 1) Чг(1 — 1), Ч1(1) = Ч1(1 — 1) т Ч2(1 — Ц, Ч2(1) Ч2(1 1) + Ч1(1 1)п Ч,(0) = Ч,(0) = 1; у(1) = и(1) ео Ч1(1 — 1), Ч1(1) — х(1)' Чз(1 1) Ч2 (в) — Чз (1 1); Ч,(0) = 1, Ч,(О) = 0; У(1) = Ч,(1 — 1), Ч (~) — Ч (~ — 1) Ч (1 — ) Ч2(1) к(1), Ч,(0) = 0, Ч,(О) = 1; У(1) = х(1) и' Ч1(1 — 1), Чз(1) =х(1) ЕЧ,(1 — 1), Ч,(1) =*(1) Ч,(1 — 1).Ч,« — 1),. Ч,(0) = Ч,(0) = 0; у" е.
Лиаграммвь таабаиивь канонические уравнения, схемы 143 у(») = Ч1(» Ц + Ч2(» Ц; Ч2(») = Ч2(» — Ц; Ч2(») — и(») ~ Чз (» Ц1 Ч,(0) = 1, Ч,(О) = О; 5) У: у(») = х(») 9 Ч1(» Ц Ю Ч2(» Ц Ч1(») = Ч2(» — Ц вЂ” ~ Ч»(» Ц, Ч (») = Ч1(» — Ц -в (») Ч„(О) = Ч,(О) = О; У(») = хт(») Ч,(» — Ц.Ч2(» — Ц фЧ»(» — Ц Чз(» — Ц, Ч,(») =2;(»)»Ч,(» — Ц Ч,(» — Ц, Ч2(») 2 (») Ч2(» Ц Ч,(О) = О, Ч,(О) = 1; у(») = х(»). Чх(» — Ц 'я' Чя(» — Ц, ) ( Ч~(») — Ч (» Ц () Чз(») х(») + Ч2(» «) Ч1(0) = Ч2(0) = 1 у(») = х(») Чз(» — Ц ч х(»)' Ч2(» Ц Ч2(») = х(») Чх(» — Ц Н х(») . Чз(» — Ц, Ч2(») х(»)' (Ч1(» Ц ' Ч2(» Ц)' „ (О) = 1, Ч,(О) = О; у(») = Чз (» — Ц .
Ч2(» — Ц -2 х(») 10) ». Ч2(») = Ч2(» Ц ф Ч1(» Ц Ч,(О) = Чя(О) = 1. 2.5. Для частично определенной д. функции »"(х '): (О., 1)" -+ — » (О, 1)"', отображающей заданные последовательности в заданные, построить диаграмму Мура с возможно меныпим числом вершин; затем полученную диаграмму доопределить до диаграммы Мура всюду определенной о.-д. функции из Р ',, и для этой новой функции Д2 построить каноническую таблицу и каноничоские уравнения: Ц ДОы) = [ОЦ и 1([10]") = 1': 2) ЯОЦ ) = 0" и Д«[10)' ) = [ООЦ 3) Я«ОЦ ) = [110) и 1([010]ы) = [101Ц 4) «'(1[110]") = 10[ООЦы и «'(01[100] ) = [10Ц 5) »(01[10) ) = [100) и ДО«1[110)ы) = 100[ОЦ 6) Я««ОЦ ) = [01Ц и ~(1100 [Ц' ) = [ОПЦ"; 7) »(111[100] ) = 00[ООЦ и Д«[1100]") = 000 [Ц"'; 8) 7"([11000] ) = [010] и 1(1100 [Ц ) = 01[0) '.
144 Гл. 1'г'. Ограниченно-дегаерминирооанные функции 2.6. Подсчитать число различных о.-д. функций из Рг',, у ко- !,! торых приведенная диаграмма Мура получается из указанного ориентированного графа путем приписывания его дугам подходящих меток вида а(Ь), где а и Ь принадлежат множеству 10, 1) (звездочкой обозначается начальное состояние): 1) рис. 4.33,а; 2) рис.
4.33,б; 3) рис. 4.33,а; 4) рис. 4.33,г; 5) рис. 4.33, д; 6) рис. 4.33, е; 7) рис. 4.33, ле, 8) рис. 4.33, з; 9) рис. 4.33, ж 10) рис. 4.33, к; 11) рис. 4.33, л; 12) рис. 4.33, и. О а б в 0 Рис. 4.33 2.7. Ц Локазатгч что приведенные диаграммы Мура различных !л о.-ц. функций веса 2 из Рг'а исчерпываются диаграммами, получающимися из ориентированных графов, изображенных на рис. 4.34, г д Рис.
4.34 у" 2. Лиаараммыс споблицы, канонические уравнения, схемы 145 путем приписывания их вершинам меток О и 1, приписывания их ребрам меток вида а(Ь), где а и Ь принадлежат множеству (О, 1), и выделения подходящих вершин в качестве «начальных» (т.е. в качестве вершин, соответствующих начальным состояниям).
1.1 2) Поде~~~а~~ спело различных о.-д. функций из Рг',„, имесощих вес 2. 2. Операции иад детерминированными функцинми. Пусть д, функция г" задана системой (2) (см. и. 1) и каждая из функций Рс и Сс всюду определенная функция Ь-злачной логики Рс (Ь > 2).
Будем рассматривать функцию 1 как элемент множества Р„' . Схема Ху, реализуюиСом функцию (, определяется следующим образом: Еу представляет собой сеть (определение сети см. в гл. У1), полюсам которой приписаны символы входных и выходных переменныхв а некоторым вершинам, отличным от полюсов, приписаны символы каких-то (вполне определенных и связанных с 1) д. функций (из множества ( ) Р" з). Схему функции у из Рп'ы будем изображать в>1 С>1 Ус уг Х1 хг у 1'нс. 4.35 в виде прямоугольника (рис.
4.35) с и входами (входными каналами) и сп восходами (выходными каналами). Входы изображаются в виде стрелок, исходящих из входных полюсов, а выходы в виде стрелок, заходящих в выходные полюса. Полюса изображаются в виде кружочков. Если т = 1, то схему Бу, реализующую функцию у, иногда изображают в виде треугольника (рис. 4.36) с п входными и одним выходным полюсами. Считаем,чтовкаждыймомент времени 1 = 1, 2, ... наг-йвходх, поступает входной символ х,(1) б Ес, а на у-м выходе у.
выдается значение ус(Г) =Рг(хс(1) " х (1) 41(1 — 1) " Ч.(1 — 1)) Говорят,что выход у зависит с запаздываниям от входах„ если функция Рг (хрб(1), Чс" с(1 — 1)) не зависит существенно от переменной х;(1). Понятие зависимости с запаздыванием можно ввести иначе. Рассмотрим, например, случай д. функции вида Д(х"'',х"', ..., х„): А, х Аг' х ...
х А„— с В и определим зависимость с запаздыванием от переменной хс . Функция с" зависит с запаздыванием от х', если при любых входных словах а, а', ... „а„' (а б А", у = 1, 2, ..., и) в-я буква выходного слова Ь = 1(Б"', а, ..., а„) однозначно определяется в первыми символами слов а'", ..., а„"' и в — 1 первыми символами слова аг" (в = 1, 2, ...).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
