Свободные интерпретации
Множество всех интерпретаций очень велико и поэтому вводится класс свободных интерпретаций (СИ), который образует ядро класса всех интерпретаций в том смысле, что справедливость высказываний о семантических свойствах ССП достаточно продемонстрировать для программ, получаемых только с помощью СИ.
Все СИ базиса В имеют одну и ту же область интерпретации, которая совпадает со множеством Т всех термов базиса В. Все СИ одинаково интерпретируют переменные и функциональные символы, а именно:
а) для любой переменной х из базиса В и для любой СИ Ih этого базиса Ih (x) = x;
б) для любой константы a из базиса ВIh (a) = a;
в) для любого функционального символа f (n) из базиса В, Ih (f (n)) = F (n): Tn T, где F (n) - словарная функция такая, что F (n)(t1, t2,..., tn) = f (n) (t1, t2,..., tn), n ³ 1, т. е. функция F (n) по термам t1, t2,..., tn из Т строит новый терм, используя функциональный смысл символа f (n).
Интерпретация предикатных символов полностью свободна, т.е. разные СИ различаются лишь интерпретаций предикатных символов.
Таким образом, после введения СИ термы используются в двух разных качествах, как функциональные выражения в схемах и как значения переменных и выражений. В дальнейшем термы-значения будем заключать в апострофы. Например, если где t1=` f (x,a)` - терм-значение переменной x, а где t2 = ` g (y)` - терм-значение переменной y, то значение свободно интерпретированного терма t3= f (x, h (y)) равно терму-значению ` f (f (x,a), h (g (y)))`.
|
|
Пример 1.1. Пусть Ih -СИ базиса, в котором определена схема S1 (рисунок 1.3, а), и в этой интерпретации предикат Р = Ih (р) задан так: P (t) = 1, если число функциональных символов в t больше двух; P (t) = 0, в противном случае.
Тогда ПВП (S1,Ih) можно представить таблицей 1.3.
Табл. 1.3.
Конфигурация | Метка | Значения | |
X | у | ||
U0 | `x` | `y` | |
U1 | `x` | `a` | |
U2 | `x` | `a` | |
U3 | `x` | ` g (x,a)` | |
U4 | ` h (x)` | ` g (x,a)` | |
U5 | ` h (x)` | ` g (x,a)` | |
U6 | ` h (x)` | ` g (h (x), g (x,a))` | |
U7 | ` h (h (x))` | ` g (h (x), g (x,a))` | |
U8 | ` h (h (x))` | ` g (h (x), g (x,a))` | |
U9 | ` h (h (x))` | ` g (h (h (x)), g (h (x), g (x,a)))` | |
U10 | ` h (h (h (x)))` | ` g (h (h (x)), g (h (x), g (x,a)))` | |
U11 | ` h (h (h (x)))` | ` g (h (h (x)), g (h (x), g (x,a)))` | |
U12 | ` h (h (h (x)))` | ` g (h (h (x)), g (h (x), g (x,a)))` |
Обратим внимание на следующую особенность термов. Если из терма удалить все скобки и запятые, то получим слово (назовем его бесскобочным термом), по которому можно однозначно восстановить первоначальный вид терма (при условии, что отмечена или известна местность функциональных символов). Например, терму g (2)(h (1)(x), g (2)(x,y)) соответствует бесскобочный терм ghxgxy. Правила восстановления терма по бесскобочной записи аналогичны правилам восстановления арифметических по их прямой польской записи, которая просто и точно указывает порядок выполнения операций.
|
|
В этой записи, впервые примененной польским логиком Я. Лукашевичем, операторы следуют непосредственно за операндами. Поэтому ее иногда называют постфиксной записью. Классическая форма записи, как мы обычно пишем, называется инфиксной. Например:
A*B => AB*; A* (B+C/D) => ABCD/+*;
A*B+C => AB*C +; A*B+C*D => AB*CD* +.
Правила представления в польской записи:
1) Идентификаторы следуют в том же порядке, что и в инфиксной записи;
2) Операторы следуют в том же порядке, в каком они должны вычисляться (слева направо);
3) Операторы располагаются непосредственно за своими операндами.
Бесскобочная запись термов короче и она будет использоваться далее наряду с обычной записью.
Дата добавления: 2015-12-20; просмотров: 20; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!