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

| ь зкнвзанептные| преобрхаэовааня уйрэйдяюцих систем. - Методзческея разработке..--,М;; 1985,' 40с, | Реценэеяты| чз.-корр. ВВ СССР профессор дупвыов О.Б. кепд.чнэ.-ынт.неук,асс. Возккн С.А. Содерзенне 1. Введеяке 2. Зквявапектные 5. Знэкэелентвые ч. Зквнзехентные 5. Эквивелентные б. Зквяьэлеитные 5 форыун в Р~ ...

7 форнуз ь Р~... 11 схем иэ Ф.З. . . . 19 контактных схем 22 евтонетов . .. . . 52 преобрнэоьэнкк преобреаоэенын преобреэоьення преобреэовэныя преобрээовеыня Зкэинелектные преобразования 'упрезннюямх саотем - раздЕл курса "Злеыеыты ккберветнкп", который чмтэзся автором в МГУ с 196Ч года, сначала кек спецкурс, эатем кэк обяэатездяыв курс по спецнелькоств СПЧ7.

Пенкея теметаня эародклесь в алгебре к логыке ь связи с построением полных систем тоздеств, построеныеы полной скотски энская. Новым ымпульсоы для рээьятия этого яепрэвленяя якнлмсь реэупьтэтн П.В.Янова [1 5 для преобразования алгоритмов «сюда онн не вонзи). Зятем поякэнась серия работ, посвяьенных эквнвезентным преобразованиям других классов упреяляюапх скстем. В денную методическую разработку включены запросы эквнгнлентных пресбреэовэний для ряда классов упревзяьных систем «формул, схен нз фуннпяонаяьных эзеыентсв, контектных схем и автоматов).

пятернях рэсполозен ь порядке неростэяия трудностей, доказательства несколько усонерпенствозэны по срэвыенкю с кх первояэчельямы вздом. Х. ВВВДЕВВВ Прп проевтзрованна схей дзсзретпых преобразозатезей часто аспозьауют сзедуыаай подход ва основе предндуаего опыта а Раэзачвых теоретачесвзх сообразеазй раэрабвтнвкстсв первовачязьпый варвент схемы, который дает схему с требуемым фуввцвовзроваваем, но мовен бмть данеазм от оптамазьного ьэ)я|на« тэ. Затем осуп|ествляетсв этап усозервевстзозавая схемы, вкемевтарвнй ааг которого состоит з ааневе фрагмеатоз схемы (подпхены) ва боксе прощай фрагмент с тазам ве фувзцаовнрозавяем. В ревузьтате пачучеют схему с тен ке функцаовароваваек, во более простого зпда.

Зта усовервевстяоваввя продокзпщ до тех пор, нона сто ярэктаческв ьоэнозво. Ня этом процесс эакавчязветсв в покупают окончательный каркнет схемы. Разумеется, что данный эзркстачесвзй подход ве гаревтарует оптвмезьаого реэузьтете, ыо зовет деть спредеэеяныа МДант. Пряведеввое рессуздевне нззвется асходвым пуантам э проблеме эквавазевтннх преобреэсэаязй усреьляюанх сястен [ 2 ) . рвссматркзэетсн класс управляюаях сястем 'К = (|,)) кандан на которых харентериэуетсн парой (",: ,«15) Предпозагается, что этот клесс удоэзетвсрает требовэнвю регувярзоств, т.е. «Р =ГЙ) что всегда вмеет место дзн т.в.

кнгоратнпэозавянх У.С. Пусть 7 = ~(«Р) — фувкцвовявьвян харвктерасткке '«) ~ змрезвюаая опредезеввую сторону фуэвцзопнрозевпя у.С, Непрпмер, есдз (Х - ккесс азтоыатсэ, то Ч~ - его ваяовкческве уравнение, э 7 - о-д фузнцпя, спредезяенэя отняв урепнекввык ° В внаем случае ~ сдвоэпячзо опредепяется схемой 2 1. у.С. «)' з '«) иеэывеютск энкязезевтзымя, есзв пра опредезеввом соответствкк полюсоВ Посвокьку сана у,С. однозначно определены свояка схемемз, то мозно гоэорать тяпке сб экзввазеатвостм схем. 2 Пусть" ,<-честь,Г. , включеюаев в себя вевщорое подмаовестзо эзеыевтов а сзнзей мевду намк. Зте час~э ,'> эапэет нодсхеыу, есзз з вей е) опредепена созозупность полюсов «иногда обзацает спе- цифвиой - иепрамер раабвиается вя иходвве я имходвве полюса) теа, что и аей отвооатса - асе иераюю ыв 2 », иеиаюиаеси подюсаыа ,С - исе иераввы, по истории:Е:» соправасяетса с остадьиой частью '.С - ыоает быть еае авиве-то иераюю Х»; б) папюса определеввым обрадов вевуаероиавм (с учетом вумерециа в ; .

) а пра етад утачаеиаях етя часть ведается схемой. Предподэ вм, что класс Й видается препыдьвыы, т.е. дда иеидой схемы с'. вайдетса упраидяюавя састеме У , обаадвюааа этой схемой, т.е. У = ~:С,СР) В атои предпоиоаевиа подсдеме '-» схемы )'-. опредеияет, и, и салу регуиариоств, одвоааечюю обрееоы, подупреидюыую систему У» = (;5 » ГР») у.с. 3. Пусть у.с. Ук имеет теиое ае аодичестао в ту ае саецафвиу пописав иеи у.с. У» . Тогда ыоиио опредедать подстевовку у.с.

У вместо у.с. У» , ддодяаей д У . Пдя а~ага уделяют иа У ' у.с. У , сохреияя тоиьио папюса аа У» , затем и иим "првсоедввяют" с учетоы спецафаив полюса у.с. У а В реаудьтете мы падучем ае у.с. У у.с. У . Очевадао процесс прасоедааеваи ааааа осуаестють ывогюа способемв. В сдучае, есдв Ук имеет вумерацию подюсои подобвую У», суаествует естествеивый способ прааоедааеава Ук к прасоедвиевае соответствует аумерецвам даиюсов У» а Ук . например, у.с. У» - едеатроавея девиа, Ук - другеа едеитроввая демис (яе обвзетедьио того ае типа, что в У» ). Падстевоаиа вместо Ь состоит в удедеввы У» а аваева ее иа Ук .

Празвдьвость подидючеаая ламам Ук обеспечивается еа счет иепреичаюяей ваада, обеспечаиеюасй соатветстаае подвеси. ч. Вада Ук едвиаедеятяе У», то операция падстаиодди яеаыэеетса еивазедевтвой подстевоииой в случае, иогде подстановка согдасоипва с соответствием полюсов У, в У , обеспечадеюв»кк их еюааедеатвасть. В примере с едеатроивкаа даыпеыа, есда Уй одвого тяпе с Ц , то вемева будет еииададевтаой. Говорят, тапке, асти при любой аадададевтвой падставоиае и праиеводьвую У.С. ае ~Х ава переходи~ ь еииаэедевтаую у.с., то дда идассе Щ юшодвед прющвп эавииадеитяой замеаи. В атом сдучае ае У» У сдедует У ° У" 5.

Подмиоиество пар ( (' У, ~Ц еииаиаиевтиых у.с. аааыааетса састемой тавдести. В деаьвейвев тоядестиа У -~Л траатуются а раею»х сыысдах. е) счатаетсв, что тоадество У» — Уд еедает одау аиавиииеатвость, вмевио У» Уг б) счвтаетая, что тоадестао У» ~l~ зедает исе ваьаиадевтвоств, подучеюявеся аа деевой пу~ем согдесоиеядых, аеоморфяых, преобразоьеввй левой и правой час~я. в) счатеетоа, что тоадестьо У» — У. задает все экавзедевтвоота, паиучакииеся ие двиной спеЦведьаыма преобрезоиеаивма, видпчеюдами аеоыорфвые преобрезодеивя а согдасоьеяаые подстанавии в деьую а правую части. В дедьвейвеы и иатдом случае фяисируется треитоииа смысдв тоадестие.

б. пусть зядеае састсые такиеств ~( У» », к Г » в оп- 'Г »~ редедеавоы смысде. Тогда пасдедаиатедьвость где У ' подучеется вз У ', с = Г,е»...»ГР-») путем аяиааедеитвой подстявоьаи с асподьаоаевиеы тоидсстие ие деяаой системы, яазыиается еиюдядеатввм преобрезсьевием при памоап системы тоадеств (((Г» У ) ) Будем обоваачвть иерее УГ Г УГР' еиьдьедеятвсе нреобреэовеаие У в УГ .

Очевидна, что еиьяГо»»(г) иадеятвое преобрязовявве обладает сиойстваы юевавасти, т.е. с,дв ГГо' -~ Г ГГР» В случае, когда выподяее прапцип эиеаиядептиой аямеиы, мы имеем У ГР) У Г»Г 7. Системе товдести ~( У» У»)Г, аэ Я аязыьается додиой, есда ивиоив бы еи были у.с. У и У аз Я теиие, что У (,Г , суаествует аиваьедсатное преобрезоге- заесть. Осыоныой вопрос ыозность проиаводыть образом> ненример, с лентнмх псдстановон.

адесь состоит в том, чтобы иыеть ьоа- ахвынелентные преобреаонаыия экономным уяотреблением наиыеньпсго чпслн аквзве- Эте аедача лучше всего раареботене для вяе прз номоцв денной евсеевы тоздестз У' а Г ° 8. Основная пробзеыатзвв теорзз вкы»велепткых вреобреаовевзй грунпяруетсп возруг сзедуке»вх нвдач е) вчв о поот оввз систем то а тн. Посяозьву всегда сукествует трзввнзьпое ревенко ведачз, которое з качестве сзотеыы тоыдестз выест смстему всех пнр ((>»,Ух) вн И зюазелептнмх Е.С., то дезвзз еедвча требует уточвевзя. Под построеввек полной сзотеыы тоздеств подревуыеввзт построенме петрввзазьвой волной евсеевы, няпрзмер, ывняканьвой мсцпоств. Зоезравеясь к рвссуздеямп о проектврозаяяв схем, ыы нвдзм, что атал усозервеястзозввзн схем аезясвт от того, владеет лв ыззенер полной свечевой нрнвзл еязмвелевтнмх преобразовывай.

Пелзчве полной скотным презвл преобрпвозевзй прявцвпвельво позволяет получать сптвыальвув схему. Метеыетвчесны более точвув зллпстрацзп деет еадече об упровензз д.в.ф. ( с». Еек ыы выделы, тны змеятся дза правила преобреномявй! 1. Уделеяне ывовзтеля; г. уд е Оканнзеетсв, что прз новояз еты превлл (а овв ззлввтся еквзвалептыыык веыенемз прз тех усчонквх, когда овв прммеввмм) макло построкть зыбун тупяяовуы д.в»ф.> кскодк зв некоторой аепмсз соверыевной д.в.ф. Есзз к етхы превзлам добевять ессоцватявныа я воккутаткввые вазовы дкя А я 7 , то ояезется воеыоянны переходвть от одной енпзея созервеввой д.з.ф. к любой другой.

Отспде следует, что прв помоны атвх презмз мозно преобразовать еклввелевтпым обреаоы проышнольнуп д.в.ф, Я в звбув ей вквкьелеятяуп д.в.ф. Я д в ф Й» ~ тупмзсзен л,ы.ф. )» '=р аапзсь совервепвой д.в,ф. Щ' ~ вепзсь сонерзепзой д.н.ф, ',~7 " -'р тупкхонен д.в.ф. Щ =р д.в.ф. Я б) За ача с пост сенцы елго ытысн н сс ествленин эквивалентных п еоб зснаыый п ш помо ан анной системы тоз- родствевпой проблемы - нроблеыы аогзческого выводе. Следует далев ееметвть, что ыозво обобынть задачу об еьвкзалеятзых вреобрееовевялх, откнеазяксь от требонпнзн екнввелентвостз пра подстевозкел, т.е. ве предполагать, что (/ м(» в рессыатрвзать направленые преобреновапкя (подстановка), т.е, ресоыатрззать подстезонвз вела Ы-Ц Пра тякмх обобвепянх данная теыетзва схватит ркд еедач теории азолюцяа, теоряя построевзн слезных сметен (зн областн кынык, бволсгяк, техввкя) в т.н.

2. Эклвнелевтвые еоб аозепнн л и Ра Ивученые ехзвюалентных преобрезованнй У.С. ыы начвнаеы с простейвего нлесоа Т.С. - форыул алгебры логязз ь классическом банное - » , с> з У ( 3 ) . Зто делаетса потону, что н нсы аквззелеятные преобреаованзя выешт пренычный елгебрвзчесвый *еравтер. Ерове того ва втоы првыере нынзлпптсз основпме вден н методы, сзнаеяные с построенвеы полных сыстеы тоынестз.

Сначала проследзы хях выглядят сзстеыа понятый, для форР2 ' 1. Формулы (Х х Я неемвептся ра»пп»ык (екнвзелевтныык), соля соответстзумняе вы функцзз «с» з «О! разны. Зеярмзер Х,~.Х,= Х,УХ, влз Х,ьх,= Х,( Х, 2. Еслз Й,часть форыулм Й является формулой, то ова нааынеется подфорыулой форвулы Й . 3. Пусть Й, подформуле формулы Й в Й,- прокезольяая формула. Земена подфсрыулы Й,ва Йсн формуле Й неемнеется подстеяозкой Й вместо Й>.