Множество - терм
Cтраница 2
Предположим, что для Q существуют два эквивалентных запроса Q0 и Q 0 с минимальным числом термов и каждый из них не имеет каких-либо неиспользуемых квантифицированных переменных. Тогда по теореме 6.1 существуют свертки / ug запроса Q0 в Q6 и Q 0B Q0 соответственно. Тогда gf является сверткой Q0 в себя, которая отображает множество термов Qn в собственное подмножество этих термов. [16]
Примером интерпретационной эквивалентности является функциональная эквивалентность стандартных схем: схемы S и S2 эквивалентны, если для любой интерпретации / программы ] ( /) и 52 ( 7) вычисляют одну и ту же функцию. Функциональная эквивалентность стандартных схем алгоритмически неразрешима. Понятие формальной эквивалентности не использует интерпретацию: со схемой связывается ее детерминант - нек-рое множество термов, производное от множества всех путей в управляющем графе от начала к концу; схемы с равными детерминантами объявляются эквивалентными. [18]
Так, для автомата конечного внешней средой обычно является множество входных слов, а поведением - словарная функция, реализуемая автоматом, или событие ( иногда сверхсобытие), представимое автоматом. Для автомата над термами ( см. Автоматов алгебраическая теория) внешней средой является множество константных термов, а поведением - класс тех термов, значения к-рых, вычисляемые с помощью данного автомата, принадлежат выделенному подмножеству элементов соответствующей алгебры. Для мозаичных структур внешней средой является множество начальных конфигураций, а поведением - последовательности конфигураций, возникающих в тактовые моменты времени. [19]
Если бы в роли предложения В - оказалось г - ф - г, то FJ I не было бы локально выполнимым, поскольку оно содержало бы г - ф - г в качестве невыполнимого конечного подмножества. Итак, г г не может быть ни одним из Bf, а потому г г обязано быть одним из них, и, значит, г - г.) Поэтому отношение - рефлексивно на множестве термов. Тогда все предложения г s, s t vi гф1 окажутся в множестве Гт 1 при т, большем чем i, j и k, так что Гт 1 не будет локально выполнимым. Bj для некоторого j есть s г, так что s - г.) Таким образом, мы убедились, что - есть отношение эквивалентности на множестве термов. Всякий терм t, следовательно, принадлежит единственному классу эквивалентности [ t ] отношения -, классу, каждый элемент которого находится в отношении - с любым другим его элементом и который содержит всякий терм, находящийся в отношении - с каким-либо из элементов этого класса. [20]
Пусть X - - индексированное семейство множеств, элементы которого называются переменными. Множество элементов этой алгебры составляют термы, использующие данные переменные. И в этой алгебре все термы по-прежнему связываются с определенными основами, а знаками операций по-прежнему являются конструкторы выражений. Однако в алгебре слов на множестве переменных X множество базисных термов сигнатуры расширено множеством термов с переменными. [21]
Пусть X - - индексированное семейство множеств, элементы которого называются переменными. Множество элементов этой алгебры составляют термы, использующие данные переменные. И в этой алгебре все термы по-прежнему связываются с определенными основами, а знаками операций по-прежнему являются конструкторы выражений. Однако в алгебре слов на множестве переменных X множество базисных термов сигнатуры расширено множеством термов с переменными. [22]
Если бы в роли предложения В - оказалось г - ф - г, то FJ I не было бы локально выполнимым, поскольку оно содержало бы г - ф - г в качестве невыполнимого конечного подмножества. Итак, г г не может быть ни одним из Bf, а потому г г обязано быть одним из них, и, значит, г - г.) Поэтому отношение - рефлексивно на множестве термов. Тогда все предложения г s, s t vi гф1 окажутся в множестве Гт 1 при т, большем чем i, j и k, так что Гт 1 не будет локально выполнимым. Bj для некоторого j есть s г, так что s - г.) Таким образом, мы убедились, что - есть отношение эквивалентности на множестве термов. Всякий терм t, следовательно, принадлежит единственному классу эквивалентности [ t ] отношения -, классу, каждый элемент которого находится в отношении - с любым другим его элементом и который содержит всякий терм, находящийся в отношении - с каким-либо из элементов этого класса. [23]
Страницы: 1 2