Определение семантического дерева

Пусть j - универсальное предложение и S={С₁,…,С_n} – соответствующее j множество дизъюнктов.

· Пусть P₁(),…,P_k() – атомы (предикаты), входящие в дизъюнкты множества S.

· H={a₁, a_2, … } – эрбрановский универсум для S.

Семантическим деревом для S называется дерево T со следующими свойствами:

1. Корнем T является произвольная точка.

2. Вершиной T является основной пример атома P_l(a_i, … , a_k) или его отрицание ØP_l(a_i, … , a_k)

3. Потомки.Каждая вершина имеет в точности двух потомков: P_l(a_i, … , a_k) и ØP_l(a_i, … , a_k)

4. Построение дерева. Дерево T строится, начиная от корня. К каждой вершине, не имеющей потомков, добавляется два новых узла, в которых размещается очередной основной пример атома P_l(a_i, … , a_k) и его отрицание ØP_l(a_i, … , a_k).

5. Ветвь, содержащая в вершинах основные примеры атомов или отрицаний атомов, трактуется как конъюнкция основных примеров атомов вершин.

6. Если вершина дерева сдержит основной пример атома P_l(a_i, … , a_k), то ни одна ветвь, проходящая через эту вершину, не может содержать узел ØP_l(a_i, … , a_k).

7. Противоречивая ветвь (a). Если в процессе построения дерева T получена вершина k (основной пример атома), которая противоречит какому-либо основному примеру одного из дизъюнктов С₁,…,С_n, тогда k является заключительной вершиной и текущая ветвь является противоречивой Ä.

8. Противоречивая ветвь (b). Если конъюнкция основных примеров атомов на некоторой ветви противоречит какому-либо основному примеру одного из дизъюнктов С₁,…,С_n, то текущая ветвь также является противоречивой Ä

9. Непротиворечивая ветвь.Каждой непротиворечивой ветви дерева T соответствует эрбрановская интерпретация, подтверждающая исходное множество дизъюнктов.

10. Все ветви противоречивы. Если для множества дизъюнктов S существует семантическое дерево T, все ветви которого противоречивы, то множество дизъюнктов S является противоречивым.

11. Трактовка дерева T. Совокупность всех ветвей дерева T трактуется как их дизъюнкция. Каждая ветвь содержит все основные примеры атомов или их отрицаний и трактуется как их конъюнкция. Таким образом, дерево T содержит все возможные сочетания основных примеров атомов и их отрицаний, и является общезначимой формулой.

Пример 1 (продолжение). Требуется проверить выполнимость следующего предложения:

j: ("x)[P(x) Ù (ØP(x) Ú Q(f(x))) Ù (ØQ(f(x))]

Соответствующее множество дизъюнктов имеет вид:

S={{P(x)},{ØP(x),Q(f(x))},{ØQ(f(x)}}

Эрбрановский универсум H:

H={a, f(a), f(f(a)), f(f(f(a))), …}

Основные примеры атомов [P(.), Q(f(.))]:

{P(a), P(f(a)), Q(f(a)), Q(f(f(a))), P(f(f(a))), Q(f(f(f(a)))), … }

Построение семантического дерева T

[P(a) Ù ØQ(f(a))] « Ø[ØP(a) Ú Q(f(a))]

Выводы. Все ветви дерева T противоречивы, следовательно, не существует эрбрановской интерпретации, подтверждающей множество дизъюнктов

S={{P(x)},{ØP(x),Q(f(x))},{ØQ(f(x)}}

Невыполнимое множество основных примеров дизъюнктов (в это множество включаются только те основные примеры дизъюнктов, которые были использованы для объявления некоторой ветви противоречивой) имеет вид:

S’={{P(a)}, {P(f(a))}, {ØQ(f(a))}, {ØP(a),Q(f(a))}}

т.е. следующая формула неподтверждаема:

P(a) Ù P(f(a)) Ù [ØQ(f(a))] Ù [ØP(a) Ú Q(f(a))]

Пример 2. Требуется проверить выполнимость следующего предложения:

j: ("x)("y) [ØP(x,y) Ú P(a,f(x,y))]

Соответствующее множество дизъюнктов имеет вид:

S={{ØP(x,y), P(a,f(x,y))}}

Эрбрановский универсум H:

H={a, f(a,a), f(a,f(a,a)), f(f(a,a),a), …}

Основные примеры атомов [P(.,.), P(a, f(.,.))]:

{P(a,a), P(a,f(a,a)), P(f(a,a),a), P(f(a,a), f(a,a)), … }

Построение семантического дерева T

Выводы. Левая крайняя ветвь содержит только основные примеры атомов, а правая – только их отрицания и являются непротиворечивыми. Каждой из этих ветвей соответствует эрбрановская интерпретация. Следовательно, исходное предложение является выполнимым.

Задание 6. Методом семантических таблиц требуется проверить выполнимость следующего предложения:

j: ("x)("z) [(ØP(x) Ú Q(f(x),x)) Ù P(g(b)) Ù ØQ(x,z)]

Здесь b – константа, f(), g() – функциональные символы, P(), Q() - предикаты. Если предложение j невыполнимо, нужно построить невыполнимое множество основных примеров дизъюнктов.