Введение в дискретную математику - Яблонский С.В.
Скачать (прямая ссылка):
І /і (^1) ‘ ) 3- }-1, X}- 1 , . ? • , X,;), ...
* * • і }о—1 (^і: ? • • , Х}~ її Хн),
/а+і О^'Т» * * *1 і, і ... іЖ„), ...
1 ' * ї ? . *, Х^—і, ^ —|— А у * • < , ХГІ) і,
зависящих от п — 1 переменных хи .. .5 х^и хН1, ..., хп.
Функции /і, ..., /а—і, /а-м* • • • > /т формально определяются так: пусть а — входная последовательность для Хі, .. Х}_і, хш, ..., хп.
1) Рассмотрим сх (1) = {сії (1), ..., аН1 (1), 0, а'-+1 (1),.. .
. .., а,і (1))- По этому пабору вычисляем /гі в момент времени 1, пусть это будет 'Іа(І).
Рассмотрим а(1) = {а'1(1), ..., «^(І), уа (1), а'+1 (1),... —,ад (1)1 И ВЫЧИСЛИМ функции /ь . . ., іт
по этому набору в момент времени 1.
2) Рассмотрим ос (2) = {«, (2), ..(2), тД1)>
а'-+1(2), ...,04(2)). По наборам а(1) и а(2) (т. е. в конечном счете по наборам а(1) и а{2)—см. п. 1)) вычисляем в момент времени 2 и получаем "^(2).
Рассмотрим а(2) = 1^(2), .. .,а^г(2), уй(2), а'Ч](2), ... и по наборам а(1) и ос(2) вычисляем значе-
Г / / % , 1
ЦИЯ функций /і, , . Іа~\! /(ІІ ы • * • в момент 2 и т. д.
ГЛ. 3. О -Д. ФУНКЦИИ О ОПЕРАЦИЯМИ 09
I) Рассмотрим а(?) = {оц (і), ..., (г), уа (? — 1),
сс;+1(?), ..., а/( (/)|. По наборам а (1), а (2), а (О вычисляем /<г в момент времени ? и получаем 7с! (О*
Рассмотрим а (?) = (?), ..., (Г), уа (?), а;+1(?), ...
• <*„(?)}, по наборам а (1), сс(2), ..а (?) вычисляем
зиачепия функции Л,-.Лі-і, Лі+і, • * • »/ш в момент ? и т. д.
Если Д, ..},п — о.-д. фупкции, то операция О может быть определена через канонические уравнепия. Пусть и зависит с запаздыванием от переменной Возьмем систему канонических уравнений для /ь ../т:
г1(1) = Рі {х^і), жД?), хп{і),
д,(?- 1), д,(?- 1)),
г,<(1) = ['«{хііі), . ' *? ї ? • я»(0. д,(? — 1), ..
• • Ч ^ (0 ї ... 9і(*-1)),
ді(0==сі(*сі(0, ? * ч ^(0> * ,.хп (?),
Їі(ї-І)),
йі(0= . * ч (0) ?
- 1) $(*-!)),
д1(0) = ... = д,(0) = 0. .
Здесь прочерк в наборе аргументов у їїа обозначает, что Рл существенно не зависит от х} По этой системе канонических уравнений путем выбрасывания ??-й строки и заменой переменной X} на строим новую систему
100 ч. I. ФУНКЦИОНАЛЬНЫЕ СИСТЕМЫ С ОПЕРАЦИЯМИ уравнении:
*.(*) = О (*< ё) В.(*.(»)', •?•
.., .«*, #Д?), 1
9і(? —1)), *„(?)» ?і(?-1), .дД?-1))\
.., •. •» х„ (0» *71 Д ~ і) і ? ? *
• ? •> 9-'(^ “ 1))» ? *ч ^ДО> Д — 1)ї • • *1 Яі{^ ~ ^))і
2<,+ 1Д) = /\;+ДгД0, --ч *’ДМ0. - *?
з:,,(і), 9і(^“1),
..., 9Д?-1)), ..., *Д0. ?Д*~ *). ?Д?~ 1))»
г™(0“^«(яДО. ^ДяДОї ...
* * •» , * • -і %п (0 > я> (? і *•*
*?., 9і(«-1)) агДО. ?Дг“0.............5-(г — 1))»
ЯД0 = Сі(жД0» ^ДМО.
. * ?? 1 •?•! (0 1 ЯІ {? ~ І ) І •••
..., д,{і — 1)).....Хп(0, д.Д™ 1)....д,(?— 1)),
9і(0= СДлДО. ? ЯДяДО.
? • і ..-і ^Ді), 5іД ^)> ?•*
..., д,(і — 1)), ..., Хп(і), дД? — 1), ..., ?Д? — 1))\
9і (0) = ...*= ?Д0) = 0.
Эта система уравнений, очевидно, определяет те же о.-д.
функции 1ъ , /(*+1, . . -, /т» которые бьіЛИ ОНрЄДЄ-
лены выше. Отсюда следует также, что система о.-д. функций, получаемая таким образом, не зависит от выбора канонических уравнений для Д, ..., /„, (при условии, что Ра существенно не зависит от зД.
Приведем пример, показывающий, каким образом выглядит применение операции О в данном случае. В качестве исходной системы о.-д. функций возьмем систему,
ГЛ. 3. О.-Д. ФУНКЦИИ С ОПЕРАЦИЯМИ
101
задаваемую каноническими уравнениями г(?) = x(t)F- y{t)+q{t— 1) (mod 2), w{t) = x{t)y(t)V x{t)q{t — 1)V y{t)q{t— 1), qity^uit), q{ 0)=0.
Как было отмечено выше, обе функции z и w зависят от переменной и с запаздыванием. Посредством тождества
и{1) = w{t)
введем обратную связь. После исключения получим следующие канонические уравнения:
z{t)=~z{t)+ y{t)+ qit-i),
q{t)=x(t)y(t)\/ x(t)q(t — 1) V y{t)q(t — 1),
ff(0)«0.
Таким образом, результатом операции О является о.-д. функция, представляющая сложение двух последовательностей.
Теорема 6. Класс о.-д. функций замкнут относительно операции О.
Введение операции обратной сеязи можно более компактно охарактеризовать в терминах подстановок функций Fit ,. .t Fm из Ра, входящих в канонические уравнения.
Рассмотрим случай, когда операция О применяется дважды, и для простоты будем считать, что сна применяется к парам (zlt г,) и (z2t я2) ((dIf /*)— (1, 1) и (d2, /а) = (2, 2)) (что легко достигается перенумерацией функций и переменных). В основе канонических уравнений лежат уравнения
Pj (^t, х2у • • >, ?Тп» Qi) • -
z2^F2(xt, x2, xn) qt)t
Zm Fn. (~Ci, 3^2, • • ^l) ,
которые, положив u=(x3, xn, кратко за-
пишем
Zi^Fi(xlt xz, u), z2 = F2(xlt xz, u),
|м > 4.1. ФУНКЦИОНАЛЬНЫЕ СИСТЕМЫ С ОПЕРАЦИЯМИ
’Гак как по условию применима обратная связь (г3, д^)’, то
= Л(— и),
т. е. /ч существенно не зависит от XI. При помощи подстановки дт ~ Т\ (—, я2, и) мы получим систему уравнений
Хг = Р2(Р1(~, Хг, н), Я2, и)
По условию возможно введение обратной связи (з2) я2). Эго означает, что
Рг(Р,(~, яг, и), х>, и)
существенно пе зависит от я2. Таким образом, введению обратной связи в последовательности (г1( дь), (г2, я2) соответствует исключение переменных Д; И Хг В ИСХОДНОЙ системе при помощи подстановок
