Математическая логика и теория алгоритмов. Галуев Г.А. - 34 стр.

UptoLike

ВУЗ: 

ТТИ ЮФУ | Таганрог

Составители: 

Рубрика: 

Математическая Логика и Теория Алгоритмов стр. 34 из 64
© 2003 Галуев Геннадий Анатольевич
О
)(aP )(aP⎤
О О
)(aQ
)(aQ⎤
)(aQ
)(aQ⎤
О О О О
))(( afP⎤ ))(( afP
О О
Рис.6
Заметим, что для каждого узла
N в семантическом дереве для S )(NI есть под-
множество некоторой интерпретации для
S
. Поэтому )(NI будем называть частичной
интерпретацией для
S .
Если эрбрановский базис множества
S бесконечен, то и всякое полное семанти-
ческое дерево для него также будет бесконечно. Очевидно и ясно, что полное семан-
тическое дерево для
S соответствует полному перебору всех возможных интерпрета-
ций для
S .
Введем определения.
О
О
п
п
р
р
е
е
д
д
е
е
л
л
е
е
н
н
и
и
е
е
.
. Узел
N называется опровергающим, если )(NI опровергает некото-
рый основной пример дизъюнкта в
S (т.е. этот основной пример дизъюнкта имеет в
интерпретации
)(NI значение 0), но для любого предшествующего
N
узла
'
N )(
'
NI не
опровергает никакого основного примера дизъюнкта в
S .
О
О
п
п
р
р
е
е
д
д
е
е
л
л
е
е
н
н
и
и
е
е
.
. Говорит, что семантическое дерево закрыто, если и только если
каждая ветвь дерева оканчивается опровергающим узлом.
О
О
п
п
р
р
е
е
д
д
е
е
л
л
е
е
н
н
и
и
е
е
.
. Узел
N закрытого семантического дерева называется выводящим
узлом, если все непосредственно следующие за
N узлы являются опровергающими.
Например: Пусть
{}
PVRQPVRQVPS ⎤⎤⎤⎤= ,,, эрбрановский базис множества S есть
{}
RQPA ,,= . Полное семантическое дерево для S имеет вид а) (предыдущий пример),
а закрытое семантическое дерево для
S имеет вид
P
О P⎤
О О
Q Q⎤
О О
R
R⎤
О О
Рис. 7

Страницы