ПОИСК Статьи Рисунки Таблицы Реализация схемы. Равносильность схем Выражения. Равносильность выражений из "Программирование " При выполнении схемы можно каждый раз, когда выполняется действующий оператор, выписывать нормальную последовательность его комплекса. При этом после выполнения схемы будет получена некоторая последовательность формул. Выберем все состояния g[x) кортежа X, входящие в область задания схемы (обозначим их совокупность через О,), которые перерабатываются в состояния одного и того же кортежа У и приводят к получению одной и той же последовательности формул. Получаемая последовательность формул будет нормальной последовательностью с входным кортежем X и выходным кортежем У. Взятая вместе с О,, она представляет комплекс, который назовем реализацией схемы. [c.160] Реализация схемы описывает произведение значений действующих операторов в том порядке, в котором они выполнялись при выполнении схемы. [c.160] Область задания схемы представляет собой сумму непересекающихся множеств, являющихся областями задания ее реализаций. [c.160] Легко видеть, что множество реализаций схемы не более чем счетно. [c.160] Пусть схема 2 удовлетворяет тому условию, что, каков бы ни был стоящий в ее графике левый знак перехода, отвечающий ему правый знак перехода стоит в графике правее него. [c.160] Такую схему будем называть прямой. [c.160] Очевидно, множество реализаций прямой схемы конечно. [c.160] Выражением будем называть конечную строку термов, в которой для каждого натурального числа г имеется не больше одного правого знака перехода с этим индексом, и терм, содержащ,ий // , может присутствовать только на первом месте. В дальнейшем, если это специально не оговорено, считаем, что выражение не содержит оператора И . [c.161] Содержательно выражения следует рассматривать как куски графиков схем. [c.161] Термы являются наиболее простыми выражениями и потому называются элементарными выражениями. [c.161] Символом Л обозначим пустое выражение. Считается, что пустое выражение присутствует после любого элементарного выражения графика схемы. Для того чтобы отметить вхождение в график схемы 2, на определенных местах выражений 1 ,. .., будем писать 2 1 ,, 1 ,. .., W . Агрегат, который получится при замене в последней схеме выражений 1 , , 1 ,. .., соответственно выражениями ТГ, . .., будем обозначать 2 1 , 1 ,. .. [c.161] Два выражения 1 , и называются равносильными, если, коль скоро 2 1 , — схема, то 1) 2 тоже схема и 2) эти схемы равносильны. Для обозначения равносильности выражений будем применять знак равенства. [c.161] Если некоторое изменение схемы 2 приводит к получению новой схемы 2, такой, что 2 = 2, то будем говорить, что схему 2 можно подвергнуть упомянутому изменению, а это изменение будем называть равносильным преобразованием. [c.161] Равносильность выражений обладает свойствами симметрии, рефлексивности и транзитивности, однако иногда замена формулы = формулой 1 2= ТГ, требует некоторых оговорок, которые в дальнейшем приводятся лишь в случаях, когда они не являются совершенно очевидными. [c.161] Вернуться к основной статье