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

UptoLike

ВУЗ: 

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

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

Рубрика: 

Математическая Логика и Теория Алгоритмов стр. 31 из 64
© 2003 Галуев Геннадий Анатольевич
Пусть
{
}
,...1
,...,
n
AAA = - эрбрановский базис множества
S
.
H
- интерпретацию
I
удобно представлять в виде множества
{}
,...,...,,
21 n
mmmI = , где
i
m есть или
i
A или
j
A
для
...,2,1
=
i
.
Смысл этого множества в том, что если
i
m есть
i
A , то элементарной формуле
i
A присвоено значение 1, в противном случае – 0
Интерпретацию множества дизъюнктов
S
не обязательно задавать над эрбра-
новским универсиумом. Пусть, например
{}
),(,(),( ayfyQxPS = .
Тогда возможна следующая интерпретация
I
над областью
{}
2,1=D
:
1)2(;0)1(
;0)2,2(;0)2,1(;1)1,2(;1)1,1(
;2)2,2(2)2,1(2)1,2(;1)1,1(;2
==
====
=
=
===
PP
QQQQ
ffffa
Можно определить
H
-интерпретацию
*
I
, соответствующую любой интерпрета-
ции
I
.
Для рассмотренного выше примера эрбрановский базис
S - таков
{}
...)),,(),,((),),,(()),,(,(),,((),,(),( aafaafQaaafQaafaQaafPaaQaPA =
Оценим теперь каждый член
A , используя заданную интерпретацию
I
:
...
0)2,2()),(),,((
0)2,2()),,((
0)2,2())2,2(,2()),(,(
1)2())2,2(()),((
0)2,2(),(
1)2()(
==
==
===
===
==
==
QaafaafQ
QaaafQ
QfQaafaQ
PfPaafP
QaaQ
PaP
Следовательно,
H
- интерпретация
*
I
, соответствующая
I
есть
{}
),...),,(()),,(,()),,((),,(),(
*
aaafQaafaQaafPaaQaPI ⎤⎤⎤= .
О
О
п
п
р
р
е
е
д
д
е
е
л
л
е
е
н
н
и
и
е
е
.
.
Пусть
I
- интерпретация на области D .
H
- интерпретацией
*
I
, со-
ответствующей
I
, является интерпретация, которая удовлетворяет следующим усло-
виям:
Пусть
n
hh ,...,
1
- элементы эрбрановского универсума
H
. Пусть каждый
i
h отобра-
жается в некоторый
i
d в D . Если )...,,(
1 n
ddp получает в интерпретации
I
значение
1(0), то
),....,(
1 n
hhP также получает значение 1(0) в
*
I
.
Очевидно, справедлива следующая лемма.
Лемма 1. Если интерпретация
I
на некоторой области
D
удовлетворяет множе-
ству (является моделью множества) дизъюнктов
S , то любая из −
H
интерпретаций
*
I
, соответствующих
I
, также удовлетворяет S .
Т
Т
е
е
о
о
р
р
е
е
м
м
а
а (
о
о
н
н
е
е
в
в
ы
ы
п
п
о
о
л
л
н
н
и
и
м
м
о
о
с
с
т
т
и
и
м
м
н
н
о
о
ж
ж
е
е
с
с
т
т
в
в
а
а
д
д
и
и
з
з
ъ
ъ
ю
ю
н
н
к
к
т
т
о
о
в
в) Множество дизъюнк-
тов
S
выполнимо тогда и только тогда, когда
S
ложно при всех
H
- интерпретациях в
H
.
Доказательство.
Необходимость.
По определению множество дизъюнктов
S
невыполнимо тогда и
только тогда, когда
S
ложно при всех интерпретациях на любой области, следова-
тельно, и при
H
- интерпретациях на области
H
.
Достаточность
. Предположим, что S ложно при всех
H
- интепретациях. Поло-
жим, что
S выполнимо (имеется некоторая интерпретация
I
, являющаяся моделью S )
. Пусть
*
I
это
H
- интерпретация, соответствующая
I
. Тогда согласно доказанной вы-
ше лемме множество
S истинно в интерпретации
*
I
. Это противоречит нашему пред-

Страницы