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

 

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

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

а) для любой переменной х из базиса В и для любой СИ 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.

Конфигурация	Метка	Значения
		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 ⁽²⁾(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) Операторы располагаются непосредственно за своими операндами.

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

 

---

Дата добавления: 2015-12-20; просмотров: 20; Мы поможем в написании вашей работы!

Поделиться с друзьями:

---

---

Мы поможем в написании ваших работ!