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

Если Р={Р₁…Р_n} – множество высказываний, то семантическое дерево – это бинарное дерево, удовлетворяющее следующим условиям:

1) каждая дуга помечена негативной или позитивной литерой из множества Р;

2) литеры, которыми помечены две дуги, выходящие из одного узла, должны быть противоположны;

3) никакая ветвь (путь) на дереве не содержит более одного вхождения каждой литеры;

4) никакая ветвь не содержит пары противоположных литер.

Например, для множества литер P={p, q} семантическое дерево имеет вид:

 

 

А для множества литер P={p, q, r} семантическое дерево имеет вид:

 

 

Каждому узлу N семантического дерева соответствует функция I_n, которая сопоставляет истинностное значение некоторым элементам из множества Р и называется частичной интерпретацией. Частичная интерпретация I_n сопоставляет значение Т или F высказыванию р, если некоторая дуга из корня N помечена р или (┐p). Частичная интерпретация не определена для высказывания р, если р и (┐p) не встречается на пути из корня в N.

Семантическое дерево полное, если каждый его лист соответствует некоторой всюду определенной интерпретации. Для того чтобы определить, выполнима ли формула А, с помощью алгоритма полного перебора требуется просмотреть полное семантическое дерево, соответствующее высказываниям, встречающимся в формуле А. Формула выполнима, если хотя бы для одного листа А получается значение Т. Этот алгоритм не эффективен, т. к. требуется просматривать 2ⁿ интерпретаций.