АкушерствоАнатомияАнестезиологияВакцинопрофилактикаВалеологияВетеринарияГигиенаЗаболеванияИммунологияКардиологияНеврологияНефрологияОнкологияОториноларингологияОфтальмологияПаразитологияПедиатрияПервая помощьПсихиатрияПульмонологияРеанимацияРевматологияСтоматологияТерапияТоксикологияТравматологияУрологияФармакологияФармацевтикаФизиотерапияФтизиатрияХирургияЭндокринологияЭпидемиология

Семантические деревья

На дерево будем смотреть, как на корневое ориентированное дерево. Изображать дерево будем растущим вниз, ориентацию дуг указывать не будем. Напомним, что листом дерева называется вершина, из которой не выходит не одна дуга. Путь в дереве – это последовательность дуг e₁,e₂,…,e_k,… такая, что если дуга e_i заходит в вершину v, то дуга e_i+1 выходит из этой вершины. Путь в дереве называется максимальным, если к нему нельзя добавить ни одной дуги. Для каждой вершины существует единственный путь от корня к этой вершине. Если вершина является листом, то этот путь максимален. Если p – путь в дереве, то через I(p) будем обозначать объединение всех литералов, принадлежащим дугам пути. В случае, когда p – путь от корня до вершины v, то вместо I(p) будем писать I(v). Мы будем использовать понятие поддерева несколько в ином смысле, нежели в теории графов. А именно, поддеревом дерева Т будем называть подграф T′, удовлетворяющий следующим условиям:

1) T′ – дерево;

2) T′ содержит корень дерева Т,

3) если из v в v′ идет дуга в дереве T, v и v′Î T′, то T′ содержит все вершины, в которые из v идет дуга.

Определение. Пусть S – множество дизъюнктов, B – эрбрановский базис для S. Семантическим деревом для S называется корневое дерево, каждой дуге которого приписано непустое множество формул из B или их отрицаний так, что выполнены следующие условия.

1. Из любой вершины выходит конечное число дуг e1,…,ek; если ci – конъюнкция литералов, приписанных дуге ei, то c1Úc2Ú…Úck – тождественно истинная формула.

2. Для любой вершины v множество I(v) не содержит противоположных литералов.

Рассмотрим примеры. Пусть S – множество дизъюнктов из примера 2 предыдущего параграфа, B – его эрбрановский базис. Напомним, что B{P(a), Q(a), R(a)}. Для простоты в примерах вместо P(a), Q(a) и R(a) будем писать просто P,Q,R. На рисунках 4.4 и 4.5 приведены примеры семантических деревьев для S. Семантическое дерево может быть бесконечным. На рисунке 4.6 приведен пример семантического дерева для множества дизъюнктов S из примера 1 §4. Напомним, что эрбрановский базис в этом случае есть B{P(a), Q(a), P(f(a)), Q(f(a)),…}.

Рис. 4.4

Рис. 4.5

Определение. Пусть B – эрбрановский базис множества дизъюнктов S. Семантическое дерево Т называется полным, если для любого элемента А базиса B множество I(p) содержит либо А, либо ØА.

Семантические деревья, изображенные на рис.4.4 и 4.6 являютя полными, а семантическое дерево изображенное на рис.4.5 – неполным.

Определение. Вершина v семантического дерева называется опровергающей, если I(v) опровергает основной пример некоторого дизъюнкта S. Вершина v называется максимальной опровергающей, если вершина v′, предшествующая v, опровергающей не является.

Рассмотрим в качестве примера дерево, изображенное на рис.4.5. Напомним, что оно является семантическим деревом множества дизъюнктов S={P(x), Q(x)ÚØR(y)}. Вершины v₁ и v₃ будут опровергающими вершинами, так как множество I(v₁), равное {ØQ(a)&R(a), P(a)}, опровергает основной пример Q(a)ÚØR(a) дизъюнкта Q(x)ÚØR(y), а множество I(v₃), равное {R(a),ØP(a)&ØQ(a)} опровергает основной пример P(a) дизъюнкта P(x). Вершина v₁ будет максимальной опровергающей, а вершина v₃ не будет максимальной, потому что опровергающей является предшествующая ей вершина v₄. Вершина v₂ опровергающей не является.

Определение. Вершина v семантического дерева называется выводящей, если все непосредственно следующие за ней вершины являются максимальными опровергающими.

Дата добавления: 2015-09-27 | Просмотры: 624 | Нарушение авторских прав