Введение в дискретную математику - Яблонский С.В.
Скачать (прямая ссылка):
Ж1 = Л(—, Рг {РI (—, Яг, и), я2, и), в),
= ^(/^1 ( —, Д2, к), Яг, и),
причем правые части не зависят существенно от д2.
Пример 7. Рассмотрим систему из трех о.-д. функций
21(0 = я2(0жз(0 V 2 (* “ О'»
2г(0 = Я1(г)я2(0 V Д3(0 V Ч (* “ 1).
23(0 = ^(я1(0» «а(^) 1 Яз(0» 9(*-1))» д(г) = С(*1(0» Дг(*Ь я3(г), в(*-1)),
<7(0) = 0.
Здесь можно применить операцию О к (^1, Д1):
Рг{Рх{~, Дг, Да, , Яг, Я3, $) =
= (я2д3 V д)я2 V я3 V <7 = я3 V у.
Полученная функция существенно не зависит от д2. Поэтому мы можем далее ввести обратную связь (г2, я2), Введению обратной связи в последовательности (г,, х)), (г2) д2) соответствует пара подстановок
X, — Хг V <7,
я2 = Д’з V </.
ГЛ.. 3. О.-Д. ФУНКЦИИ С ОПЕРАЦИЯМИ
103
С другой стороны, невозможно осуществить введение обратной СВЯЗИ в порядке (z-i, хг ), (Zt, X,), потому что 1\{хи х2, х3, д) существенно зависит от переменной х2.
Данный пример выявляет некоторые негативные стороны введенной нами операции О, Следующая теорема показывает, что для широкого класса ситуаций порядок введения обратных связей безразличен.
Теорема 7. Пусть для системы о.-д. функций {/о /з> *-.1 jmh где m ^ 3, возможно введение обратных связей и в порядке (Zj, хх ), (zn, х2), и в порядке (z2, хг), (zi, ?',). Тогда результаты применения операции О совпадают.
Д о к а з а т о л в с т в о. Поскольку к системе о.-д. функций применима операция О как для (z1( хл), так и для
(д>, xz), то
Л = Л(~, в)’,
Fz=-Fz(xi, -, и).
В случае применения операции О в порядке [zu xt), (Zz, xz) мы используем пару подстановок
Xi = Fl(~, F2{F1{-, zs, и), -, ЯГ), гг),
Xz=*F2(FД-, х,, и), -, и),
где правые части не зависят существенно от xz. Аналогично, в случае применения операции О в порядке (z2, хг), (zu arj), имеем .
= Fi(—, Fz(xu —, и), и),
x2 =Fz(Fi (-, Fz(xit -, гг), гг), -, гг),
где правые части не зависят существенно от
Подставляя в правую часть второго уравнения первой системы вместо xz выражение Fz{xu —, и) и в правую часть первого уравления второй системы вместо Xi выражение FД—, хг, и), мы получаем тождественные системы. Теорема доказана.
Данная теорема легко обобщается па случай s-кратного применения операции О.
Теорема 8. Если система о.-д. (функций {fu ../т} содержит функции /з1? . . ., /г?с (m > s-f- 1; индексы попарно различны), каждая из которых зависит с запаздыванием от переменных x^,...,Xjs (индексы попарно различны), то тогда система функций, получаемая путем
104
Ч. I. ФУНКЦИОНАЛЬНЫЕ СИСТЕМЫ С ОПЕРАЦИЯМИ
введения обратных связей (<Д, Д), ..., (бД, Д), не зависит от порядка введения обратных связей.
Доказательство. В силу того что каждая из функций Дц, - * , Дц зависит с запаздыванием от всех переменных ад, .ад, введение обратных связей (е^, Д), ... ..., (бД, Д) возможно в любом порядке. Тогда на основании обобщенной теоремы 7 получаем, что результаты применения операции О при любых порядках совпадают. Теорема доказана.
Следующий пример показывает, что могут не выполняться условия теоремы 8, а результаты применения операции О не зависят от порядка.
Пример 8. Возьмем систему о.-д. функций
г1(г) = а:г(і)^з(0^ 1)>
г, (г) = ?,(?) Vх3(і) V 5(( — 1),
zi(t) = Fs{z1{t), х2(1), я3(г), 1)),
9(0“° ®а(0і хз(0і 5(^-1))»
<? (0) = 0.
Здесь возможно применение операции О в порядках (ги а^), (г2, х2) и (г2, аг), (гь .яд), и оно определяется одной и той же парой подстановок
В дальнейшем при многократном использовании операции О мы, как правило, будем иметь дело с ситуацией, описанной в доказанной теореме.
стороны, многократное введение обратных связей А)» (да, Д) для системы о.-д. функций Д, /1П приводит нас к системе из тп — 5 функций ОТ ГС — ? переменных, вычисление которых может быть осуществлено
Хі = X, V 9,
х2 = 1.
V
Рис. 15
а
При тех условиях, для которых справедлива теорема, многократное введение обратных связей (с?,, Д), ... ..(бД, Д) можно изображать так, как это сделано на рис. 15, ибо в этом изображении нет упорядоченности обратных связей. С другой
ГЛ. Э. О.-Д. ФУНКЦИИ С ОПЕРАЦИЯМИ
105
посредством однократной процедуры типа процедуры на с. 98, т. е. одновременным пересчетом по переменным
? ? *1 )*
Из теорем 4, 6 вытекает
Теорема 9. Класс РОЛ, к замкнут относительно операций С и О.
§ 5. Примеры полных систем
В предыдущем параграфе построена функциональная система (Роя, м С, О). Теперь мы приступим к рассмотрению вопросов полноты. Для этого необходимо предварительно изучить связь между функциональными системами (Р0д.а, С, О) и (Рь, С) и разработать процедуры построения «формул», выражающих о.-д. функции через более простые о.-д. функции.
Как мы видели в § 1, каждой функции Ф из Рк соответствует о.-д. функция /ф. Соответствие
ф -+? /ф
порождает отображение Рк на некоторое подмножество &й о.-д. функций.
Пусть Ф есть суперпозиция функций из Ри, характеризуемая формулой $[, а именно:
Ф~ЩФи ..., Фт].
*) Данное замечание справедливо и в случае, когда /ь <.. . *Рп — система детерминированных функций, в которой функции зависят от переменных с запазды-
ванием.
По аналогии с изображением операции обратной связи для преобразователей введем аналитическую запись для операции обратной связи. Если /|» ? • ч /» — система о.-д. функций и ...,
