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

UptoLike

ВУЗ: 

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

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

Рубрика: 

Математическая Логика и Теория Алгоритмов стр. 30 из 64
© 2003 Галуев Геннадий Анатольевич
Покажем теперь, что удаление кванторов существования сохраняет противоре-
чивость формулы:
Т
Т
е
е
о
о
р
р
е
е
м
м
а
а
I
I. Пусть
S
множество дизъюнкторов, которые представляют стандарт-
ную форму (скулемовскую) формулы
A
. Тогда
A
противоречива тогда и только тогда,
когда
S противоречиво.
Следует отметить, что согласно
т
т
е
е
о
о
р
р
е
е
м
м
е
е
I
I, стандартная форма
S формы A экви-
валентна
A , если A противоречива.
Если
A
противоречива, то не обязательно AS
↔
.
По определению множество дизъюнкторов невыполнимо (противоречиво) тогда и
только тогда, когда оно ложно при всех интерпретациях на всех областях. Все облас-
ти, из-за их бесконечного числа, перебрать разумеется невозможно. Однако сущест-
вует одна специальная область,
H
, такая, что S невыполнимо тогда и только тогда,
когда
S
ложно при всех интерпретациях на этой области. Эту область
H
называют эр-
бановским универсумом множества
S
и определяют следующим образом.
О
О
п
п
р
р
е
е
д
д
е
е
л
л
е
е
н
н
и
и
е
е
.
. Пусть
0
H - множество констант, встречающихся в
S
. Если никакая
константа не встречается в
S
, то
0
H состоит из одной константы, скажем
{
}
aH =
0
. Для
,....2,1,0=i пусть
1+i
H есть объединение
i
H и множества всех термов вида
)...,,(
1 n
n
ttf
при всех n для всех функций
n
f , встречающихся в S , где )...,1( njt
j
= при-
надлежит
i
H . Тогда
i
H называется множеством констант i - го уровня для S , а
∞H называется эрбрановским универсумом.
Очевидно, что если
S не содержит функциональных букв, то
∞
H
есть множество
констант из
S .
Например:
Пусть
{}
)()(),( xQxPaPS ∨⎤= , тогда
{
}
aHHH
=
=
=
=
∞
...
10
.
Пусть
{}
))(()(),( xfPxPaPS ∨⎤= , тогда
{
}
aH
=
0
,
{
}
)(,
1
afaH
=
,
{}
))((),(,
2
affafaH = ,
…
{}
.)...))),..((...((...,)),((),(, affffaffafaH =∞ .
О
О
п
п
р
р
е
е
д
д
е
е
л
л
е
е
н
н
и
и
е
е
.
. Пусть
S - множество дизъюнктов. Тогда множество элементарных
формул вида
),...,(
1 n
n
ttP для всех предикатов
n
P
, встречающихся в S , где
n
tt ...,
1
- эле-
менты эрбрановского универсума, называется эрбрановским базисом
S .
Поясним смысл термина предикат. Возьмем высказывание (выражаемое предло-
жением): «Сократ есть человек». Часть этого высказывания «есть человек» называ-
ется предикатом или сказуемым. «Сократ» же субъект т.е. подлежащее. Если читать
«Х есть человек», имея в виду математическое понятие переменной, то предикат –
сказуемое высттупает в роли пропозиционной функции. Каждому значению незави
-
симой переменной Х эта функция ставит в соответствие некоторое высказывания, ко-
торое может быть истинным или ложным. В исчислении предикатов предикатом назы-
вают всякую пропозиционную функцию
),...,(
1 n
xxP с любым числом 0≥n независимых
переменных.
Продолжим теперь наше изложение.
О
О
п
п
р
р
е
е
д
д
е
е
л
л
е
е
н
н
и
и
е
е
.
. Основной пример дизъюнкта
C из множества дизъюнктов S есть
дизъюнкт, полученный заменой переменных в
C на члены эрбрановского универсума.
Дадим теперь определение
H
- интерпретации.
О
О
п
п
р
р
е
е
д
д
е
е
л
л
е
е
н
н
и
и
е
е
.
. Пусть
S - множество дизъюнктов,
H
- эрбрановский универсум S ,
I
- интерпретация S над
H
. Говорят, что
I
есть
H
- интерпретация множества S , или
она удовлетворяет следующим условиям.
1. I отображает все константы из
S в самих себя;
2. Пусть
f есть n - местный функциональный символ и
n
hh ...,
1
- элементы
H
; в I
через
f обозначается функция, которая отображает
n
n
Hhh ∈),...,(
1
в
Hhhf
n
∈)...,(
1
.

Страницы