С.В. Яблонский - Введение в дискретную математику (1060464), страница 17
Текст из файла (страница 17)
Тогда результаты применения операции 0 совпадают. Докааательство. Поскольку к системе о.-д. функций применима операция О как для (г„х,), так и для (г„х,), то г"~ рз(-, хи й), р,=р,(хи —, й)'. В случае применения операции О в порядке (ги х,), (гн хг) мы используем пару подстановок хю п1( —, ра(рв(-, хи й), —, й), й)1 х, е,(р,(-, х„й), —, й), где правые части не зависят существенно от х,.
Аналогично, в случае применения операции О в порядке (г„х,), (г„х,), имеем 1 рл(хи 1 и)~ й)ю х~ р*(р~( —, р~(х„—, й), й)', —, й)', где правые части не зависят существенно от х,. Подставляя в правую часть второго уравнения первой системы вместо хг выражение рл(хо -, й) и в правую часть первого уравнения второй системы вместо х, выражение р,( —, х„й), мы получаем тождественные системы. Теорема доказана.
Данная теорема легко обобщается на случай в-кратного примененпя операции О. Теорема 8. Если система о.-д. функций ф, ..., ~ ) содержит функции (в,,..., (з, (лг > г+ 1; индексы попарно различны), каждая из которых зависит с запаздыванием от переменных х;,,...,х;, (индексы попарно различны), то тогда система функций, получаемая путем 104 ч. ь ФункциОнАльные системы с Опегяциями введения обратных связей (ди ),)', „(до 1,), не зависит от порядка введения обратных связей. Доказательство. В силу того что каждая из функций1е1, ° ° ° 1в, зависит с запаздыванием от всех переменных х1„...,хьовведение обратных связей (ди 7',), ... ..., (д„у,) возможно в любом порядке. Тогда на основании обобщенной теоремы 7 получаем, что результаты применения операции О при любых порядках совпадают. Теорема доказана.
Следующий пример показывает, что могут не выполняться условия теоремы 8, а результаты применения операции О не вависят от порядка. Пример 8. Возьмем систему о.-д. функций х,(г)- х,(т) х,(г) Ч о(з-1), з, (г) = х, (г) ~I х, (г) Ч о (г — 1), з,(1) Р,(х,(1), х,(1), х,(С), д(à — 1)), Я(1) С(х,(г), хз(1), х1(1), д(з — 1)), о(0) = О. Здесь возможно применение операции О в порядках (з„х,), (еи хз) и (з„х,), (з„х,), и оно определяется одной и той же парой подстановок х, х,Чд, В дальнейшем при многократнои использовании операции О мы, как правило, будем иметь дело с ситуацией, описанной в доказанной теореме. Прн тех условиях, для которых справедлива теорема, многократное введение обратных связей (ди 1,), ... (д, 7',) можно изображать так, как зто сделано на рнс.
15, пбо в этом изобраРкс. 1б женнп нет упорядоченности обратных связей. С другой стороны, многократное введение обратных связей (ди Д), ..., (д„у,) для системы о.-д. функций ~и ..., ~,„ приводит нас к системе пз гп — з фупкцнй от и- з перемепных, вычпсленне которых может быть осуществлено гл. з. о.-д. еннкцни с опвглцнями (об иосредстном однократной процедуры типа процедуры на с. 98, т. е. одновременным пересчетом по переменным ьт х>„., „х;, ).
Из теорем 4, 6 вытекает Теорема 9. Класс Р„,э замкнут относительно операций С и О. в 5. Примеры полных систем В предыдущем параграфе построена функциональная система (Р., „С, О). Теперь мы приступим к рассмотрению вопросов полноты. Для этого необходимо предварительно изучить связь между функциональными системами (Рею„С, О) и (Ры С) и разработать процедуры построения «формуле, выражающих о.-д. функции через более простые о.-д. функции. Как мы видели в 3 4, каждой функции Ф из Р, соответствУет о.-Д. фУнкЦиЯ 1е.
Соответствие Ф порождает отображение Р, на некоторое подмножество Рь о-д функций. Пусть Ф есть суперпозиция функций иа Р„характеризуемая формулой И, а именно: Ф = Ж(Фн ..., Ф 1'. е) Данное еамечзяяе справедливо н з случае, когда 1о ... ..., 1„— спстема детерминированных функцнй, в которой функ- цнн 1е ... „ 1е завнсят от переменных э;, ..., э; с эапаздыи"' н ваняем. По аналогкн р иэображением операции обратной связи для преобрааозателей введем аналнтнческую запнсь для операцнк об- ратной свяан.
Если 1ь „ 1м - снстема о.-д. функцпй н 1е,, ...,1е, зависят с эапаздызаннем от переменных л1 ° . „ я , то обратные сэаэя (йь 11), ..., (е„ 1.) запнсываезп з =1(х,...,т„), '~, = 1э (ээ~ ° ~ е~ ) зн = 1э, (э, "" т„) ы 1м (еы ''' ээ)' 166 ч. ь отпкцпоплльпыв спстнмы с оппгзцпямп Рассмотрим о.-д, фупкцни ~ф ~э, ° °, Ь, являющи®я образами в этом отобрал~ения функций Ф, Ф„..., Ф .
Легко видеть, что ® (Ь1~ ° ° з 1Фр,) = Ги(Ф,...,Фщ) 1Фз т. е. образ суперпозпцпп, характеризуемой формулой 6, является суперпозицией образов, характеризуемой той же формулой 6. Это утверждение на языке преобразователей имеет совсем простой смысл. Пусть преобразователь (см, рнс. тб) реализует функцию Ф(х„..., х ) из Р„. Если на входы этого преобразователя пода- вать значения в моменты времени Ряс. 16 Г = т, 2, ..., то он, очевидно, бу- дет реализовывать о.-д. функцп|о 7е(хо ..., л„). Аналогично, пусть блок-схема (см.рис.
(7) реализует суперпозицпю Ф(ло ..., х.) = Ф,(Ф,(хо ..., я.), ..., Ф„(ло .', я„) )', где функции Ф„Ф„..., Ф принадлежат Р,. Если на входы этой блок-схемы подавать значения в моменты Рис. 17 1 1, 2, ..., то она будет реализовывать о.-д. функцию 1э,(о,,...,о„) го. Таким образом, отображение Рэ на У, взаимно однозначно и сохраняет операцию суперпозиции. Функциональные системы (Р„С) и (Ум С), обладающие указанными свойствами, нааываются изомор4нььэи.
Изоморфизм позволяет все результаты для (Р„, С) перенести на (Ум С). В частности, отсюда следует, что Уэ гл. 3. О.-д. Функции с опеРАциями тот имеет конечный базис. В качестве базисов для Д11 можно ваять, например: 1 ( ) 1е11, ° ° .~ 11-о 11«(хР ° ° ° 1!1«11хь 1е1х(х1х '1~1х1ах(ххх ))1 где А А ", (х- — образы констант О, 1, ..., и — 1; ) !Ь(х1 х,)), где у(х„х1) — функция Вебба. Для произвольных о.-д. функций важно иметь их представления в терминах операций О и С через более простые о.-д.
функции (аналог теоремы о разложении функций в Р. и Р„й > 3). Как мы знаем, проиавольная о.-д. функция может быть задана при помощи канонических уравнений з(1) Р(х,(1)', ..., х„(1), Д1(1 — 1), ..., Д1(1 — 1Ц, Д1(г)=а1(х1(т) ""х (г) Д1(г — 1) " Д1(г-1)) Ф Д1(г) 61(х1(г), ..., х„(1), Д1($ — 1), ..., Д1(1 — 1))', д,(0) ... д1(0) = О. Они «выражаютз функцию г с использованием функций из Р„и не являются «формулами» в системе (Рсь „С, 0). Однако нетрудно от них перейти к формуле системы (Рьь„С, 0). Рассмотрим выражение з — ~г(х„...,х„, д„..., д1), е д1 1с1 (х1, ° ° ., х,, до ° ° ° д1) Д1 1с1(хм ° ° 1 хх~ Д11 1 Д1). Легко видеть, что оно образовано из функций вида ге (принадлежащих 9'з) и х путем применения операций С и О: сначала в о.-д.
функции 1г,1с1 ", 1с1на места последних 1 переменных подставлены о.-д. функции д„... ..., д, (операция суперпозиции). Функции 1г(х11 ° . ° 1хх1 Д11 ° 1Д1)~й (х1ю ° °,хх~ Д1~ ~ Д!)> ° ° ., )с1(х„..., х„, Д„..., Д1) аависят от переменных д„..., д1 с запаздыванием, поэтому возможно введение обратных связей (в силу теоремы 8 они не зависят от порядка) и результат приме- 103 ч. ь ФункциОнАльные системы с Опеглциями пения операции О может быть ааписан в виде данного выражения. Следовательно, ато выражение является «формулой» в системе (Р„,„С, О).
Итак, проиавольная о.-д. функция 1 может быть ааписана в виде «формулы» (которую мы будем также называть канонической формулой) через более простые о.-д. функции при помощи операций С и О. Теорема 10. Система о.-д. функций ( ". 1» а ° ° ° з 1»-1з 11» (х) з ° ° ° ° ° э 12» 1 (х)~ 1ппп (х1ю х»)1 11пап (х1э х»)1 х) колка в (Р„,„С, О). Докааательство.
Пусть 1(х„..., х.) — проиавольная функция из Р„в. Запишем ее в виде канонической формулы е = 1г (х1, °, хп, чв ° ° в В) в у1 1С (Х ° ° ° Хтп Ч ° ° ° у~)в у1 1с1(х1~ ° в хп~ йи ° ° » у1) Функции 1е, 1с,,..., 1св принадлежат множеству йэв, порождаются (см. следствие на с. 107) системой (1 °" 1»- 11»(х) ", 11» 1(х), 1Ф1п(х» х»)) 1 „(хм х»))* Таким абрагом, каноническая формула может быть записана через функции исходной системы. Теорема доказана. Аналогично доказывается Теорема 11.
Система о.-д. функций (1„(х„х,), х) колка в (Р,, и С. 0) ° Теорема 12. Пусть (Фи ..., Ф„) — некоторая пол ная в (Рм С) система. Тогда система о.-д. функций (, 1Ф« (хм ° ° ° в хп)в . э 1Ф»в (х1э ° ° в хп)1 х) является нолной е (Р„м С, О).
Следующее утверлвдение является обобщением резуль тата В. Б. Кудрявцева (11). Теорема 13. Существует о.-д. функция 1 (аналое функции Шеффера) такая, что система (1), состоящая ие одной этой функции, является полной (Р„,», С, 0). гл. з. о.-д эвикции с опшлцнями тое Д о к а з а т е л ь с т в о. Пусть Р, (х„х„х„х,) — функция из Р„, задаваемая формулой Р,(х„хм х„х,)=шал[х, х,+х,(1 — х,), хз)+1 (шоз(х) (здесь °, + и — берутся по шоб й). Рассмотрим о.-д. функцию 1(хо хз, хь ха) 1го (х„хз, хз~ ха). Покажем, что система (1) полна в (Р„,м С, 0). Положим х, х, и рассмотрим Ра(хо хз, хз, х,) шах[хо хз)+1(шобй)' У(х„хз), где 7 — функция Вебба.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
