Введение в дискретную математику - Яблонский С.В.
Скачать (прямая ссылка):
Таблица 2
Т а б л и ц а 3
X ?1 <1* F' CI ci.
0 0 0 1) О 1
0 0 1 0 0 1
0 1 0 1 t 0
0 1 1 не опреде-
лены
1 0 0 0 1 0
1 0 1 1 0 1
1 1 0 0 1 0
1 1 1 не опреде-
лены
V F с, о.
0 0 0 0 0 1
0 0 1 0 0 1
0 1 0 1 1 0
0 1 1 1 1 1
1 0 n 0 1 0
1 и 1 1 0 1
1 1 0 0 1 0
1 1 1 1 1 1
G'u с;, например так, как
D lft.vi.1* Uj JYIdJ LluJj V J rl JH Ijlj ПпЦИЦ I у j Ц '^2*'
Имен теперь функции Ft G|, Gg> получим канонические
ГЛ. 3. О.-Д. ФУНКЦИИ С ОПЕРАЦИЯМИ
91
уравнения
г (/) == ^ (/)(* — 1) V х(1)&д2(1 - 1),
= 1)Уя(0&?2(*-1),
9а(0” Чг{1— 4)У* (0&9* — 1),
чЛ 0) => 9а (0)« 0.
Заметим, что в случае, когда т = 1, переменные q в канонических уравнениях отсутствуют.
Таким образом каждой о.-д. функции можно сопоставить канонические уравнения. Однако выбор канонических уравнений не однозначен. Эта неоднозначность свя-аана:
а) с различными способами кодирования (нумерации) состояний;
б) с различными способами доопределения функций
с;.
Легко видеть, что канонические уравнения позволяют вычислить по входной последовательности
а = (а(1), а(2), ...}
выходную последовательность
К = -у(2),
Часто рассматривают произвольные системы (*) (у которых I может быть и больше ]1о?* г[) для задания о.-д. функции. В частности, может оказаться, что если для о.-д. функции /, определяемой этими уравнениями, взять любые канонические уравнения, то они не будут совпадать с исходными уравнениями.
§ 4. Операции над о.-д. функциями
При определении операций над о.-д. функциями удобно всходить из классов Рс,ь и Тд,*.
В П[1Й) так же, как и в Рц вводится операция суперпозиции: сначала определяется понятие формулы над системой функций из Рс,гм а затем каждой формуле сопоставляется функция нз Рг,Ъ' Легко видеть, что справедлива
^ Теорема 3. Класс детерминированных функций замкнут относительно операции суперпозиции.
92 ч. I. ФУНКЦИОНАЛЬНЫЕ СИСТЕМЫ С ОПЕРАЦИЯМИ
Суперпозицию детерминированных функций удобно изображать графически в виде блок-схемы. Если система содержит тождественную функцию, то суперпозиция сводится к мпогократному применению элементарных суперпозиций вида
т шт))-
Поэтому достаточно указать, как выглядит блок-схема для элементарной суперпозиции (см. рис. 12). На блок-
схеме квадратиками изображены преобразователи, которые реализуют функцию, написанную внутри квадрата.
1 Теорема 4. Класс о-д. функций замкнут относительно суперпозиции.
Доказательство. Так • как класс о.-д. функций содержит тождественную функцию, то для доказательства теоремы достаточно установить, что функция /(X), получаемая из о.-д. функций Д, Д, Д, но формуле
/т = /й(Д(Г).......
является о.-д. функцией.
Поскольку, как и прежде, функция рассматривается с точностью до несущественных переменных (а при добавлении и изъятии несущественных переменных о.-д. функция переходит в о.-д. функцию с тем же весом), то можно считать, что функции Д, ..., /т зависят от одних И тех же переменных XI, ..., хп> т. е.
/(&!, I . ., ? • *, ^я), I • <1 . • ", 3?п)5.
Выпишем канонические уравнения для /0, Д, ../т: г0^) = К0{у1{1), . ^т(0» Й(* — 1). ?, Й0(* — 1))*
яЧ (Н = <4 (У1 (0, ..., Ут (0, Й И - 1), - 1)),
ч\ (0 = Ч (^ (/), . . ., ут (?), г;? {?-!),..., я% (? - 1)),
Й(0)= -й0(0)-0;
( ------------------—-----------------“I
ГЛ. 3. О.-Д. ФУНКЦИИ С ОПЕРАЦИЯМИ 93
«ЛИ ®п(0> — 1)т —1 ^(? — 1)),;
д\ (0 = (Ж1 (0 хп Н)* ?1 (* — 1)» - ? •. я\ И — 1)),
« 9
«?, (О = с‘, (^1 (*).........(*), 91 (* — 1). • • • , (I — 1)).
?! (0) ” . •. “ ?!, (0) = 0;
М0 = Л»(*х (0, ..*„ ((). 9’." (« - 1) С (! -1)).
?Г (0 = 0"{х, (0. ..., I» (0. 9? (* — 1),. О - 1)).
гГт (*) - Спт (х,(0, • • •, (<), (< -1), -С («-1)),
вГ (0) =... =}Г„ (0) = °.
(Предполагается, что символы д] для разных пар (I, /) различны.) Покажем, что / можно задать также при помощи канонических уравнений. В самом деле, положим
^(*^11«1!! хпт #1» ? * ?) 9г0> 51» ? ? •) 9^» • • ? ?91 и • ?( Я^т) =
“ ^0 (?^1 (а'1> ? • • ? ‘Гщ $1» • • м ^1)1 ? ? *
г? ( т гл \ П О \
?* • » 5 Г т ^3^, . . •) Хп, , • • • , 9Хт^ > З11 ? ? ? ')
С Г 0 0 1 1 т т \
О ^1> * 1 ‘1 хп> $1> ? • • 1 9(ф» 9ь ? ’ • I 9^» • ? • »91 »* • ч 9^т/ в
(^1 (‘^ч» ? * •» хгпЧх1 - ? ?>
* * *Л Рт (^1, * • •! Хп,_ яТг • ?., 9^,), , 9?0)
П = о,
^*3 (^11 • * ч I р> 9^) (г ^ ^ ^ ^ а)»
Й4 Ч. I. ФУНКЦИОНАЛЬНЫЕ СИСТЕМЫ С ОПЕРАЦИЯМИ
Тогда уравнения
г(() = р (х, (()....»„((),??(*—1), —а,...
.... «Г («-1).....гГт («-!)).
в) (0 = (*1 (0 х« (0.9? (< — 1).......в?0 В — а. • •.
.. .,?Г(< -1).,. .л7м1« -1)). г'(0) = о,
0 < I т, 1 < / < 1и
задают, очевидно, функцию /. Теорема доказана.
В * определим операцию О, пазываемую операцией введения обратной связи.
Определение. Детерминированная функция }{хи ..., хп) зависит от переменной х{ с запазды-
ванием, если для любых входных последовательностей
а* = {«1 (!), а,(2), ..аД?), -Ь
ссп (ап (1), (2), ..сс?, (?), ,.
и любого момента времени Ь значение у(?)» гДе
У =/(а1( ..., 0?п),
полностью определяется значениями первых г членов последовательностей
СС1? • » «| С?{— 1} ОСуу-!} • * ССп
