1626435694-d107b4090667f8488e7fa1ea1b3d0faa (844295), страница 52
Текст из файла (страница 52)
Из леммы 3 вытекает Т е о р е м а 2. Две схемы Янова функционально эквивалентны тогда и только тогда, когда они эквивалентны формально. Замечательным свойством схем Янова является то, что все тре введенных вида эквивалентности $ ЬЗ. ЭКВИВАЛЕНТНОСТЬ СХЕМ ЯНОВА — функциональная (по результатам) — операционная (по истории вычисления) — формальная (по множеству всех возможных цепочек операторов, порождаемых схемой) оказываются равнообъемными. Истинная ценность этого обстоятельства, конечно, может быть осознана только в сравнении с другими рааделами теоретического программирования.
Для себя же мы воспользуемся этим обстоятельством лишь для того, чтобы сохранить за всеми тремя эквивалентностями одно обоаначение н взять аа основу построения системы равносильных преобразований формальную эквивалентность, связанную с понятием конфигурации. ГЛАВА 8 ИСЧИСЛЕНИЕ РАВНОСИЛЬНБ1Х ПРЕОБРАЗОВАНИЙ $8.1. Построение исчисления Исходные аналогии и догадки.
Сравнивая схемы Янова с их прародителями — формулами исчисления высказываний, мы нв можем не обнаружить значительное усложнение конструкций. Поэтому, хотя мы и стараемся следовать общей канве построения формальной аксиоматической теории, за редкими исключениями не может быть и речи о сколько-нибудь буквальном воспроизведении рассуждений, которыми мы руководствовались в повтори- тельной главе о математической логике.
Автор постарается ввести исчисление равносильных преобразований схем Янова некоторым, с его точки зрения, естественным образом, для того чтобы хоть как-нибудь показать читателю, как можно догадываться до подобного рода вещей. Однако, как уже отмечалось, экономия места и необходимость обеспечить поступательность изложения не позволит реставрировать реальный ход мысли создателей обсуждаемой теории, даже если бы автор опросил их самым подробным образом.
Тайна открытия остается для каждого искателя спрятанной за ванном с семью печатями, отпирать который ему сун<дено в одиночестве. Ыы будем вводить правила преобразований как аксиомы или правила вывода, постулирующие элементарные и интуитивно независимые свойства схем Янова. Некоторые из этих свойств нам с самого начала стали известны в виде правил преобразований, например, перенос плюс-стрелки (рис. 7.7, а)) или расчленение дизъюнкцни (рис. 7.4, б)), другие (например, понятие допустимых наборов) нам еще предстоит представить в виде удобного для работы правила, третьнещетолько всплывут ва поверхность при более детальной инвентаризации свойств. Попробуем, однако, навести в нашем хозяйстве некоторый порядок.
Нам нужно построить такую систему преобразований, которая для всех преобразуемых друг в друга схем сохраняла бы наш главный инвариант — множество (корректных) конфигураций, создаваемых порождающим процессом, описанным в конце предыдущего параграфа. Мы не случайно вставили слово «корректныхэ. Дело в том, что наш порождающий процесс при свое» $8Л. ПОСТРОЕНИЕ ИСЧИСЛЕНИЯ 25$ свободном раэвертывании создает существенно более широкое множество объектов. Это, во-первых, конечные цепочки операторов, упирающиеся в пустой цикл, и, во-вторых, бесконечные цепочки.
С другой стороны, даже при такой «дополнительной» свободе действий порождающий процесс может не затрагивать всего того, что внесено в текст схемы. Наиболее очевидным примером являются изолированные вершины, т. е. такие части графа переходов, которые либо не достижимы от входа, либо от которых нет пути на останов, либо обладающие обоими недостатками вместе (рис. 7ЛО). Можно вообраэить схемы, которые построены и работают в некотором смысле «наиболее экономною опи содержат только «выполнимые» операторы и не совершают никаких «бесполезных» действий, т.
е. таких, которые приведут к бесконечному двил«ению по преобраэователям и распознавателям схемы. Если мы претендуем на построение. полного исчисления, мы должны обеспечить преобразуемость любой схемы в любую, ей эквивалентную, в том числе и обладающую подобного рода экономностью. Поэтому нам нужно иметь в исчислении какие-то правила, поэволяющие обнаруживать, устранять, а когда надо и добавлять такие избыточные фрагменты схемы. В простейших случаях избыточные элементы схемы обнаруживают себя ораву.
Очевидным правилом является такое: преобраэователь с оператором, не имеющий входных дуг, недостижим и может быть устранен. Другим очевидным случаем является ситуация, когда на вершину ведет плюс-стрелка от распознавателя с тождественно ложным условием. Эту ситуацию можно, однако, сформулировать в виде более элементарного независимого правила: распознаватель Л с тождественно ложным условием можно заменить дугой, идущей от предшественника вершины Л к преемнику вершины Л по минус-стрелке. При атом плюс-стрелка от В исчезает вместе с самим Л. В общем случае свойство элемента схемы быть «пену»кным» не характеризуется им самим, а является свойством всей схемы в целом.
Неработающий оператор может быть вершиной в изолированной компоненте графа переходов, а тождественность условия маскироваться цепочкой предшествующих или последующих проверок других условий. Можно легко сформулировать два достаточных условия. Вершина У графа переходов схемы Янова наэывается лвазидостилгил«ой, если в схеме существует путь от входной стрелки к У. Аналогично, вершина У называется леалипродрлтиепои, если в схеме существует путь от У к астапову *). ») Читателю предлагается самостоятельно восстановить логическую свяаь етях определеянй с форнулнровеннем лостаточних у«повей недоствжнносте и непродуктивности верлош. 256 гл.
з. исчисление РАвносильных пРеОБРАЗОВАыии Материал первой части подсказывает нам, что так сформулированные свойства достижимостн и продуктивности хорошо описываются в терминах прямого и обратного транзитивных замыканий: достижимая вершина принадлежит прямому транзитивному замыканию входной вершины графа переходов, а продуктивная вершина принадлежит обратному транзитивному замыканию останова. Важным отличием схем Янова является, однако, что в распознавателях преемники выбираются не произвольно, а предписанным условием способом. Таким обрааом, недостигкимость вершины при построении конфигураций может оказаться замаскированной наличием пути от входной вершины, но содержащего распознаватели с противоречивыми условиями.
В связи с этим в уже известные индуктивные процедуры построения транзитивных замыканий нам придется внести ряд поправок. Достижимость и допустимость. Займемся сначала достижимостью, при этом для начала полагая, что ни один из операторов не меняет ни одной предикатной переменной. Этот случай нааывается пустым распределением сдвигов.
Начальный шаг: берем некоторый набор Ь значений преднкатных переменных и метим им входную стрелку. Индуктивный шаг: пусть набор гь метит входную дугу некоторой вершины т' графа переходов. а) Если Р— оператор, и его выходная дуга не имеет гг в качестве пометки, метим ее набором гг.
б) Если )г — распознаватель с условием Е ") и ни одна из его выходных дуг не имеете в качестве пометки, то метим набором Ь плюс-стрелку у )г, если Г(Л) = $, и минус-стрелку — в противном случае. в) Если )г — останов, ничего не делаем. Так описанная разметка оканчивается, когда ни на одном из индуктивных шагов нечего делать. Сделав такую разметку для каждого набора Ь, который моягно подавать на входную стрелку, мы обнаружим, что каждая дуга графа переходов окажется помеченной некоторым множеством (мол<от быть, пустым) наборов значений предикатных переменных.
Вспомним из шестой главы, что любая булеза функция может быть представлена своим множеством истинности и, наоборот, любое множество наборов значений логических переменных может рассматриваться как множество истинности булевой функции. Тогда мы можем сказать, что вершина гг графа переходов дослгижима тогда и только тогда, когда хотя бы одна из метящих ее входные дуги булевых функций не является тождественно ложной. «) Говоря о распознавателе с условием р, мм позволяем себе вольность пе вводить для булевой фупкппи, соответствующей формуле К, особого обозиачеяяя. % эз. ПОСТРОЕНИЕ ИСЧИСЛЕНИЯ Как только мы это сказали, нам видно, что это свойство останется справедливым, если мы освободимся от ограничения пустого распределения сдвигов.
Общий случай отличается от рассмотренного лишь тем, что если на входной дуге оператора А (Р) окажется набор Л, то на его выходной дуге окажется целое семейство наборов (Л'), каждый из которых образует с Л 'допустимую пару (Л, Л'). Второе очевидное наблюдение состоит в том, что этот индуктивный процесс разметки множествами наборов (или, что то же самое, логическими формулами) нег необходимости делать для каждого входного набора в отдельности. Можно осуществить тотальный процесс, а именно: подать на входную стрелку полное множество наборов, т. е. тождественно истинную функцию, а на все остальные дуги — в качестве начального значения — тождественно ложную функцию.
После этого трактовать каждый распознаватель В с условием Р как сортировку: если по какому-то входу поступает множество наборов Ф, то тогда то множество, на котором Р истинна, т. е. ФАР, дизъюнктивно добавляется к функции, метящей плюс-стрелку у В, а множество наборов из Ф, на котором г ложна, т. е. ~РАФ, дизъюнктивно добавляется к функции, метящей минус-стрелку у В. Для того чтобы завершить это обобщение, нам надо рааобраться в том, как вырааить в терминах булевых функций роль операторов, которые являются источниками выходных наборов, образун~щих со входными допустимые пары. Пусть Р— множество наборов, поступающих на вход оператора А(Р). Напомиим, что Р с: (Р„..., Рь), а Р— это фУнкциЯ Р(Р„..., Рь).
ПУсть Ф вЂ” множество всех наборов Л', образующих с каким-нибудь нз наборов Ь из Р допустимую пару. Рассмотрим любой набор 6 = о„..., аь и множество Чаг(6) наборов, получающихся из 6 варьированием переменных из Р. Тогда, по определению, если 6:Р пли, что то же самое, Р(6) = Г, то Чаг(6) с: Ф. Далее, если Г(6) = $, но в Чаг (6) есть такой 6', что Р(6') = $, то, по-преэкнему, Чэг (6) ~ Ф. Это очевидно, так как для любого 6' с:. Чаг (6) справедливо равенство Чаг (6') = Чаг (6), Если же для любого 6'с:Чаг (6) имеет место Р(6') = (, то тогда наверняка Чаг (6) () Д Ф = е(. Отсюда получаем, если считать, что шах((, $) = $: Ф = шах Р (р„..., рь).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
