Элементы математической логики. Фролов И.С. - 61 стр.

UptoLike

ВУЗ: 

СГАУ | Самара

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

Рубрика: 

Пример 3. В формуле ∀xP (x, y)∧∀yQ(y, z) переменная x связана,
переменная y одновременно свободна и связана, переменная z свободна.
Будем считать, что любая переменная, содержащаяся в терме,
свободна в этом терме, и любое ее вхождение в терм свободно.
Выражением называется терм или формула. Для выражений бу-
дем использовать обозначение E или E(x
1
, . . . , x
n
), где x
1
, . . . , x
n
—
переменные, входящие в выражение. Выражение, не содержащее пе-
ременных, называется осн´овным выражением. Выражение, не содер-
жащее свободных переменных, называется замкнутым выражением.
Замкнутая формула называется предложением.
Терм t называется свободным для переменной x
i
в выражении E,
если никакое свободное вхождение x
i
в E не лежит в области действия
∀x
j
или ∃x
j
, где x
j
— переменная, входящая в t.
Пример 4. Терм f(z) свободен для переменной y в формуле
∀x(P (x, y) ⇒ Q(x, z)), а терм f(x) не свободен для y.
Если термы t
1
, . . . , t
n
свободны для переменных x
1
, . . . , x
n
соответ-
ственно в выражении E, то правомерна подстановка термов t
i
вместо
x
i
(1 6 i 6 n) в выражении E, результат которой будем обозначать
E(t
1
/x
1
, . . . , t
n
/x
n
) или E(t
1
, . . . , t
n
), если ясно, вместо каких перемен-
ных подставляются термы t
1
, . . . , t
n
.
Упражнение 1. Докажите следующие утверждения:
1) всякий терм свободен для любой переменной в любом терме;
2) всякий основный терм свободен для любой переменной в любой формуле;
3) терм t свободен для любой переменной в формуле F , если никакая пере-
менная терма t не является связанной в F ;
4) переменная x свободна для x в любой формуле;
5) всякий терм свободен для переменной x в формуле F , если F не содержит
свободных вхождений x.
2. Интерпретация формул
Выражения, т.е. термы и формулы в логике первого порядка име-
ют смысл только тогда, когда задана интерпретация входящих в них
символов.
Определение 4. Интерпретация I в логике первого порядка со-
стоит из непустого множества (предметной области) D и отображения
оценки, которое будем обозначать |·|
I
и которое ставит в соответствие:
1) каждой константе a — некоторый элемент |a|
I
из D;
2) каждому n-арному функциональному символу f — некото-
рую n-арную функцию (операцию) |f|
I
из D
n
в D;
3) каждому n-арному предикатному символу P — некоторый
n-арный предикат (отношение) |P |
I
на D
n
.
60

Страницы