Формулы имеют смысл только тогда, когда имеется какая-нибудь интерпретация входящих в нее символов.
Определение. Под интерпретацией мы будем понимать всякую пару, состоящую из непустого множества M, называемого областью интерпретации, и какого-либо отображения, относящему каждому предикатному символу арности n некоторое n-местное отношение на M. При заданной интерпретации предметные переменные мыслятся пробегающими область M этой интерпретации, а связкам и кванторам придается их обычный смысл.
Для данной интерпретации всякая формула без свободных переменных представляет собой высказывание, которое истинно или ложно, а всякая формула со свободными переменными выражает некоторое отношение на области интерпретации; это отношение может быть выполнено (истинно) для одних значений переменных из области интерпретации и не выполнено (ложно) для других.
Дадим индуктивное определение значения формулы (в данной интерпретации).
Значение формулы F на n-ке <a1, a2,…, an>, aiÎM, своих свободных переменных <x1, x2, …, xn> будем обозначать F|<a1, a2,…, an>.
Формула F есть атомарная переменная A(x1, x2, …, xn), где x1, x2, …, xn - свободные переменные, тогда F|<a1, a2,…, an> есть значение n-местного предиката, сопоставленного предикатному символу A, при соответствующем замещении его переменных элементами a1, a2,…, an.
Формула F имеет вид ØA. Пусть A|<a1, a2,…, an>=e, тогда F|<a1, a2,…, an> =Øe.
Формула F имеет вид AÚB, A&B, AÉB или A~B. Пусть A|<a1, a2,…, an>=a, B|<a1, a2,…, an>=b, тогда F|<a1, a2,…, an> равно соответственно aÚb, a&b, aÉb, a~b.
Формула F имеет вид "x A. Если x1, x2, …, xn - все свободные переменные формулы F, то x, x1, x2, …, xn - все свободные переменные формулы A. Значение "x A|<a1, a2,…, an> = И тогда и только тогда, когда для любого aÎM имеем A|<a, a1, a2,…, an> = И.
Формула F имеет вид $x A. Если x1, x2, …, xn - все свободные переменные формулы F, то x, x1, x2, …, xn - все свободные переменные формулы A. Значение $x A|<a1, a2,…, an> = И тогда и только тогда, когда существует такое aÎM, что A|<a, a1, a2,…, an> = И.
Пример 4.4. Рассмотрим три формулы:
1) A(x, y);
2) "y A(x,y);
3) $x "y A(x,y).
Возьмем в качестве области интерпретации множество целых положительных чисел и интерпретируем A(x, y) как x£y. Тогда первая формула - это предикат x£y, который принимает значение И для всех пар a, b целых положительных чисел таких, что a £ b. Вторая формула выражает свойство: "для каждого целого положительного числа y x£y", которое выполняется только при x=1. Наконец, третья формула - это истинное высказывание о существовании наименьшего целого положительного числа. Если бы в качестве области интерпретации мы рассматривали множество целых чисел, то третья формула была бы ложным высказыванием.
Пример 4.5. Пусть задана следующая интерпретация. M - множество натуральных чисел (0, 1, 2,…), предикатные символы S(x,y,z) и P(x,y,z) обозначают следующие предикаты "x + y = z" и "x ´ y = z" соответственно.
Запишем формулы, истинные на M тогда и только тогда, когда выполнены следующие условия:
1) x = 0;
2) x = 1;
3) x - четное число;
4) x - простое число;
5) x = y;
6) x £ y;
7) x делит y;
8) коммутативность сложения.
Ответы:
1) F1(x) = "y S(x, y, y), так как x+y=y для любого y тогда и только тогда, когда x = 0;
2) F2(x) = "y P(x, y , y);
3) F3(x) = $y S(y, y, x);
4) F4(x) = ØF1(x)&ØF2(x)&("y "z (P(y, z, x) É (F2(y)ÚF2(z)))), где F1, F2 - формулы, определенные в пп. 1 и 2;
5) F5(x, y) = "z "u (S(x, z, u) É S(y, z, u));
6) F6(x,y) = $z S(x, z, y);
7) F7(x,y) = $z P(x, z, y);
8) "x "y "z (S(x, y, z) É S(y, x, z).
Пример 4.6. Пусть f(x) - произвольная фиксированная функция, заданная на отрезке [a, b].
1. Рассмотрим интерпретацию: M - множество действительных чисел, P(x,d) обозначает |x-x0|<d, Q(x, e) обозначает |f(x) - A|<e, R(e) обозначает e>0. Здесь x0 -фиксированный элемент отрезка [a,b]; A - некоторое фиксированное действительное число. Тогда утверждение о том, что A - предел функции f(x) при x®x0, записывается формулой
"e $d "x ((R(e)&P(x, d))É Q(x, e)).
2. Рассмотрим интерпретацию: M - множество действительных чисел, P(x,d) обозначает |x-x0|<d, S(x, e) обозначает |f(x) - f(x0)|<e, R(e) обозначает e>0. Здесь x0 -фиксированный элемент отрезка [a,b]. Тогда утверждение о том, что функция f - непрерывна в точке x0 записывается в виде формулы
"e $d "x ((R(e)&P(x, d))É S(x, e)).
3. Рассмотрим интерпретацию: M - множество действительных чисел, P(x,x1,d) обозначает |x-x1|<d, S(x, x1, e) обозначает |f(x) - f(x1)|<e, R(e) обозначает e>0, D(x) обозначает xÎ[a,b]. Тогда утверждение о том, что функция f - непрерывна на отрезке [a,b] записывается в виде формулы
"x1 "e $d "x ((D(x1)&R(e)&P(x, x1, d))É S(x, x1, e)).