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

Доказательство. Положим (г"' на Рт ~ (Х1а ° ° ° т Хда 714 . ° * т ту) (р Покажем, что 7 существенно не зависит от ху, ° ° .,х1, / т е е Пусть (Ду, ..., ~н, Ч1,..., Чу) и Ат ..., ~н, Чут . " Ч1)— два произвольных набора, которые совпадают для всех переменных, кроме, быть может,ху,,..., ху, Тогда в силу цилиндричности д' они оба одновременно либо не принадлежат множеству гу, либо оба содержатся в то.

В первом случае Р Жт..., ~'.т Ч,!..., Чу) = Р (114 . ", унт Ч1,..., Ч11 - О Во втором случае р(1! " ~ Чм ",Чу)-р'(11,...,144,Ч1,...,Чу)т р(~~ ° ° с Ч1 ° ° Чу) р (~ы ° ° ~.» Ч1 Ч1) Покалуем, что р'Ж ",1ат Ч1, °" Чу) -р'(1 " ~ Чу " Ч1) ° В самом деле, если это не так, то найдутся два набора (Ю„..., С.,Ч„...,Ч) ° (М",...,аГ, Ч„...,Ч) соседних по одной из переменных ху„...,х,, (нанример, х; ), для которых из условия ~, ~, следует ~ и гт р' (11 " 1 Ч1 ° ° Ч1) Ф р (11 .

° ° 1 Чы ° ° Ч1). Но тогда Рм невозможно доопределить до функции из Рам которая существенно бы не зависела от х;,, что противоречит тсходпому допущению. 4 Введение а днекуетную математику 98 ч. 1. Функциональные системы с ОпеРАцнямн Таким образом, Р существенно не зависит от х;,, ... х1, и теорема доказана. Перейдем теперь к определению операции О. Пусть ((1(хт ..., х„), ..., ) (х„..., х„)) (т>2)— система детерминированных функций и пусть )л зависит от переменной х, с за- Х1 паздыванием. Тогда, ху г рассматривая эту спсте- му как преобразователь ' с и входами и и выходами, мы можем Н-й выход соединить с си Рис. л4 входом (см. рис. 14)— ввести «обратную связьэ между выходом И и входом 1.

Мы получим преобразователь, реалиаующий систему из «1 — 1 детерминированных функций ( У 11 (х1, ..., х; „х;+„..., х,). Р ~л-1 (х1,..., х; 1, х1+11 ..., х„), / 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),О,а,'+1(1)1 ,с1„(1)) По этому набору вычисляем (л в момент времени 1, пусть это будет (1(1). Рассмотрим а(1)=(п1(1),..., и';-1(1), ул (1), а,'+1(1),... ...,а„(1)) и вычислим функции ~1, ° 11з-11 )а+1 ° ° 1)т по этому набору в момент времени 1.

2) Рассмотрим с1(2) (а1 (2),..., С1>-1 (2), уз (1), а„+1 (2), ..., а'„(2)]. По наборам а(1) и а(2) (т. е. в конечном счете по наборам а(1) и и(2) — см. и. 1)) вычлсляем 11 в момент времени 2 и получаем (1(2). Рассмотрим а(2)-(сс1(2),..., а;-1(2), ул(2), с11+,( )~ ' ° ...,а,,(2)) и по наборам а(1) и сс(2) вычисляем аначеиия функций ~» ° ° 1~з-11У1~11 ° ° „~ в момент 2 и т. д. тл.

а о.-д. этнкцпп с опктлцнями 99 Ф) Рассмотрим а(8) (а~(1), ..., а;-~(1), та(1 — 1), а>+,(г), ...,а„(г)]. По наборам и (1), а (2), ..., сс Щ вычисляем 1~ в момент времени т и получаем (, (г). Рассмотримй(~) = (и, (г), ..., а;, (г), у,~ (г), сс,+,(С), ..., а~(1)!, по наборам а (1), и (2), ..., а (Г) вмчисляем значения функций ~~ ° 6-м 6+м ° ° .,1е в момент и т. д. Если ~ь ..., ~ — о.-д.

функции, то операция 0 может быть определена через канонические уравнения, Пусть ~~ еависнт с запаадыеанием от переменной хь Возьмем систему канонических уравнений для 1„..., 1,.: з,(1) Г~(х~(О, ° ., х~Я,, х.(г), д, (1 — 1), ..., д~ (1 — 1) ), з,(г) Р,(х,(г), ..., —, ..., х.(8), Я (Ю вЂ” 1), ..., В(1 — 1)), в.(Г)=Р.(х,(г), ..., х,(г), ..., х„(ю), й,(1-1), ..., р,(г — 1)), д,(0) ... — д~(0) = О. Здесь прочерк в наборе аргументов у Р~ обовначает, что Рь существенно не аависит от х По этой системе канонических уравнений путем выбрасывания И-й строки и заменой переменной х, на Р~ строим новую систему $00 ч. 1. Фънкцконзльпые системы с ОпегАцпямн уравнений: зв($)=Рв(хв(Г), ..., Ра(х,И)', ...

..., —, ..., х. (г), о, (т- (), ° . „ав(1 — 1)), ..., Х„(1), Яв(г — т), ..., В)в(Ю вЂ” $))', за-в(1) Ра-в(хв(1), ..., Ра(хв(з), ... ..., —, ..., х„(г), о,(С вЂ” (), ... °, в)в(в — 1)), ..., х„(с), втв(ю — А), ..., дв(г — 1)), за+в(т) Га+в(хв(й), ..., Ра(х,(с), ..., —, ..., Х„(в), д,(à —.1), ... ° .'0(Г-())." х.(~) Ч Ь-()," й(Г-()), з„(1) Р„(хв(1), ... Ра(хв(~) ..., —, ..., Х„(1), ~в(à — т), ...

, чв(Ю вЂ” 1)), ..., хв(в), дв(à — Ц, ..., Ов(й — ()), д,(Г)-С,(х,(т), ..., Р,(х,р), ... ..., —, ..., х„(в), д,(в — 4), „, ..., Д (в — 1) ), ..., Х (1), ва,(1 — т), ..., ~,(т — 1) ), Яв(а) бв(хв(й)в ...в Ра(хв(вв)в .., ' ° 'в в ° ° 'в Ха(в) Дв(В А)в ° ° ° , ч,(т — 1)), ..., х.(ю), д,(г - 1), ..., О,(т — ()), ,(0)-...'-,,(0) О'. Эта система уравнений, очевидно, определяет те же о.-д. фунвнни 11 ° ° ° Й вЂ” 1в Й+вв ° ° ° в 1ва Которма бЫЛВ Ояродо- лены выше.

Отсюда следует также, что система о.-д. функ-, ций, получаемая таким образом, не зависит от выбора канонических уравнений для ~„ ..., ~ (при условии, что Ра существенно не зависит от х,). Приведем пример, показывающий, каким образок вы- глядит применение операции О в данном случае. В каче- стве исходной системы о.-д. функцвй возьмем систему, гл. з. о,-д. ж нкции с опвглцнями СОС задаваемую каноническими уравпеннями г(С)= х(С)+ у(С)+ д(С вЂ” 1) (шоб 2)', ш(С) = х(С) у(С) 7 х(С) д(С вЂ” 1) Ч у(С) д(С вЂ” 1), д(С)=и(С), д(0)=0. Как было отмечено выше, обе функции г и ш зависят от переменной и с запаздыванием. Посредством тожде- ства и(С)= ш(С) введем обратную связь. После исключения получим сле- дующие канонические уравнения: г(С) х(С)+ у(С)+ д(С- 1), д(С) хЧ(С) уЪ(С) Ч х(С)д(С вЂ” 1)Ч у(С)д(С вЂ” 1)', д(0) О.

Таким образом, результатом операции О является о:д. функция, представляющая сложение двух последователь- ностей. Теорема б. Класс о.-д. функций замкнут относи- тельно онерации О. Введение операции обратной связи можно более ком- пактно охарактеризовать в терминах подстановок функ- ций т"„ ..., Г из Р» входящих в кацонические урав- нения. Рассмотрим случай, когда операция О применяется дважды, и для простоты будем считать, что она применя- ется к парам (г„х,) и (г» х,) ((сС>, ),) (1, 1) и (сС» Сз) (2, 2)) (что легко ДостигаетсЯ пеРенУмеРаЦией функций и переменных). В основе канонических урав- нений лежат уравнения г, р>(х„х» ..., х„, д„..., д,), г> Г>(х> х2», .

х д>,, д>) з т' (х„х»...,х„,д»...,д), которые, положив й (х» ..., х„, д» ..., д>), кратко запишем г, т",(х„х» й)', г,=р,(х„х» й), СОЗ ч. ь фтнкционлльнык систвмы с опктгцкями Так как по условию применима обратная связь (г„х,)', то Р, =Р,(-, х„й)', т. е. Р, существенно не аависит от х,. При помощи подстановки х, Р,( —, х,, й) мы получим систему уравнений гг = Рз(Р,( —, хо й), х,, Й) По условию возможно введенпе обратной связи (го х,).

Это озпачает, что Р,(Р,(-, х„ й), хм в) существенно не зависит от хь Таким образом, введению обратной связи в последовательности (го х,), (гь х~) соответствует исключение переменныл х, и х, в исходной системе при помощи подстановок х, Р,(-, Р,(Р,(-, хи б), хи о), 6), х, Р,(Р,(-, х,, й), х„й'), причем правые части не зависят существенно от хь П р и м е р 7.

1'ассмотркм систему из трех о.-д. функций г!(С) хг(С)хэ(С)Ч д(С 1)у г,(С) = х,(С)х,(С) Чх,(С) Ч д(С вЂ” 1), г,(С) Р,(х,(С), х,(С)', х,(С), д(С вЂ” 1)), я(С)'= 6(х!(С)в хг(С)э ха(С), я (С 1))~ д (0) О. Здесь можно применить операцию О к (го х~): Р,(Р, (-, х„х„о)', хм х„о) (х,х. Ч д) х, Ч х. Ч с х; Ч д. Полученная функция существенно не зависит от х,. По- этому мы можем далее ввести обратную связь (гг, хг).

Введению обратной связи в последовательности (г„ х,), (гг, хг) соответствует пара подстановок х, =х,Чд, х, = х, Ч о. ГЛ. 3. О..Д. ФУНКЦИИ С ОПЕРАЦИЯМИ 103 С другой стороны, невозможно осуществить введение обратной связи в порядке (ги х,), (г„х,), потому что Г,(хи хи хи д) существенно зависит от переменной х,. Данный пример выявляет некоторые негативные стороны введенной нами операции О. Следующая теорема показывает, что для широкого класса ситуаций порядок введения обратных связей безразличен. Т е о р е и а 7. Пусть для системы о.-д. функций ((и (и ..., г ), где т~ 3, возможно введение обратных связей и в порядке (г„х,), (ги х,), и в порядке (ги х>), (г„х,).