6.9. ПОСТРОЕНИЕ СЕМАНТИЧЕСКОГО ДЕРЕВА

Семантическое дерево представляет собой бинарное дерево, простирающееся вниз от корневой вершины. В соответствии со способом, который мы выбрали для приписывания значений истинности атомам эрбрановской базы, мы будем спускаться по этому дереву по определенному пути. Если мы присвоим атому значение Г, то окажемся непосредственно под корневой вершиной слева, а если то справа. Далее, независимо от того, в какой из двух вершин, расположенных непосредственно под корневой вершиной, мы оказались, если мы присвоим атому значение Т, то пойдем из нее по левой ветви, а если то по правой. Этот процесс продолжается до тех пор, пока каждому элементу эрбрановской базы не будет присвоено значение истинности. Очевидно, что в случае бесконечной эрбрановской базы любой полной интерпретации будет соответствовать бесконечный путь вниз по вершинам этого дерева. Полное дерево, содержащее все возможные пути, представляет все возможные интерпретации предложений из отсюда и название: семантическое дерево.

В качестве примера рассмотрим неудовлетворимое множество предложений

Универсумом Эрбрана будет здесь конечное множество

Эрбрановская база также конечна. Ее можно упорядочить так:

Семантическое дерево для этого множества предложений конечно, оно показано на рис. 6.1. Каждое ребро, соединяющее вершину с одной из ее дочерних вершин, представляет решение, принятое относительно значения истинности одного из атомов эрбрановской базы. Условились записывать рядом с ребром, где атому присваивается значение Г, сам этот атом, а рядом с ребром, где атому присваивается значение — его отрицание. Каждый из путей, ведущих от корневой вершины к концевой вершине этого дерева (а именно к вершине, расположенной внизу этого дерева), дает одну из интерпретаций для множества Эту интерпретацию можно однозначно представить в

Рис. 6.1. (см. скан) Семантическое дерево для множества предложений

виде множества атомов, встречающихся на этом пути. Так, интерпретация, получающаяся при прослеживании пути от корневой вершины к концевой вершине, отмеченной на рис. 6.1 цифрой 1, задается множеством

Такое множество называют моделью для данного множества предложений.

Говорят, что модель не удовлетворяет предложению, если существует константный частный случай этого предложения (построенный на термах универсума Эрбрана), имеющий значение F при означиваниях, определяемых этой моделью. Так, не удовлетворяет ни одному из предложений Аналогично не удовлетворяет предложению так как константный частный случай имеет значение

Если в есть предложение, не удовлетворяющееся интерпретацией, или моделью, то эта модель не может удовлетворить Так, не удовлетворяют множеству нашего примера, более того, можно исключить по очереди каждую из 16 возможных интерпретаций и сделать рывод, что множество 5 нашего примера неудовлетворимо.