1626435694-d107b4090667f8488e7fa1ea1b3d0faa (844295), страница 53
Текст из файла (страница 53)
ш-Р Нам остается понять, как распорядиться информацией о разметке дуг схемы булевыми функциями, изображающими множества наборов, с которыми возможно прохождение данной дуги при порождении конфигураций. Как во всяком индуктивном процессе, мы можем воспользоваться информацией о разметке только после ее завершения. Условием завершения является насыщение 258 ГЛ. 8.
ИСЧИСЛЕНИЕ РАВНОСИЛЬНЫХ ПРЕОБРАЗОВАНИИ разметки, т. е. когда переносы логических наборов со входов на выходы не меняют уже стоящих там булевых функций. Поскольку' при разметке имеет место только дизьюнктизное накопление, т. е. процесс, строго монотонный, насыщение обязательно наступит.
Йазовем насыщенную разметку стационарной и пусть при ней некоторый распознаватель Л с условием Р имеет на плюс-стрелке функцию Ф. Из правил разметки следует: а) Фс:Р; б) условие распознавателя Я будет передавать управление по плюс-стрелке только на наборах, принадлежащих Ф. Отсюда следует, что в Л условие Г можно заменить на Ф.
Смысл этого преобразования в том, что у множеств истинности условий схемы «срезаются» все недопустимые наборы, т. е. па которых это условие заведомо не будет вычисляться. Из-за этого, например, любое условие, передающее плюс-управление на недостижимый оператор, заменится тождественно лох;ным. Применяя правило устранения тождественно ложных условий, мы уберем входную дугу у оператора, после чего сможем убрать и сам оператор. Итак, мы видим, что свойство вершины в схеме Янова участвовать в процессе порождения конфигураций правильнее рассматривать в совокупности с множествами наборов предикатных переменных: вершина У называется достижимой, если существует непустое множество наборов Ф, допуск»имых для У, т.
е. таких, с которыми вершина у проходится при порождении конфигураций. Продуктивность. Постараемся в аналогичных понятиях описать продуктивные вершины в схемах Янова. Определим процесс порождения остаточных конфигураций для любой вершины У ,в схеме и любого набора Л предикатных переменных. Процесс порождения, остаточных коуфигураций отличается от общего лишь начальным шагом, который в данном случае состоит в переходе к вершине У, с набором О. Мы скажем, что набор Л является продуктивным для вершины у, если для этой пары существует остаточная конфигурация. Соответственно, вершина у в схеме называеФся продуктивной, если множество Ч' ее продуктивных наборов непусто.
Уже угадывается, что понятия допустимости и продуктивности исчерпывают проблему избыточных конструкций в схеме: вершина, являющаяся одновременно и достижимой и продуктивной,— это именно тот материал, который используется во мво«кестве конфигураций схемы. Рассмотрим индуктивный процесс разметки дуг схемы Янова булевыми функциями, которые мы будем выбирать так, чтобы они накапливали нам для каждой вершины множества ее продуктивных наборов.
259 ьал. постговнив исчислвния 11 а ч а л ь н ый и» а г. Очевидно, что для останова ля~бой набор является продуктивным (Ч'~~) = — $): именно эта функция метит все дуги, ведущие к останову. Ш а г и и д у к ц и и для распознавателя. Пусть у распознавателя В(Г) плюс- и минус-стрелки помечены соответственно Ч'+ и Ч', которые по предположению являются продуктивными наборами его преемников.
Естественно, что' для любого множества наборов М распоэнаватель может «пропустить» по плюс-стрелке только ГАМ, а по минус-стрелке — только АГАМ. Отсюда получаем, что Ч'в = ГЙЧ'.» () ~ГЙЧ" . В этом и только в этом случае Г будет правильно сортировать множество своих продуктивных наборов между своими преемниками. Функцией Ч'а метятся все дуги, ведущие в В. Шаг индукции для оператора. Пусть у оператора А(Р) выходная дуга помечена функцией Ч«.
Очевидно, что любой набор Ь, для которого Ч"(Л) = $, будет продуктивным не только для преемника оператора А(Р), но и для него самого. Но тогда и любой набор Л'~ шах Л тоже будет продуктивным для А(Р), так как наборы (Ь', Л) будут образовывать допустимую пару. Отсюда заключаем, что Ч',пр, = шах Ч' и этой функцией метятся все дугл, ведущие в А(Р). Очевидно, что везде под пометкой мы понимаем дизъюнктивное добавление метящих функций к тем, которые метили дуги в результате предыдущих шагов.
Аналогично случаю достижимости посмотрим, как мы можем распорядиться информацией, полученной после насыщения разметкой дуг схемы. Рассмотрим любой оператор А схемы с его мноя<еством Ч' продуктивных наборов. Если на его вход попадет непродуктивный'набор, т.
е. из ~%", то в этом случае мы знаем наперед, что процесс построения остаточных конфигураций при любом дальнейшем развитии не аавершится результативно: он наверняка попадет в бесконечный цикл. Таким образом, любая работа с любым Л~ ~Ч' будет бесполезной. Эту бесполезную работу можно заблокировать, если поставить перед оператором А распознаватель В(Ч') с плюс-стрелкой, ведущей на А, а с минус- стрелкой, поставленной на заглушку — простейший пустой цикл, имеющий вид распознавателя с условием 1 и обеими выходными дугами, ведущими на него я;е самого. В дальнейшем будем изображать заглушку (рис. 7ЛО, б) символом ®.
Заметим, что блокирование движения с,непродуктивными наборами не только предотвращает «ненужные» вычисления, но и делает непродуктивные»(а- боры недопустимыми для соответствующих фрагментов схемы, 260 ГЛ.В.ИСЧИСЛЕНИЕ РАВЫОСИЛЬНЬТХ ПРЕОБРАЗОВАНИИ что может быть замечено на предмет их возможного удаления иэ схемы. Очевидно, что такую же блокировку надо ставить и длв входной стрелки. На рис. 8.1 и 8.2 показаны некоторые' пары 'зквивалентных схем Янова, преобразуемость которых опирается на понятия достижпмостн и допустимости (8.1) и (8,2) продуктивности. а) ф ф~ ф лр Рис. ЗЛ. Преобрааоаание с яспольаоааннем понятия допустимости. а) Исходная схема. б) Стационарнан верхняя разметка. в) Срезание недопустимых наборов.
г) Ликвидации одного тождественного условия, замена другого на его отряцааие, стационарная верхняя разметка. д) Срезание недопустимых наборов. е) Ликвидация тождественного условия. ж) Ликвидация оператора беа входа. Перечень правил. Подведем некоторый итог. Наши правила равносильных преобразований группируются по пяти категориям„ которые мы назовем: логические правила, топологнческие правила, б) оюоиианарнол нилснлл рахита о) блоарпаное неорааунюлени» носарев ф~ валено условий но влашу~ Ооние ф Перенос снрслак е) Уйлсню нерпбо~ппюциртпоттиай Рнс. 8.2.
Преобразование с использованием понятия продуктивности. е) Исходная схема. б) Стационарная нижняя разметка. в) Блокирование непродуктивкых наборов. г) Замена условий на их отрицание. д) Перенос стрелок. «) Удаление неработающих распознавателей. ГЛ. 8. ИСЧИСЛЕНИЕ РАВНОСИЛЬНЫХ ПРЕОБРАЗОВАНИЙ правила верхней разметки, правила нижней разметки, правила замены. Логические правила постулируют связь базисных булевых функций (ложь, отрицание, дизъюнкция) с правилами выбора плюс- и минус-каправлений при вычислении условий в распознавателях. Это: (А1) удаление распознавателя с ложным условием, (А2) — правило отрицания (рис.
7.4, а) и (АЗ) — расчленение диаъюнкции (рис. 7.4, б). Топологические правила постулируют возможные изменения графа переходов. Это — (А4) правило удаления преобразователя, не имеющего входных дуг, (А5) перенос плюс-стрелок (рис. 7.7, а) и (Аб) — правило одинаковости двух любых заглушек. Мы о нем не говорили, но необходимость его становится очевидной при некотором размышлении.
Правила верхней разметки постулируют: (А7) — отсутствие наборов перед началом разметки, (А8) — допустимость любого набора значений предикатных переменных перед началом построения конфигураций, (А9) — правила распределения наборов по плюс- и минус-стрелкам при попадании на распознаватель и (А10) — свойства сдвига операторов как источника допустимых наборов.
Правило (П1) «срезания» недо- Г' пустимых наборов из множеств истинности условий в распознавателях позволяет реалиаовать информацию о допустимых на- ГГ борах в условиях стационарной верхней разметки. ' А, Правила нижней рааметки постулируют: (А11) — отсутствие наборов перед началом рааметки, (А12) — инициирование «~йе~ . ' разметки, начиная с останова, перенос разметки с выходных дуг на входные (А13) прн прохождении распознавателя и (А14) при прохон«денни преобразователя. Правило (П2) в условиях стационарности нижней размет- 'У А" ки разрешает блокировать вычисления на непродуктивных наборах. Рис. 8.8, Пример Правило замены (ПЗ) позволяет замефраг»1»лта.
нять вхождение логической формулы в схему на любую зквивалентную логическую формулу. Правило подстановки (П4) постулирует сохранение равносильности при аамене некоторой части схемы на равносильную. Нам остается ввести метаяаык для изображения найденного исчисления. Исчисление будет состоять из схем аксиом (А1— А13) и правил вывода (П1 — П5). Аксиомы и утверждения правил % зл.
постгокннв исчислвння вывода изображаются в виде У, У„ где — знак равносильности, а Я, и У з — некоторые фрагменты схемы Янова. Фрагментом схемы С называется некоторая часть 1(лг4 1 1 1 1 "- '-Ь.А-- 1 У 1 Г 1 1 1 Я 1 /) // // 1 1 а 1 а . ~1 ~/1 1 /1 ~(:)-Ф ° ° . - ° ° орй-М 1 У ' 1 ф 1 // 1 гг // 1 рэ//1 рХ Аз( (; мз~ ~Й Аю - зи~я-~я 1 1 1 1,6чиар учш/а иифр '1 Я1 г Р ~( а (т-Рчу)/ '~ /(р/ Г Ся-я ~/Ч Р /77) А,А Рис. 8.4. Исчисление равносильных пресбразоваввй. а) Логические правила. 8) Топелегическяе правила. Ч) Правила верхней разметки. (подгра~) схемы 6, для которой (части) указана ее свяаь с остальными в ршинами схемы 6. Эта связь укавывается в виде входов и выходее фрагмента. Выходы фрагмента — это размеченные дуги, показывающие, какие вершины фрагмента соединены с остальны- 264 ГЛ.
Э. ИСЧИСЛЕНИЕ РАВНОСИЛЬНЫХ ПРЕОБРАЗОВАНИЙ ми вершинами схемы. Входы фрагмента — это размеченные стрелки, показывающие, к каким вершинам фрагмента ведут дуги от остальных вершин схемы. Фрагменты могут быть конкретными и обобщенными. В обобщенных фрагментах вместо конкретных условий и онераторов стоят метапеременные, чьими значениями являются произвольные (или с указанными ограничениями) логические формулы, операторные символы и их сдвиги. Кроме этого, 1 1 1 1 1 1 1 1 (а лгАттла1 (а фчтх(А) Р А1() ~г ~)г4' А14~г~~~1 Аф и гь и Аф А(Р) гьг А(Р) 1рнк)1 Я ~к;) г "~ ь .~,г 1 г 1 А 1' 1' гэ фцЬчяау р) й ~ Ая ~наля )р) 7 Р 1 (г~) З л) Р =Аг Р(::гг) "ГЯ Рис. 8.5. Псчислеккс равносильных преобразований (ококчаквс), г) Правила ввжкей рааисткк. д) Правила эамскы, в обобщенных фрагментах могут быть так называемые обобщенные входы, которые указывают, к какой вершине может вести проиавольная (в том числе и пустая) совокупность дуг, выходящих либо от остальных вератин схемы, либо (если это не запрещено специальной оговоркой) от выходов этого же фрагмента.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
