Введение в дискретную математику - Яблонский С.В.
Скачать (прямая ссылка):
и значениями первых ? — 1 членов последовательности (следовательно, у(?) не зависит от «,-(?)).
Пример 5. Рассмотрим функцию }(х) из Рд> 2, для которой у(?) = а(?-~1) и у(1) = 0, т. е. /(#) осуществляет сдвиг входной последовательности на один разряд. В даль-
—3»
нейшем мы эту функцию обозначим через х. На рис. 13
представлено дерево для х. Из рисунка видно, что х — о.-д. функция с весом 2 и имеет следующие канонические уравнения:
г(1) = д(1- 1),
9(0"“ *(0» е(0)=о.
Легко видеть, что функция х зависит от х с запаздыванием.
Пусть }(хи ..хп) зависит с запаздыванием от переменных . ,,ж^, тогда, очевидно, для любых входных последовательностей
СС1 = {«1(1), «1(2), О!(О,
ап = (а„(1), а„(2), ..., а„(?), ...) п любого момента ? значение К (О» гДв
К “/(«1.....«п),
полностью определяется значениями первых Ь членов последовательностей
«1» * ? • 1 «Ц —1» * ’ ?) 1 * * ? • •» «п
и значениями первых 1 членов последовательностей
«4,.....«1,
(значит, 7 (I) не зависит от
«^(О. • --.сыЛО)-
В случае, когда /(.г1; ...
..:гн) Р0д> А, можно дать определение зависимости от переменной (1 ^ ^ /г) с запаздыванием на языке канонических уравнений:
/(.г,, ..., хп) зависит от х1 (1 < ? ^/г) с запаздывани- рЕС
ем тогда н только тогда, когда / можно задать каноническими уравнениями
г(?) = , лг„((), <21 ((— 1). ?,(?- 1)),
..., Л.(0. *.(*“ I), ?:(«™1)),
(*)
?|<0) = ...-?,<0)-0,
в которых функция /?(,?„ гв) д,, ..с^) как функция вз Ръ существенно не зависит от х
И примере 5 видно, что Р{х, #)=<7, т. е. Р не зависит существенно от х, что согласуется со вторым определением зависимости от переменной с запаздыванием.
Пусть теперь о.-д. функция Цхи хп) зависит с вапаздыванием от переменных х\я- Тогда из (*)
для каждого х^ (V = 1, ..б) можно найти канонические уравнения, описывающие /, вида
% (?) = Р\ (х^ {?), • • • ^ Хгу—1 (0> ? • *
.,хп(1),д1^~ 1), . ..,?((? — 1)), Я\ (*) = °1 (х\ (0» ..?,*« (0. <71 (г — 1). • • ? 1 ?| и — 1)).
дI (?) = (хь(?), . • .| хп (0> Ях ? • • 1 #1 {Р ^))»
дк{ 0) = ... = ^ (0) = О,
где /ч получается путем доопределения из некоторой функции Р\ Ру>&Рк и существенно не зависит ОТ Х{у.
Таким образом, из Рг мы получа-Таблица 4 ем? вообще говоря, различные доопределения
Возникает вопрос, можно ли подобрать доопределения так, чтобы
Р1 = ... ^ ^ ^ Л
(Другими словами — найти такое доопределение которое бы существенно не зависело от
Если Р' — произвольная не всюду определенная функция из Рк, то гарантировать этого нельзя, в чем можно убедиться на следующем примере.
Пример 6. Пусть Р'{хи х2) определена на множестве <?, где <§Г = {(0, 0), (1, 1)} и (см.
табл. 4).
Очевидно, что /^(х,, хг)^х1 И Рг{хи х2) = х2 являются доопределениями Р\ причем Р1 существенно не зависит от х2, а Р2 — от XI. В то же время не существует доопределения Е', которое бы существенно не зависело одновременно ОТ XI и х2.
Однако при некоторых ограничениях, которые в нашем случае выполнены, поставленный вопрос допускает положительное решение.
*1
0 0 0
1 1 1
1Л, и-"А* Л1Л-Ц1'1а'а ^ ии&хг
VI
Теорема 5. Пусть Р'{хи ..., л:,,, уи ..., <г<)'— функция из Рь, определенная па множестве 8являющемся цилиндрическим по хи ..хп, и F/ допускает доопределения Ёи ..Р, такие, что Р% существенно не зависит от Рг существенно не зависит от х^ и т. д., наконец, РЙ существенно не зависит от Х{$. Тогда существует такое доопределение Т'’, которое существенно не зависит от переменных Х\г, Х{$,
Доказательство. Положим
\Р
Р {^1 х-и .. -, уд = |0
Р' па 8, вне 8.
Покажем, что Р существенно не зависит от . .. ,^3.
ПуСТЬ (^1» ? ? ?, ?п, ^1) * • -1 ^1/) В (Й> • • * 1 *ь • * *>
два произвольных набора, которые совпадают для всех
переменпых, кроме, быть может, х^,--------,Х1&. Тогда в силу
цилипдрпчпости 8 они оба одновременно либо не принадлежат множеству 8, либо оба содержатся в 8. В первом случае
т(й,.... с», р (Й......С ч,.....г,,) =. о.
Во втором случае
^ (Й......Й., % Чг) =? Р' (й> • • •. Й>,Чк • • ?. чО»
(Й С Чх, • ? •, Ч() - Р‘ (Й Й, 41, •: ?. Ч<).
Покажем, что
Р’ (Й, • -'-Хп, Цц ..мЛО (Й* • *..?п. Ли ••ч1']!)*
В самом деле, если это не так, то найдутся два набора
(СГг'"1 ?п'Ч1> и (й\-? -,ЙУ, *и, —»яО*
соседних по одной из переменных Х{^ ..., (напри-
Л. Я ш Я*
г для которых из условия ^ ^ следует & =
= ?г В
Г (й\ ? • •, С, ч» ? • •. чО Ф Г (сГ. • • •, С, ч„. ?Ч<).
Но тогда Р’ невозможно доопределить до функции из Рк, которая существенно бы не зависела от х^, что противоречит исходному допущению,
7 с, В. Яблдвский
й-1
ЛМ ч. I. ФУНКЦИОНАЛЬНЫЕ СИСТЕМЫ С ОПЕРАЦИЯМИ
Таким образом, Р существенно не зависит от х^,... Х\я и теорема доказана.
Перейдем теперь к определению операции О.
Пусть {/і(х„ х„), /т(хи хп)} (т> 2) —
система детерминированных функций и пусть її зависит
от переменной х} с заду ——»| —— ^ паздыванием. Тогда,
рассматривая эту систему как преобразователь с п входами и т выходами, мы можем й-'А выход соединить с ;-м рис- 1/1 входом (см. рис. 14) —
ввести «обратную связь» между выходом сі и входом /. Мы получим преобразователь, реализующий систему из т - 1 детерминированных функций
