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

UptoLike

ВУЗ: 

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

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

Рубрика: 

Математическая Логика и Теория Алгоритмов стр. 32 из 64
© 2003 Галуев Геннадий Анатольевич
положению, что S ложно при всех
H
- интерпретациях. Следовательно S должно быть
невыполнимо, что и требовалось доказать.
Таким образом, на основании этой теоремы, для установления невыполнимости
множества дизъюнктов достаточно рассмотреть лишь
H
- интерпретации над эрбра-
новским универсиумом.
Далее мы и будем рассматривать только
H
- интепретации.
Прежде чем переходить к теореме Эрбрана, устанавливающей условия невыпол-
нимости множества дизъюнктов, требуется ввести понятие семантического дерева.
Дерево это граф (т.е. объект, задаваемый упорядоченной парой <
u
x
, >, где
x
-
множество вершин;
u - множество ребер, соединяющих вершины их
x
, причем каж-
дое ребро, направленное от (выходящих из) вершины
i
x к вершине (входящее в вер-
шину)
j
x
, можно задать парой <
ji
xx ,
> не содержащий циклов и имеющий только од-
ну корневую вершину куда не заходит ни одно ребро.
О
1
x
=
1
u <
21
, xx >
2
x О О
3
x
=
2
u <
31
, xx >
О О О О О
=
3
u <
42
, xx >
4
x
5
x
6
x
7
x
8
x .
.
.
О
О
п
п
р
р
е
е
д
д
е
е
л
л
е
е
н
н
и
и
е
е
.
. Пусть
S - множество дизъюнктов и
A
его эрбраноский базис. Се-
мантическое дерево для
S есть растущее вниз дерево (в соответствии с введенным
определением дерева), в котором каждому ребру приписано конечное множество
элементарных формул из
A или их отрицаний таким образом, что:
1. Из каждого угла (вершины)
N
выходит конечное число ребер
N
LL ...,,
1
.
Пусть
Q i- конъюнкция всех литер, приписанных ....,,1 niL
i
= Тогда
n
VQVVQQ ...
21
- общезначимая формула.
2. Пусть для каждого узла
)(NIN
есть объединение всех множеств, припи-
санных ребрам ветви, входящей к узлу
N от корневой вершины. Тогда
)(NI не содержит контрарных пар (Если A -элементарная формула, то го-
ворят, что две литеры
A и
A
¬
контрарны друг другу, а множество
{}
AA ⎤, называют контрарной парой)
О
О
п
п
р
р
е
е
д
д
е
е
л
л
е
е
н
н
и
и
е
е
.
. Пусть
{}
...,...,
1 N
AAA = - эрбрановский базис множества S . Говорит,
что семантическое дерево для
S
будет полным тогда и только тогда для каждого i и
каждого конечного узла
N
семантического дерева (т.е. для узла, из которого не вы-
ходит никаких ребер)
)(NI содержит либо
i
A , либо
i
A⎤ .
Рассмотрим примеры семантических деревьев.
Пусть
{}
RQPA ,,= - эрбрановский базис множества S . Тогда, например, каждое
из указанных деревьев есть полное семантическое дерево для
S .

Страницы