1626435695-d1df5d2e6d953ce7ad4b4ccb5f4f4e30 (844296), страница 35
Текст из файла (страница 35)
Пусть А — В, где А — распознаватель с ус- ловием ол, Л-дуга которого ведет к вершине Аь, зд = (Л = ол) г, «ь Л = О, 1. Тогда тЛ Аь — В. Д ока за тел ь с т в о. По определению результата прог- раммы(8 (А), 1) для!~ С!(гь) нмеем та1(Я (А), 1) та1 ф (Аз), «ь «ь !), так что т Л Аь — А. Иэ гз ~ г следует А — В, поэтому трап° ь эитивность отнопюния гь-эквивалентности дает ч Л Аь — В.
Заметим, что в условии леммы ке требуется, чтобы А, В были вершинами сквозных схем. Д Л е м и а 7А1. Пусть А — В для вершин А, В двух разных схем, удовлетворяющих усммию разделенности переменных, при- чем А — оператор присваивания х:= $, выходная дуга которого «' ведет к вершине С, а г' = (х:= г) з. Тогда С вЂ” В.
Д о к а э а т е л ь с т в о. Воэьмем произвольную интерпре- тацию 1 Е= МСХ (г') и построим интерпретацию 1, следующим абрагом: 1 у, если у~= Ъаэ(г), 1«(У) = ~ г, если (у= т) е= аггее (г) и т — терм над переменными нэ Ьае(з). Если логическое выражение я содержит вхождения переменной х только внутри подтермов Ф, то положим 1, (и) = 1 (я [х/Ц).
Если же я содержит вхожденик х вне подтериов з, то прн (й = = я) ~ аввегз(г) положим 1, (и) = Л, а в остальных случаях определим 1, (я) произвольно. Нетрудно видеть, что 1, я МС1 (г). По интерпретации 1, построим интерпретацию 1': 1,(у), если у„-Ф*х, (У) 1,(з), если у =х. Для произвольного логического выражения я положим 1' (я) = = 1, (я [1/х]). По определению результата программы (Я (А), 1,) имеем ъа1 (8 (С), Г) сы ъа1 (8 (А), 1,).
Далее, поскольку А В и Е, б= МС1 (з), получаем та1 (8 (А), 1,) та1 (8 (В), 1,). С другой стороны, та1(8(В), 1,) ~ та1 (8 (В), 1'), поскольку интерпретации 1 и Г отличаются только на выражениях, содержащих переиенную х, а в 8 (В) переменная х не встречается. Таким образом, та1 (8(С), Е') ж ъ'а1 (8 (В), Г). Но Г (я) = Х, (я [о/х)) =- = Е (н [з/х) [х/з)) = Х (л) для любого логического выражения я, т. е. интерпретации Е и 1' согласованы, поэтому в силу ленин 7.8 нивен та1 (8 (С), Г) ж 1' (та1 (о(С), 1)) и та1 (8 (В), 1') сы Г (та1 (8 (В), 1)). Это значит, что либо оба результата тв1 (Я (С), 1) и та1 (8 (В), 1) не определены, либо оба определены и Г (та1 (8 (С), 1)) = Г (ъа1 (8 (В), 1)).
Покажем теперь, что если 1' (у) = 1' (ъ) для некоторых у е-:Ю и герма т иад перемекныии ив Ьав (г'), то 1 (у) = 1 (т). Рассмотрим для этого два возможных случая. 1) учь х. Тогда 1,(у) = 1" (у) =1' (т) = 1, (т [о/х[) > +(у =к[о/х)) я аввегъ(г) Ф(у = ъ) е аввегъ(г)-+1(у) = Х (т). 2) у = х. Тогда либо т = х (и 1 (х) = Е (т)), либо терн з не содержит вхождений переменной х. В последнем случае 1' (х) = = Е' (ъ) -> 1, (з) = 1; (т). Пусть хи ..., х„— все переменные терна з. тогда тв (1~(1~(и) йт~ т = 8[то/хи .
° ., т„/х [ и 1, (хо) = 1, (чо), откуда т1 (1 ~1~( и) (х, =т) б= амико(г) =+ М (х = ч) ~ авзегь (з') -Ф 1 (х) = 1 (ъ). Предположим, наконец, что ъа1 (8 (С), 1) Ф та1 (8 (В), Х). Тогда найдутся такие у б= Ьав (з') и терм т иад переменными иэ Ьав (г'), что 1 (у) чь 1 (т), ко Г (у) = Г (т), а это противоречит только что доказанному. ~ Л е и и а 7А2. 11уеть А — *' В и А — '* В длв двух таких сетей ги г, чтоЯАБЫТЬ) г = СЗАБЫТБ> г и (Л= и) б= аввегь (гз) с=> ти (Л = и) б- :аввегь (го) длв любых а Е (О, 1) и логичгсках заражений я. Тогда А Уд-'о В.
Д о к а з а т ел ь с т в о. Пусть г = гз/ъ ь, Возьмем произвольную интерпретацию Е б:— МС1 (г) и построим согласованные с ней интеРпРетации 1м 1о, 1, ~ МСЕ (гз), 1о бс МСЕ(гз). Тогда из У1 = 1, 2А 'Вследует т1=1,2та1(8(А),1/) та[ (Я (В),1/), В В. к, котов, в. к. совоооаозов Абв а лемма 7.8 дает ту = 1,2 та1(8(А), Еу) 1у (та1 (8(А), Х) ) и Ч»у = 1, 2 та1 (8 (В), Еу) еи Еу (та! (8 (В), 1)), откуда ЧУу = = 1, 2 Еу(та1(8 (А), 1)) Еу(та1 (8 (В), Е)).
Зто значит, что ча1 (8 (А). 1) н та1 (8 (В), Е) либо одновременно не определены, либо определены и Ч»1 =1, 2 Еу(та1 (8(А), 1)) =Ху(та[ (8 (В),1)). В последнем случае предположим, что та! (8 (А), 1) чь чь та1 (8 (В), Е). Тогда существуют переменная р б= Ьаз (г) и терм т над переменными нз Ьаз (г) такие, что т»у = 1, 2 Ху (р) = = Еу (с), но 1 [р) Ф 1(т). Далее, т'у = 1, 2 Ху (р) = Еу (т) =Ф Ч»у = 2 (р = с) е= азгегс (гу) =о (р = с)»== азэегФ (г) ~1(р) = = 1(т). Полученное противоречие доказывает та! [8 (А), Х) = =-1(8 (В), Е). И Т е о р е м а 7ЛО.
Если 8» ° 8 для приведенных сгободнмл сягогниг слом 8п 8г, удоелетеоряющиг условию разделенности перел»еннг»г, то для наясдой достижимой гери»ини о = [А, В, г] граС)а О (8п 8г) справедливо А В. Д о к а за тел ь ство проведем вндуяцией по количеству достижимых вершин графа О (8„8 ), построенных к очередному шагу алгоритма Ф. Для вершины о = [А, В, г], к которой ведет вход е, доказательство А — В получается повторным прнмененввм леммы 7Л1. Пусть для всех вершин [А, В, г], построенных к некоторому шагу алгоритма %, уже доказано А В. Мы докажем теперь, что В» — Вг для любого из наследнвков о' = [В», Вг, г'] вершвны о = [Ап А, г], обрабатываемой на очередном шаге алгоритма %.
Пусть к вершние о' на атом шаге проводится 8»- дуга е вершины о, причем е — Л-дуга. Пусть, далее, гс = г„, (г) и 3 = (ЗАВЬЕТБ) я Примекяя леммы 7ЛО и 7Л1, получим Вс — В . Если ~е»1 (В» В, г») или еЧ (В„В, г»)»ч г, = 1, где гг = ТТ [Вм Вг, г], то в соответствви с описанием алгоритма М е имеем г' = гп так что Вс — Вг доказано. Если же е»1 [В», В „г»), но г чь 1, то зто означает, что среди обработанных вершин уже имеется вершина [Вс, Вг, г,], так что в силу индуктивного предположения  — 'В. Построим в этом случае сети г» = (УДАЛИТЬ~ г» (1 = 1, 2), где операция (УДАЛИТБ~: М' -».
Я' оавачает преобразователь сеген, удаляюпа»й все такие элементы с, двя которых Ч»(с) е= Рдс Эу (1 ~(у (»[(Ч» (с))) Х П !»пож (Г (е, у)) = О. Неформально. операция (УДАЛИТЬ) г» удаляет иэ аэзегс (г,) все утверждения Л = р (ты ..., т„), и: 1, в которых хотя бы одни из термов ту отличен от переменной. Легко видеть, что если одновременные вычисления сквозных схем 8», 8г достигли состояния [В», Вг, г,], для которого справедливо е»! (В» В„г»), то никакие продолжения этих вычислений не могут проверять предикаты на таком наборе термов (отличном от проверяемого в В» и Вг), на котором какие-нибудь предикаты уже проверялись раньше.
6» 1» Зто значит, что из В, Вэ вытекает В» — Вг. Заметим теперь, Ий что для Вы Вэ, г»» гэ выполи»шы все условия леммы 7Л2, так что »»л»» мы можем заключкть, что В» В,. В соответствии с описанием алгоритма 2[ в игом случае г' = г» /~ гэ. Но г» ~ г» для» = $, 2, а' поэтому э' = г /~ г э г»/~ г„откуда В» — В.
( ) Сл едс тане 7.3. Вели 8» 8», то аягериэ»г» 2[ гавани»ь еаетея уенеи»яо. Д о к а з а т е л ь с т в о. Если бы алгоритм 2[ заканчивался » без успеха„то А — В было бы ложно по крайней мере для тех вершин о = [А. В, г) графа О (8», 8»), для которых одно из проверяемых на шагах (За) — (Зв) условий оказывается истинным. 3 а д э н н е 7.6. Сформулируем новую схему врээвя прэсбрээоээввя Ф2 [Удэмки» н»Ф»ге»пи»як»»» раек»»кэ»атаая).
О»эвкдко, С С, есле фрэгмэит С» ксяуэаэтся вэ фрэгмэвтэ С» ирвмэнэннэм схемы правая Ф2. Докажите, чтэ система прэсбрээавэнвй Х О (Ф$, Ф2) является неанэй системой нрэсбрээсваикй дяя отношения функциональной экввээяэвтиссти сквозных схем. Уээ»»кис. Ээмэ»ьтэ, чтс каки крэсбрэээээикя схемы 81 в схему 8 дая произвольных экэвээяэвтвых [крик»денных се»бедных) сквозных схем сед»шкет»я в с»руктурэ граф» 0 [э"», 8»). Краткий обзор и комментарив Первым всесторонне исследованным классом схем программ были схемы Янова.
В работе Янова [78) впервые вь»делены и формализованы основные компоненты теории схем и в первую очередь — понятие схемы программы и отношение эквввалентвоств схем. Яновым были найдены алгоритмы распознавания зквввалытвости в этом классе схем„построена полная система преобразований, позволяющая трансформировать друг в друга любую пару эквивалентных схем. Схемы Янова активно иэучалвсь в различных модификациях и обобщениях.
Схемы Янова монте рассматривать как подкласс стандартных схем. Такое определение проще оригинального, так как оно не использует интерпретированные логические операции в условных выражениях в понятие сдвига (дополнительного средства управления воадействием преобразователей на распознаватели) еэ 263 ~78]. Однако такое сужение класса не слишком существенно, тзы более, что главные проблемы имеют одинаковые решения в определяемом ниже и оригинальном классах схем Янова. Схемами Яяеэо называются схемы иэ подкласса стандартных схем со следузвцвм базисом: ((х), (~агп, 4'~, ° ° .), (рР', рагп, ° ° -), (с'оп ( И0 (~ -'= У~ (~Н ~ > О) 0 (р (~) 1~ ) О)).
Другими словами, базис класса схем Янова содержит $) единственную переменную л; 2) только одноместные функциональные и предикатные символы; 3) только операторы присваивания вида л:= 1, (л), условные операторы вада р, [л) и заключительный оператор' стоп (л). Тот факт, что память схем Янова содержит всего лишь одну переменную л, трактуется часто таким образом: в теории этвх схем память реальных программ считается монолитной, не разбитой на отдельные ячейки, н внимание ковцевтрируется на логической структуре программ.
Пример двух эквивалентных схем Янова приведен на рис. 7.И. Рве. 7.И. Прамер двух еээвзалеатамх схем Янова Отметим, по всякая схема Янова является сквоавой, так что описанный в $2 алгоритм Ф распознавания эквивалентности сквозных схем годится и для распознавания эквивалентности схем Янова. В связи с тем, что статья Янова еО логических схемах алгоритмов» (783 «ве стала известна широкому кругу читателей, преж- ао4 де всего из-за того, что написана довольно трудным яаыком, рассчитанным в болывей степени на специалистов по математической логике, нежели па программистско (Ершов [15]), а также эвызвала эначителъный антерес и некоторое замешательство» (Ратледж [т36)), в начале 60-х гг. были предприняты попыткк перешложвть и упростить теорию схем Янова.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
