Введение в дискретную математику - Яблонский С.В.
Скачать (прямая ссылка):
зависят с запаздыванием от переменных ^ то обратные
связи ((?!, /1),..,, (<?*, /*) записываем:
Х31 (г1* *?*» гг.)>
% = (*1* ' “1 *“)*
гт $т ('Т1> * ?
ЮО "-1 - 1 - ч^^тхцнидЛьШ ды^ ипих ьмы с: шш^лц и ям 11
Рассмотрим о.-Д. функции /ф, /фг, . . ., /фто, являющиеся образами в этом отображении функций Ф, Ф1, ..Фт. Легко видеть, что
и (/фЬ1 • • ч /фт) = т) = /ф*
т. е. образ суперпозиции, характеризуемой формулой $?, является супериозицией образов, характеризуемой той ни? формулой $[. Это утверждение на языке преобразователей
имеет совсем простой смысл. Пусть преобразователь (см. рис. 16) реализует функцию Ф(лц, ..хт) из Рк. Если на входы этого преобразователя подавать значения в моменты времени Ряс- 16 2 = 1, 2, ..то он, очевидно, бу-
дет реализовывать о.-д. функцию /ф(#1, ..., хп). Аналогично, пусть блок-схема (см. рис. 17) реализует суперпозицию
Ф(2Д, ..., а,п) = Ф0(Ф1(я1, .... хп), Фт{хи дга)),
где функции Фд, Ф1? ..., Фт принадлежат Ри. Если на входы этой блок-схемы подавать значения в моменты
хп
Рис. 17
? = 1, 2, то она будет реализовывать о.-д. функцию
/ф0{«\.-.Фт) = /Ф*
Таким образом, отображение Рк на взаимно однозначно и сохраняет операцию суперпозиции.
Функциональные системы (Рк, С) и (^к, С), обладающие указанными свойствами, называются изоморфными. Изоморфизм позволяет все результаты для {Рк, С) перенести на (?Ри, С). В частности, отсюда следует, что
ГЛ. 3. О.-Д. ФУНКЦИИ С ОПЕРАЦИЯМИ
107
имеет конечпый базис. В качестве базисов для можно взять, например:
1) {/о 1 Л, ? * ?> /а—1) $ 1и(х)г ‘ * *’ /йг~1<ж)! /пшх(х1,ж^] 1
где /о, Д, ..Зк-х — образы констант 0, 1, ..., к — 1;
2) [/ур^г)}, где У(х^ Х‘>)— функция Вебба.
Для произвольных о.-д. функций важно иметь их представления в терминах операции О и С через более простые о.-д. функции (аналог теоремы о разложении функций в А и А ^3), Как мы знаем, произвольная о.-д. функция может быть задана при помощи канонических уравнений
г{1) = Р{х1{г), ..., ха{1), <7^-1)', ..., ^ («-!))',
чЛ^)=(^1{х1{1), а*(0, {?!(?- 1), дД*- 1)),
ф(0 = СДл:1(^, хп{1), д,(г-1), ..., дД(-1)),
?1<0) = ... = д,(0) = 0.
Они «выражают» функцию / с использованием функций из Рк и не являются «формулами» в системе (Род, к, С, О). Однако нетрудно от них перейти к формуле системы (Род, к, С, О). Рассмотрим выражепие
г = /г(г:) . ..,1П1
—* —*
Ч\ = д!; ..., 5 ),
—*?
5; = /сД^1, - - Хт 5()-
Легко видеть, что оно образовано из функций вида /ф (принадлежащих и а; путем применения операций С и О: сначала в о.-д. функции /е,Айна места по-
следних I переменных подставлены о.-д. функции д1} ...
—^
..., дг (операция суперпозиции). Функции
А’ (’^'1? ? ? * г ?З'П, 51? ? * ? 1 5^)? (^1) * ? ? I ?Г.ч, 51, * • •, 5;), • ? *
> -ь->
" * *) /б; (^1, * * ?, *®л., 51? ? ? *, 50
зависят от переменных ..., 5,- с запаздыванием, поэтому возможпо введение обратных связей, (в силу теоремы 8 они не зависят от порядка) и результат приме-
108 Ч, I. ФУНКЦИОНАЛЬНЫЕ СИСТЕМЫ С ОПЕРАЦИЯМИ
нения операции О может быть записан в виде данного выражения. Следовательно, это выражение является «формулой» в системе (Р0д, С, О).
Итак, произвольная о.-д. функция / может быть записана в виде «формулы» (которую мы будем также называть канонической формулой) через более простые о.-д. функции при помощи операций С и О.
Теорема 10. Система о.-д. функций
полна е (Род.*, С, О).
Доказа тельство. Пусть f (ач, ..#п)’ — произвольная функция нз Р0д,*. Запишем ее в виде канонической формулы
Функции /г,/с1, принадлежат множеству 3?ь, по-
рождаются. (см. следствие на с. 107) системой
|/о' ? ? 'з А—Ь /Цг_і(а')і /тІгХ^И ?^а)} їжг)}«
Таким образом, каноническая формула может быть записана через фупкции исходной системы. Теорема доказана.
Л нал пгичпо доказывается
Тен рем а И. Система о.-д. функций {/у(ач, хг), х} полш а (Р„я.н, С, О).
Та о р о м а 12. Пусть (Фі, ..Фстї — некоторая полная в (РА} 61) система. Тогда система о.-д. функций
является полной в (Р0д,*, С, О).
Следующее утверждение является обобщением резулы* тага И. Г). Кудрявцева [11].
То орем а 13 .Существует о.-д. функция / (аналог функции Шеффера) такая, что система {/}, состоящая из одной этой функции, является полной (Род,*, С, О),
? — Іе (^1, * * *ї хпі (7і, • -? ч (?і)іГ
Чі ~ /о1 (*^'1У • ? ? 5 {?1і 1 • • і Ці)%
(хи і *. л хпг і «*з Я і)'
1-л. з. и.-д. ч>ушицш О ОПЕРАЦИЯМИ 109
Доказательство. Пусть Р0(лг4, х2, х3, х4) — функция из Рк, задаваемая формулой
Ро (лч, х2, х3, х4) = тах [лч ? х4‘+ .г3 (1 - я4), лч] + 1 (той &)
(здесь *, + и — берутся по тейй). Рассмотрим о.-д. функцию
]{хи *а, я3> ж4) = /Го (а?!, х2, я3, л:*)'.
Покажем, что система {/} полна в (Род,*, Су О). Положим =?= Хз и рассмотрим
Ро(^1, Хг, хи я*)™ тах[?„ х2] 4- 1(той/е) = V(хи хг),
где V — функция Вебба. Тогда в силу упомянутого выше изоморфизма
](х1> х.2, лч, лг4) = /у(лч, х2) ?
Данная функция, порождая все ?Рк, позволяет построить функции /о, /и Д_, и /*+*-!(«). Рассмотрим суперпозицию
/*+Й—1 (/ (А, /о, /о, ?4)) ~ /х+Й-1 (/в0 (/и /о, /о. ^Ч)) =
