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

UptoLike

ВУЗ: 

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

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

Рубрика: 

Математическая Логика и Теория Алгоритмов стр. 24 из 64
© 2003 Галуев Геннадий Анатольевич
Если терм t есть предметная переменная ,
i
x то ;)(
*
bitS = если терм t есть пред-
метная константа, то
)(* tS совпадает с интерпретацией этой константы в D ; если
n
f функциональная буква, интерпретируемая операцией ,
g
и
n
tt ,...,
1
термы, то
))(*),...,(*()),...,((*
11 nn
n
j
tStSgttfS = .
Таким образом,
*S
- функция, определяемая последовательностью
S
и интер-
претацией I и отображающая множество всех термов в
D . Иными словами, для любой
последовательности
,...),(
21
bbS = и для любого терма t величина )(* tS есть элемент
множества
D , который получается в результате подстановки при каждом
i
элемента
i
b на места всех вхождений переменной
i
x в терм t и затем выполнения всех операций
интерпретации, соответствующих функциональным буквам терма
t .
Например, если
t есть )),(,(
1
daDcS и
,...),(
21
bbS
=
, областью интерпретации слу-
жит множество действительных чисел,
1
S интерпретируется как сложение, а D - как
умножение, то
)(* tS представляет число
413
*bbb
+
(в предположении, что переменные
dcba ,,, упорядочены по алфавиту).
Так как все логические операции могут быть выполнены через базис
,,→⎤ а
кванторы
x
∃ и
x∀
связаны соотношением
x
∃
x∀
есть ))(( xAx
¬
∀¬ ,
то можно дать следующее индуктивное определение того, что формула
A вы-
полнена на последовательности
,...),(
21
bbS = из
∞
D при данной интерпретации I:
o
•
1 Если
A
есть элементарная формула
),...,(
1 n
n
j
ttA
и
n
j
B
есть соответствующее ей отображение в интерпретации, то фор-
мула
A
считается выполненной на последовательности S в том и только в том случае,
когда
1))(*),...,(*(
1
=
n
n
j
tStSB .
o
•
2 Формула
A⎤
выполнена на
S
тогда и только тогда, когда формула A не
выполнена на
S .
o
•
3
BA →
выполнена на
S
тогда и только тогда, когда A не выполнена на
S или когда формула
B
выполнена на S .
o
•
4 Формула Ax
i
∀ выполнена на S тогда и только тогда, когда формула
A
вы-
полнена на любой последовательности из
∞
D , отличающейся от
S
не более чем своей
i компонентой.
Таким образом, формула
A выполнена на последовательности ,...),(
21
bbS = тогда
и только тогда, когда подстановка при каждом
i символа, представляющего
i
b , на
места всех свободных вхождений
i
x в
A
приводит к истинному в данной интерпрета-
ции I предложению.
Формула
A называется истинной (в данной интерпретации) тогда и только то-
гда, когда она выполнена на всякой последовательности из
∞
D .
Формула
A
называется ложной (в данной интерпретации) если она не выполне-
на ни на одной последовательности из
∞
D .
Данная интерпретация называется моделью для данного множества формул Г,
если каждая формула из Г истинная в данной интерпретации.
Формула
A называется логически общезначимой (в исчислении предикатов),
если она истинна в каждой интерпретации.
Формула
A называется выполнимой (в исчислении предикатов), если существу-
ет интерпретация, в которой
A выполнима (в смысле введенного выше определения)
хотя бы на одной последовательности из
∞
D .

Страницы