Математическая логика и теория алгоритмов. Сергиевская И.М. - 33 стр.

UptoLike

ВУЗ: 

ПГУТИ | Самара

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

Рубрика: 

38
В формуле
()
jiij
xxAxx ,
)2(
∀∃ вхождения обеих переменных связаны.
Пусть
A
– формула,
i
x – переменная в формуле
A
,
t
– терм. Введем
обозначение
()
i
xA
. Тогда
()
tA – результат подстановки
t
вместо всех свободных
вхождений
i
x в формулу
A
.
Пример. Рассмотрим подстановку
t
вместо всех свободных вхождений
i
x в
формулы из предыдущего примера.
В формуле
()
ji
xxA ,
)2(
вхождение
i
x
свободное, следовательно, получаем
()
j
xtA ,
)2(
.
В формуле
()
(
)
(
)
ijii
xAxxAx
)1()2(
, →∀ вхождения переменной
i
x
в посылку
связаны, а вхождение в следствие свободно. Получаем:
()
(
)
(
)
tAxxAx
jii
)1()2(
, →∀ .
В формуле
()
jiij
xxAxx ,
)2(
∀∃ вхождения обеих переменных связаны, поэтому
осуществить подстановку
t
невозможно.
Определение.
Терм
t
называется свободным для переменной
i
x в формуле
A
тогда и только тогда, когда никакое свободное вхождение
i
x
в формулу
A
не лежит
в области действия квантора
j
x∀ , где
j
x – переменная в терме
t
.
Пример. Рассмотрим формулу
(
)
211
, xxAx
∀
и терм
()
21
)2(
, xxft = .
t
не
свободен для переменной
2
x в данной формуле, так как
2
x лежит в области действия
квантора, тем более
t
не свободен для переменной
1
x .
Пусть теперь дан терм
3
xt = .
t
свободен для переменной
2
x .
Уточним понятие интерпретации для множества формул
Γ
теории первого
порядка.
Определение. Интерпретацией множества формул
Γ
называется область
интерпретации
X
и заданное на ней соответствие, которое каждой предикатной
букве
)(n
k
A ставит в соответствие n -местный предикат на
X
, каждой
функциональной букве
)(n
k
f – n -местную функцию на
X
, каждой предметной
константе
i
a
– элемент множества
X
.
При интерпретации формулы превращаются в предикаты на множестве
X
.
Если формула не имеет свободных переменных, то после интерпретации она
превращается в высказывание.
         В формуле ∃x j ∀xi A( 2) (xi , x j ) вхождения обеих переменных связаны.

     Пусть A – формула, xi – переменная в формуле A , t – терм. Введем
обозначение A( xi ) . Тогда A(t ) – результат подстановки t вместо всех свободных
вхождений xi в формулу A .

     Пример. Рассмотрим подстановку t вместо всех свободных вхождений xi в
формулы из предыдущего примера.
     В формуле A( 2) (xi , x j ) вхождение xi свободное, следовательно, получаем
A( 2) (t , x j ).
                      (              )
         В формуле ∀xi A( 2) (xi , x j ) → A(1) ( xi ) вхождения переменной xi в посылку
                                                              (               )
связаны, а вхождение в следствие свободно. Получаем: ∀xi A ( 2) (xi , x j ) → A (1) (t ) .
     В формуле ∃x j ∀xi A( 2) (xi , x j ) вхождения обеих переменных связаны, поэтому
осуществить подстановку t невозможно.

      Определение. Терм t называется свободным для переменной xi в формуле A
тогда и только тогда, когда никакое свободное вхождение xi в формулу A не лежит
в области действия квантора ∀x j , где x j – переменная в терме t .

     Пример. Рассмотрим формулу ∀x1 A( x1 , x2 ) и терм t = f ( 2) ( x1 , x2 ) . t не
свободен для переменной x2 в данной формуле, так как x2 лежит в области действия
квантора, тем более t не свободен для переменной x1 .
     Пусть теперь дан терм t = x3 . t свободен для переменной x2 .

     Уточним понятие интерпретации для множества формул Γ теории первого
порядка.

     Определение. Интерпретацией множества формул Γ называется область
интерпретации X и заданное на ней соответствие, которое каждой предикатной
букве Ak(n )  ставит в соответствие n -местный предикат на X , каждой
функциональной букве f k(n ) – n -местную функцию на X , каждой предметной
константе ai – элемент множества X .

     При интерпретации формулы превращаются в предикаты на множестве X .
Если формула не имеет свободных переменных, то после интерпретации она
превращается в высказывание.




                                              38

Страницы