Свободные интерпретации

Множество всех интерпретаций очень велико и поэтому вводится класс свободных интерпретаций (СИ), который образует ядро класса всех интерпретаций в том смысле, что справедливость высказываний о семантических свойствах ССП достаточно продемонстрировать для программ, получаемых только с помощью СИ.

Все СИ базиса В имеют одну и ту же область интерпретации, которая совпадает со множеством Т всех термов базиса В. Все СИ одинаково интерпретируют переменные и функциональные символы, а именно:

а) для любой переменной х из базиса В и для любой СИ I_h этого базиса I_h(x) = x;

б) для любой константы a из базиса ВI_h(a) = a;

в) для любого функционального символа f ⁽ⁿ⁾ из базиса В, I_h(f ⁽ⁿ⁾) = F⁽ⁿ⁾: Tⁿ T, где F⁽ⁿ⁾ - словарная функция такая, что F⁽ⁿ⁾(t₁, t₂, ..., t_n) = f ⁽ⁿ⁾ (t₁, t₂, ..., t_n), n ³ 1, т. е. функция F⁽ⁿ⁾ по термам t₁, t₂, ..., t_n из Т строит новый терм, используя функциональный смысл символа f⁽ⁿ⁾.

Интерпретация предикатных символов полностью свободна,т.е. разные СИ различаются лишь интерпретаций предикатных символов.

Таким образом, после введения СИ термы используются в двух разных качествах, как функциональные выражения в схемах и как значения переменных и выражений. В дальнейшем термы-значения будем заключать в апострофы. Например, если где t₁=`f(x,a)` - терм-значение переменной x, а где t₂ = `g(y)` - терм-значение переменной y, то значение свободно интерпретированного терма t₃=f(x, h(y)) равно терму-значению `f(f(x,a), h(g(y)))`.

Пример 1.1. Пусть I_h -СИ базиса, в котором определена схема S₁ (рисунок 1.3, а), и в этой интерпретации предикат Р = I_h(р) задан так: P(t) = 1, если число функциональных символов в t больше двух; P(t) = 0, в противном случае.

Тогда ПВП (S₁,I_h) можно представить таблицей 1.3.

Табл. 1.3.

Обратим внимание на следующую особенность термов. Если из терма удалить все скобки и запятые, то получим слово (назовем его бесскобочным термом), по которому можно однозначно восстановить первоначальный вид терма (при условии, что отмечена или известна местность функциональных символов). Например, терму g⁽²⁾(h⁽¹⁾(x), g⁽²⁾(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) Операторы располагаются непосредственно за своими операндами.

Бесскобочная запись термов короче и она будет использоваться далее наряду с обычной записью.