С.В. Яблонский - Эквивалентые преобразования управляющих систем, страница 3

Вснк система Р имеет коввчпую полную систему тоздеств, то н система ф такие выест конечную полную систему тоздвств. Доказательство. Пусть система Р имеет кояечяую йолную систему тоацвствйлЯ'О(~[рэ,.-, О( Я= О(' [Е1 плд ~арахис ЙЯ=Йе[Е1 Так кэк г и и баэисы Д~ , то Даа (-г,...фи~=~,..яй вайцттсэ ФорэуэыК;РЯ и О. (ф такие, что фя,[;[Я1э ц„.= О.Щ иэм кратко Г=Дф Ф=7Я) . Покаием, что скстема токдестэ (Д,[ГЕЩя = Я!'[ ( Щ ,ф= п(,Щ33 является поэпой для Я .

Рассмотрнм в $ пар~ экваэаэвптюгх формул $~ ~[Ф)=$ [Ц. Если в форнулэх Ь ' я эырвэнть бээнспыв, Функции Ь через Е , то мм получим эквивалентные Формулы О(~с[ЕЗ=~ье[))Ян Я н[Е1=Ьай[П[ЕП нэ ~" . цепочка преобраэоээпай: (д,"[я- О('е[р1 - О(ея осуацстьяяемых в ф , позволяет постронть цепочку лреобрэаованнй ~ ИЯЯХ[Б]~зЯггЩ~ Ц ~Я ... К)[Х[БЯзй [Ш[Б)1" ею[61 в (([ . Теорема докэаапа. Заметим далев 1. Теорема дает способ построения конечной позаой системы в проиэвоэьаоы баэасе 2. Сэойстэо иметь уопечпую поэпую сметану тоздеств зависит тольао от класса 8' з на зависит от басаев. Еак мы эндели в хя дзя любого эамкаутого кэасса мокко выбрать копечыый безас (теореме пос~а [4 ) ) и дэя ваго указать конечную пояаую систему тоадеста (Теореме йээдока [5) ).

Только что докаээааав теорема оэпачает, что дая любого эанкаугого классе нэ Р э эюпом копечпоы бавасе суаествует ксвечяен пояс пая система тоадестэ н тем саыымкэассемэ мозно абраааться как с традицзоаяыма аэгвбро-логическими обьектамв. Пра переходе к Рф окаэыээется, что смтуацмя стекоэатся более слезной, есзя Ф г т .

Вывако2 пе КэздЫй Эенапгтнй плесе имеет конечный баево в кэк нм пояезеы - пе дзэ иаадого эеняаутого язасса с конечным баэнссэ ваэыозао построить конечную полаую систему тоадеств. Первый такой пример э Рч быэ построек Лаадоеом [ 63, в 1е посзедстэаа удалось саааить эпэчзооть сиачааа до к=4 (Ванна [Т1) и затеи довести до мюшума хя 3 (йурсаай[З3) Здесь ны зэаоззн реэузьтат йипдопа, кото)ай с методической точка зреюю пэаавтсп попа саюю простым. Воэьмеи фупкцию ~(х<,х ) (ои, твбз.1 ) твбз.

1 Очеэидко ЯеРч ° В дэзьвейаем введем дзя аее боэее простое обоэпачепав ~(Х„Х)=Х, Хх. Обоэкачаы х х черен О, т.к. Фуюпюэ х х я О Расснотряи совоаупяость Формул Р, построеааых пад Х,.х~ а соотэетстэуююй ей эемззутый кэасс фукююй Ю . Показан, что раэввстэа Ааааа ' О'Хе-0)Х 'О 01Х (хахд Ь.д': (... ((Х,'Х,) Х,...) Х.) =С,еО (м-42,- ) С: (...((ХеХ )Х ...) Х'-)Х,=(...(ХХ.)Х, )Х (мя2,2,.-) эи са эР де тэ Дна Асхь угэеркдензе саедует аэ табюпю Дэя Ь утэерадеапе очеэадпо пра м= я . Пра м>1 очеэздяо Х,хх лабо разно О а ~отде кеми часть тоне равна О эибо " О э этоа случае принимает одно иэ эавченнй 45,6 , что воэмоэзо, асан х,=чу,6 - иногда зевая чань тазае раааа О . Дкя С рассыотрпи саедуанае эариааты дла правой часта а)(..(х,х.)...)х =О тогда а эаэел часть ранка О б)(.,(х,х).,)х =~, тетках,=4, ах,=2и эначзт леэна часть есть ~ 2.„, 2 я1 )( ( „С) ) 5 6, тогда Мр2,2~» эяи 6.х,=6 О(( х ) н 1(х х)дзе проиээокьюю эяэнэа эватпые Формуны иэ 'Р, тогда суаестэует экэизаэентвсе преоб- раэоэенпеО( в Б» цра помоап тотдвствАс,1,~ О где т и 15 Доиаэательство.

Повааею, что при уваэавнмх огрезачевавх воэмозио любую формулу зад Х»г.. »Х. прввести и вааовичесвоиу виду, в иачестве иоторого юн берси ивбо вмрааевае Х Х»» если )с,м0 звбо вырезание(..(х;,х„)..)х;„, где ваадый свивав зэ аифавнта Х„-,х встречается ве более одного рава.

Последнее имеет место, если <<и э0 Левее поваэыэеется, что при поюоав тех ае аравии (с ~ли ю) новью от одного иановачепвого ваде перейтв и зпбоюу еюу эавввалевтвому. Пусть Й (хо" »Х«) - провээоиьаая формула. Воэмоавы сведущие свучаи а) ~Х содераыт 0, т.е.

подфорюуиу виде и и , тогда, аспоиьэуя А » ь, й, преобрээуетси в 0 б) О( содерант уюыозевзе слева иеиоторой ветривиэзьвой под4ормулы (отлзчвой от символе переюеиыого), т.е. имеет фрагмент зила <<(Ъм) , тогде, ыспсэьэуя д ь, этот фрагмент перейдет в О, н мы приходим и гувхту а).

Теперь мозво предпоэегеть, что формула яе содерзит вуией и уывоаеыий одена, т.е. имеет вид (.,(х х;,)х;, )х;„ Левее рессыетраээютса форюузн, в воторыг уювозеаае совераается тозьво справа. В этою случае, есзв опустить сзобиз, то запись привнюает сиедуэаай вад Х;,Х;»...Х; Лопустим, что в форюузе змеится повторные вховдеаив перемеанмх а Х»»,Х;,- пара повтораюанхся перемеввых, т.е. Х;,= Х; гаваи, что ввиду Х;, а Х;чэстречаются переюенвюе аэ йвозестэа (хо...,х.1'» (х,,~ ае более одного Рева. В) Х„=Х<» . ТОГдв ПраМЕВНМО ПраВИЗО 8 С»»»с<» И Эю ПраХО- дам и сиучею в) г) Х;»ф Х;, . Тогда, обоэаачив начальный вусов проиеэедевиа Х; черен ц , подучим чм <<ХПХ;„,, Х;,, где Х; - Х< и мю повею я этой подформуие првмевить прэввзо <: <»» а»» В результате всчеэиет вхозденае Х...

Совервеа уиеааэвые преобрээоэаыня мы вибо позучан Х» Х; либо Х;, Х;„, где ывозителм ие повторяются. Теперь остается 16 повевать, что при поюоаи тех ае тоэдеств воэюозво осуаестэять эывзвалевтвое преобраэовеаие одной иавоввчесиой формулы в любую другую иевовачесвуп форюузу ей эивавелевтыуэ. Здесь юы имеем двэ случае 1.

<»я э0 . Пусть форюуиа Я. имеет два кавовичесвнх вида: х,х, н х х, . Счевндыо испольвуя А, и А, получнм х;. х» =(х х,)<х;х <:х т' 2. <ссФО . Доказан, что иввоиичесааЯ фоРмэ имеет едавстэевяый внд. Пусть фориупа Й. дояусяает две явыовичесвих представ евин Х»Х»х~у (») ы х< х)»- ' х)< и) а) сбе проаээедеыив состоят иэ одних и тех ае ювсзитеэей. Лопустию, что это пе таз в Х)»ч 1 . Тогда полагеею Х, = 1 Хч=х;,= Х; =2, е остэльаые переменные - 0 . В этом свучае первое произведение резво » 2 2 2 = д , второе - О, т.в.

СОдсрэят Х<,= 0 . Зтс ПрстяэсрЕЧКт ЕомпвеиЕятэсотм 1 З П. тенин оправою »)=(» и состав миоэмтеэей э 1 и и сднвевсв б)Х ,=х;,. Есин ато' ве так, то полегеен опять =Хм=2 Тогда < = <.2.2 2 = <, П= 2 <...2 = 0 . Певучем противоречие в) Порадоа мвозитезей в 1 в П одмвевовюй. Допустнм, что это ые тэя, тогда найдутся такие мвозвтеаи Х,, а Х;,, что )с Ъ а во втором проиээедевин мвозмтеэь Х;ч предюествует мвочителп Х», . В этом случае налагаем Х;,=»,Х;»= П,х;, = П , е остальные перемевыые - 2 . Тогда 1=< . 232- 242."2=~ и <«=, 242...

212...2=б что протаворечит эивиэалеятности 1 и П. Теорема доиээеве. Следствие. Система тоадеств А »д », 6,„,2 , ';~л м <.2, ) яэпяется полной системой тоздеств дл<.:(. . Теперь перейдем к вэучеиип полных систем тоздеств для('.. Мм»м»»»», вю т М Г ю ее <' 1. 0<. СОДЕРант СВЮЭОЭМ Х»»Х»г..,Х. 2. пе имеет подформуэ виде <».<» и <<(~<»г) 5. Пусть (Д =Х„ Х; н имеетсв второе (считая слева) ьхоадеине снювоээ Х;, , тогда левее этого второго вхоздеяия встречэптсв все символм переюепвмх иэ Х,,х„...,х „ 17 В оетаиюпа олувих ОС ые удовлетзорвет свойству С Наперл Левая чаеть аадеетза К удоваетзо)кет озойству С уйми). Вели Формула О( удозлетзорпет евойстзу С" в уь получепп из ОС врв повода аадеотз Аппп В„, и С,„где тяеп, то Формула Ь у реп йыпуС Лоиапательотзо. Очепидво длв устввовзеюа лавы доствточво раооыотреть случай когда Ь получаетсв зз О(.

одвой пкзкпалеп- таой подстаиовкой. Легко задеть, что тоздестза А л,ь щкмевать з О(, вельзя, т,а. О(. удовлетворяет п. 2 определеаав озойотза С" а О( = Х«Х(а-. Х(л С другой егоровы к ОС вппьпя мрвиеиить првюаоВ„,( е)вп-еп того, что левее второго вхоздеаап символа Х;, зетречаюты зае сзизолы перемеюпа Тч>.-~х .

Таюа образом к ОС ыоиао щаые- юаь тольао тоадеоюа С~,(и~ел), иотщме увзчтозают только пыторвые ююидеаав перемеюах. Поэтому Фо)аула Ь будет удо- злетзорвть свойству С Следствие. Зкзвзелевтвость Р~ „ (... (х, хдх,...)х„) х, = О ве копет быть пыучева пра попова тоздестз А< т т>В,„с ( я и) В паком деле, зевав плоть 6, удылетзорпет свойству С, а примак вот, а если бы зевая часть позучелаеь.юй врезой'ща ло- мова указавюгс тоцдеетз, тойо кредпдуаей зевке овв удозветзо- рвза бв такие езойетзу С" . ХФПЛПЛПп Лла овотеиы Формул '~ ие оуаестзует аозечаой полкой саотемп тоадестз. Локааатппьотзо.

Лопуствы, что системам' имеет ковечвую поп- арю систему тозд етв а,'=С(', О(',*О(~", Обоаиачам череп ааибольаай вомер переиелвогоХ, зстречко- иегосв в птах тоадеетзпх. На освозаюа теоремы давая сиоте- ма тоздеотв молев йаь получевв зв саотеиы ~йч.л,В,С„„~ ля) В то зе преки оиа поюыа, пввчвт вп аее аале юаестп тоздеетзо Ь... Следоюаельво тогда а ав езстеиы~Цг,ьб,б,"~м") вако было бы юаеотв тоадестзо В„,<, что протвюречит следствию юредмдуаей аеюа. Теорема доиаэеиа. Телам обрезом з Рипр ° й 2 попппвют ж илпсевУдлв лото1ах вет зоаечиой полкой саыеяы тоздестз. 18 Е. Зязпввлевтпые п об е завяв охем ав Ф.З. исод схемы,созвеаеюай со зходои апеыевте заход схемы,созппдптапй ео плодом схемы — ветплевзе паоле плеыезта зыход ыекепта, ве пзляюапйая выходом ыеыы 7К табл.

2 пкход схемы,созыеаепвый с входом плеиевте Лелея уточпам оевозиые повитая, сзяапюае с екзазелептваа преобраэозевзпмв 1. схемм л. =Б (х,.„т;п~,-.,п~)п '.> =Е (х - х 'и ,гт)напыляются 19 Этот перегрей качаем с везоторых Замечавай, иасвюаихоа попятив схемы из Ф.Э.С9 ( 1. Таа иек при вкзвзплевтвых преобрввоааивх схем зз Ф.Э. промепуточвме обьекты могут озаэвтьсз пе схемами ап Ф.З., то аесзыьио рвеаирам повятие озавы ие Ф.З. й иыевво мы допускаем а) добпплезве ввыарозаввкс пхоюиа полюеоп б) величие вводов, кото)аы ве првасва оюаолы зыходвого пл(ызита (пыходм пе мвюакяеск пыюоеии) з) допускаютев охеиы без выходюа попиков Прп этом естестпеюпа обрапом доопределяется и Фузпциоимрозаизе схеым: от перемеивого, щаписввпому ззоаврозеппому плоду, зппдый змход зависит песуцестзеюпа образом; Щувзцяоизропавие па юаодех ве язлпююаса попюсаыв ве определяетсв. 2.

Определевпе схемы зз Ф.З. пемз лава з геометричеекой йорке. Блпгодпрв етому обеепечвзается вагладвоеть обьектп, во зато позиикеет елемезт веоиредыеввости (вотормй копет быть полностью устрпвев, вела исходить ап ебстреитпого определезвя ехемм). Поэтому мы змпуздевм сделать веиото)ае оговорил, касатыиеы отепдертвьацзв веобрвзевзв охам (см.таблицу 2 ) вполарозаипый зпод схемы е ° эквивзлеытными, есля урзвненяя ~,ю~,'(Х„...,Х.) ~2,=(,"(Х,г.чы.) ~р-~'(хч.,ех.) ~рр--чр" (с„,х.) описывающие их <Пуэлционировение,имеют равные правые части,т.е. ~,'(ХЧ...,Х.)=((Х,—,Х )," Э('(ХΠ— чХ.)=(р(ХΠ— тХ ) Схемы с одинаковыми эходэми и без выходных полюсоз считаются аквивзлентнмыи 2.