С.В. Яблонский - Введение в дискретную математику, страница 15

о,(0)=0. Для ограниченно-детерминированных функций, описанных в примерах 3, а) и 3, б), канонические уравнения «) Множество Ю с= Е«к ... х Е«нааываетсв зели»драч«елим »«[ ве вервым воордиматам л„.. » в» тогда и только тогда, когда любые два набора (ь„..., ь„, Ч, ..., Ч~) и (~,', ... ь„, Ч„...,Чй либо одновременно принадлежат д', либо одновременно не принадлежат й.

Очевидно, что область определенна Е фуниппй Г',6, ..., 6~~ является цилиндрическим множеством ло ль ..., а». 90 ч. ь Функциональные системы с ОпеРАциями имеют, соответственно, следующий вид: з(г)- х,(1) б:х,(~); з(Ю) х(1)+р(й)+д(à — 1) (ипоб2), д(1) х (1) у (8) Ч х Я д (г — 1) Ч у Я д (г — 1), д(о)-о. Пример 4. Пусть о.-д. функция 1(х) задана диаграммой Мура, приведенной на рис. 11. Для нее функции У' и У приведены в табл. 1. Закодировав состояния О, 1, 2 Рис. Ы наборами (О, 0), (О, 1) и (1, 0), мы получим функции г"', б„бз (см.

табл. 2). Табл ппа 2 Таблппа 3 Доопределив функции г', 6„6„например так, как вто сделано в табл. 3, мы получим функции г', С, и би Имея теперь функции Е, Сп С„получим канонические гл. 3. О.-д. Функции с опеузцпяыи уравнения з(Ю)=х(М) &д,(С вЂ” 1)Чх(Ц&д,(1 — 1), у, (г) = у, (г — 1) Ч х (г) &д, (г — 1), 9в(Ф)= Дз(1 — 1)ЧУ(С) &д,(à — 1), д,(0) = д,(о) = о.

Заметим, что в случае, когда г 1, переменные д в канонических уравнениях отсутствуют. Таким образом каждой о.-д. функции можно сопоставить ианонические уравнения. Однако выбор канонических уравнений не однозначен. Эта неоднозначность свявана: а) с различными способами кодирования (нумерации) состояний; б) с различными способами доопределения функций Р,б» ° ° ° ~ 6с Легко видеть, что канонические уравнения позволяют вычислить по входной последовательности а = (а(1), а(2), ) выходную последовательность т = (т(1), т(2), ...).

Часто рассматривают произвольные системы (») (у которых 1 может быть и больше )1оу„г1') для задания о.-д. функции. В частности, может оказаться, что если для о.-д. функции т, определяемой этими уравнениями, взять любые канонические уравнения, то они не будут совпадать с исходными уравнениями. $4. Операция над о.-д. функциями При определении операций над о.-д.

функциями удобно исходить из классов Рьз и Рз,А В Рьа,так же, как и в Р, вводится операция супер- позиции: сначала определяется понятие формулы над системой функций из Рью а затем каждой формуле сопоставляетси функция нз Рьь. Легко видеть, что справедлива Теорема 3. Класс детерминированных (рункци6 замкнут относительно операции суперпозиции. 93 ч.

г, Функцнонлльные системы с Опеглцпями х' 1(Х)-1,(1,(Х'), ..., 1.(Х.)), является о.-д. функцией. Поскольку, как и прежде, функция рассматривается с точностью до несущественных переменных (а при добавлении и изъятии несущественных переменных о.-д. функция переходит в о.-д. функцию с тем же весом), то можно считать, что функции )о ..., т зависят от одних и тех же переменных х„..., к, т. е. Пк!, "., к.)-1.(И „..., Е.), ..., 1,.(х!, .", к.))'.

Выпишем канонические уравнения для 1., )о ..., 1„! е,(Ю) — Рз(у,(1), ..., у (1), д",(1 — 1), ..., д!,(1 — 1)), д, (1) С",(у, (1), ..., у (С), д,"(! — 1) ° ° ° д!з (1 — 1)) д! (Ц - а! (у, (1), ..., у„, (!), д",(1 — Ц, ..., д!„(г — 1)), д',(о)= ... =д,",(о)-о; Суперпозицию детерминированных функций удобно изображать графически в виде блок-схемы. Если система содержит тождественную функцию, то суперпозиция сводится к многократному применению элементарных супер- позиций вида )(Х) =(,(УХ ), ..., 1.(Х.)). Поэтому достаточно указать, как выглядит блок-схема для элементарной суперпозиции (см.

рис. 12). На блоксхеме квадратиками изобральены преобразователи, которые х ть ! реализуют функцию, написан- ную внутри квадрата. ! Теорема 4. Класс о.-д. ! ! функций замкнут относительно ! суперпозиции. х' тз ! Доказательство. Так как класс о.-д. функций содержит тождественную функцп!о, то для доказательства теоремы достаточно установпть, что функция 1(Х), получаемая пз о.-д. функций 1„1„..., 1 по формуле РЛ.

3. О.-Д. ФУНКЦИП С ОПЕРАП!!ЯМИ (1)»' (х (!),, х (!) д (! 1), . д! (! 1)) д',(1) 6, '(х, (Е), ..., х (!), Д! (! — Ц, ..., Д1, (! — 1)), Д,' (1) б!! (х,(а),..., х„Я! д»(1 — 1),..., д,', (С вЂ” 1)), „'(о) - ... - д',, (о) — о; (!) 1! (х ~, ..., х„(к), д" (1 — Ц, ..., д~„(1 — 1)), Й (К) 6,(х,(С), ..., х„(С), д» (1 — 1), ..., Д1„,(1 — 1))» д",„(Ю) - ~! (х, (Ю), ..., х (1), д" (1 — 1), ", д! (1 — 1)) дт(о) „, д, (о) о. (Предиолагается, что символы д! для разных пар (1, !) различны.) Покажем, что 1 можно задать также при помощи канонических уравнений. В самом деле, положим О О 1 ! О» О» ! (х1! ° ° ! хп! д!! ° ° ! д!О! д!! ° ° ° ! д!1~ ° ° ° ~д! ю ° ! д!О») ! !) '~О (»Р1 (»Х1~ ' ! Х!» Д» ° ! Д!!/в О» (Х!» ' '! ХО! Д! ~ ' '> Д!»О/ Д» ' '! Д»О/! О О ! ! О» О» ! о (х» ° ° ! хО~ Д!» ! Д!О~ Д» ° ° ~ Й ~ ° ° ° »Д1 ! ~ Д!О») ~ » (~о~~~ Й ) ° ° »с»О(х1! ° ° »х»! Й ! ° ° ° ю Д!О») Й ° ° ! ЙО) (1-О, 1<1~1,), б,'~хм ...!х„,д1!»,»д~!) (1>0, 1~(~»;1»).

д4 ч. г. фтнкцпонлльнык систнмы с опввлцнямн Тогда уравнения г (С) = Р (х, (Г), ..., х„(С),д", (à — 1), ..., д7, (С вЂ” 1), .:. ...,д",(с — ц, ...,д™. (с — 1)), д)(г) = ~о (х (г), " , *, (с), д~(с — 1), " , д7„ (с — 1), ... ...,д", (с — 1)„ ...д,„(с — 1)), д5(о) - о, 0<с~т, 1~)<7ь аадают, очевидно, функцию г.

Теорема доказана. В Р,, определим операцию О, называемую операцией введения обратной связи. О п р е д е л е н и е. Детерминированная функция Дхо ..., х, ..., х„) зависит от переменной хс с запаздыванием, если для любых входных последовательностей сс, =(сс,(1), сс,(2), ..., а,(С), ), сс„=(сс„(1), а„(2), ..., сс„(с), ) и любого момента времени с значение ((г), где т - У(ссо ..., а.), полностью определяется значениями первых с членов последовательностей ио ° °, сс<-о исзо ..., се~ н значениями первых с — 1 членов последовательности се~ (следовательно, ((Г) не зависит от сс,(С) ).

Пример 5. Рассмотрим функцию г'(х) из Р,,м для которой д(г)= сс(с — 1) и д(1) О, т. е. г'(х) осуществляет сдвиг входной последовательности на один разряд. В дальнейшем мы зту функцию обозначим через х. На рис. 13 представлено дерево для х. Из рисунка видно, что х— о.-д. функция с весом 2 и имеет следующие канонические уравнения: (г) = д(с -1) д(с) = (с) д(о)-о.

гл. а о.-д. фтнкции с опквлцггями 95 Легко видеть, что функция х зависит от х с запаздыванием. Пусть ~(х„ ..., х.) зависит с аапаздывавием от переггенных х;,,...,хг,, тогда, очевидно, для любых входных последовательностей а, = (а,(1), а,(2), ..., аг(г), . ), а = (а„(1), а„(2), ..., а„(г), ) и любого момента г значение ((г), где '(=1(а„..., а.), полностью определяется значениями первых 1 членов последовательностей а,,...,а,, „а;,+„...,аг, „а;,+„' ...,а„ и значениями первых г — 1 членов последовательностей гг1 '''' га (значит, 1(8) не зависит от сг;, (г),..., аг, (г)). л г г гг В случае, когда ((хь ... х„) ги Р„м можно дать л л 1 определение зависимости от перемеиной хг (1 < г < гг) гг гг с запаздыванием на языке каионическил уравнении: Йхг, ..., х„) зависит от х, (1 ~ г < и) с запаздываки- Рвс.

гЗ ем тогда и только тогда, когда 1 можно задать каноническими уравнениями г(ю) =Р(х,(г), ..., х.(г), д,(г — 1), ..., д,(г — 1)), д,(г) = С,(х,(Г), ..., х,.(г), д (г — 1), ", д (1-1) ), ("). %(м)=С,(ха(г), ..., х„(г), дз(с — 1), ..., д~(е — 1)), д,(о)=...-д,(о)=о, в которых фувкция Р(х„..., х„, д,, ..., д~) как функция из Рг существенно не зависит от хь ве ч. 1. етнкциональные системы с ОпеРАцпяыи В примере 5 видно, что Р(х, с) д, т.

е. Р не аавнсит существенно от х, что согласуется со вторым определением зависимости от переменной с запаздыванием. Пусть теперь о.-д. функция 1(х„..., х.) зависит с аапаадыванием от переменных Х1! !х1 ° Тогда ид (») для каждого х1 (т 1, ..., а) можно найти канонические уравнения, описывающие 1, вида з(г) Р,(х,(1), ...,х1„-,(1),х1„+,(1).

° ° ° ха (Г) т1(à — 1),..., ч1(1 — 1))~ д,(г)-б,(х,(г), ...,Х„(г),о,(г — 1), ...,д,(г — 1)), о1(Г) 61(хг(Г),...,Х„($), дг(à — 1), ...,д1(à — 1)), ,,(о)-...-д,(о)-о, где Р„ получается путем доопределения из некоторой функции Р', Р.1и Р~ и существенно не аависнт ог Х1„. Таким образом, иэ Р' мы получаем, вообще говоря, рааличные доопределения Р„..., Р.. Возникает вопрос, можно ли подобрать доопределения так, чтобы Р, ~... ~ю Р, ав Р? (Другими словами — найти такое доопределение Р, которое бы существенно не зависело от Х1 Ф 1х1 ) Если Р' — произвольная не всюду определенная функция из Р„, то гарантировать этого нельзя, в чем можно убедиться на следующем примере.

Пр.имер 6, Пусть Р'(х„х,) определена на множестве Р, где 8'= ((О, О), (1, 1)) и Ю~Е1ХЕ~ (см. табл. 4). Очевидно~ что Р~ (хо ха) ие х~ и Рз(хо хз) ~ю хв яВляют ся доопределениями Р, причем Р, существенно не зависит от х„а Р,— от х,. В то же время не существует доопределения Р', которое бы существенно не аависело одновременно от х, и хь Однако при некоторых ограничениях, которые в на- шем случае выполнены, поставленный вопрос допускает положительное решение. гл.

а о.-д. етнкции с опкглциями 97 Теорема 5. Пусть Р'(х„.. и хн, ои ..;, д,) — удункция из Р„определенная на множестве ет, являющемся цилиндрическим по х„..., х„, и Р' допускает доопредегения Р„..., Р, такие, что Рт существенно не зависит от ху,, Р; существенно не зависит от ху, и т. д., наконец, Г, существенно не зависит от х4,. Тогда существует такое доопределение Р, которое существенно не зависит от ПЕРЕМЕННЫХ Х»,..., Х1,.