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

UptoLike

ВУЗ: 

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

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

Рубрика: 

Математическая Логика и Теория Алгоритмов стр. 23 из 64
© 2003 Галуев Геннадий Анатольевич
Если X не является свободной переменной формулу A(x), то результат опера-
ции подстановки A(t) есть само первоначальное выражение A(x).
Если требуется в некоторой формуле A одновременно произвести подстановку
вместо переменных
n
xx ,,
1
K соответственно термов
n
tt ,,
1
K , то исходную формулу бу-
дем обозначать
()
n
xxA ,,
1
K , а результат подстановки -
(
)
n
ttA ,,
1
K .
Будем говорить, что терм t свободен для переменной x в A(x), если никакое
свободное вхождение x в A(x) не входит в область действия какого-нибудь квантора
y∀ или
y
∃ , где y – переменная, входящая в терм t.
Будем говорить, что подстановка
t вместо
x
в )(xA свободна, если t свободен для
x
в
)(xA
.
Отметим, что :
А) всякий терм, не содержащий переменных, свободен для любой переменной в
любой формуле;
б) терм
t свободен для любой переменной в формуле A , если никакая перемен-
ная терма
t не является связанной переменной в
A
;
в)
i
x свободно для
i
x в любой формуле;
г) всякий терм свободен для
i
x в
A
не содержит свободных вхождений
i
x .
Лекция №5
Интерпретация формул в исчислении предикатов.
Выполнимость формул.
Аксиоматическое построение исчисления предикатов.
Предваренные нормальные формулы.
В исчислении высказываний интерпретация формул есть приписывание пропози-
ционным буквам, входящим в формулу, истинностных значений (истина, ложь). Для
определения интерпретации формулы исчисления предикатов нужно указать пред-
метную область (область значений предметных переменных) и значения констант,
функциональных и предикатных символов, встречающихся в формуле.
Дадим определение интерпретации
.
Под интерпретацией
будем понимать всякую систему, состоящую из непустого
множества
D , называемого областью интерпретации и какого-либо соответствия, от-
носящегося каждой предикатной букве
n
j
A некоторое отображение
n
D во множество
{1,0}, каждой функциональной букве
k
j
f некоторую функцию (отображение)
k
D в D и
каждой предметной константе
i
a - некоторый элемент D . При заданной интерпрета-
ции предметные переменные
1
x , …,
n
x , … мыслятся пробегающими область D этой
интерпретации, а логическим связкам
→,&,v
и т.д. и кванторам
∃∀,
придается их
обычный смысл.
Для данной интерпретации всякая формула без свободных переменных (замк-
нутая формула) представляет собой высказывание, которое имеет некоторое опреде-
ленное истинностное значение (истина или ложь). Всякая формула со свободными
переменными есть истинностная функция этих переменных, определенная на области
интерпретации; при этом для некоторых значений предметных переменных
n
xx,..., эта
функция принимает значение 1, а для других – 0.
Введем понятие выполнимости
и истинности формулы в исчислении предика-
тов.
Определим предварительно одноместную функцию
*
S со значениями из D и оп-
ределенную на множестве всех термов
t , если задана последовательность
,...),(
21
bbS = элементов из D и некоторая интерпретация I.

Страницы