Семантика языка логики предикатов

Моделью А языка L первого порядка называется пара, состоящая из множества А, называемого универсумом, и функции , сопоставляющей

· каждому символу константы c Î L некоторый элемент ;

· каждому символу n-арной операции f из L функцию ;

· каждому предикатному символу R из L отношение .

Символ «=» интерпретируется как логический символ, такой, что .

Пример 1

Пусть L = {R} состоит из одного предикатного символа, и пусть #(R) = 2. Модель языка L задаётся как пара A = (A, r), состоящая из множества А и отношения , равного . Такую модель можно представить как ориентированный граф, вершинами которого являются элементы из А, а рёбрами – пары (a, b) Î r. Произвольное множество с отношением порядка будет моделью этого языка, если положить .

Пример 2

Полугруппой называется множество А вместе с бинарной операцией , удовлетворяющей закону ассоциативности a×(b×c) = (a×b)×c, для всех a, b, c Î A. Полугруппа вместе с элементом e Î A, удовлетворяющим для всех a Î A соотношениям
e×a = a×e = a, называется моноидом. Моноид, в котором для каждого a Î A задан такой элемент , что , называется группой. Язык теории полугрупп
L = {×} состоит из одного элемента, #(×) = 2. Язык теории моноидов состоит из символов бинарной операции и константы. Язык теории групп состоит из символов бинарной и унарной операций и из символа константы. Множество действительных чисел R вместе с аддитивными операциями (R, +, -x, 0) будет моделью языка теории групп. Символы интерпретируются следующим образом:

.

Моделью языка теории групп будет также множество положительных действительных чисел с мультипликативными операциями ). Множество натуральных чисел w можно рассматривать как линейно упорядоченный моноид, если определить язык теории линейно упорядоченных моноидов как L = {+, 0, £}.

Модели языка теории групп могут не удовлетворять закону ассоциативности и другим формулам, определяющим группу. Наша задача – дать формальное определение истинности предложений q в модели А языка первого порядка. Будем записывать выполнение формулы q в модели А, как А |= q. Например:

(R, +, 0) |= "x $y (x×y = e)

будет верно, поскольку для каждого a Î R существует такой b Î R, что a + b = 0.

Обычно не для всякого элемента модели существует символ константы, обозначающий этот элемент. Предположим, однако, что для каждого a Î A существует такой символ константы в языке L, что . Интерпретацию операций можно расширить на термы, не содержащие переменных, с помощью преобразования:

.

Каждому терму t без переменных будет соответствовать элемент . Определим отношение |= («удовлетворяет формуле») по индукции:

1) A |= R , если

2) A |= Øq, если и только если утверждение A |= q ложно;

3) A |= (q Ú y), если и только если A |= q или A |= y;

4) A |= $ x q(x), если и только если существует такой b Î A, что A |= q ().

Определим теперь A |= q для произвольных языка L и модели А этого языка. Пусть , где – символы констант. Обозначим через модель языка , полученную из модели A сопоставлением каждому элемента a.

Заметим, что поскольку " x q(x) равносильно Ø$ x (Øq(x)), то A |= "xq(x) тогда и только тогда, когда для всех b Î A верно A |= q ().

Если q – предложение языка L, то положим: A |= q, если и только если |= q.

Пример 3

Пусть L = {×, e, R} – язык теории частично упорядоченных моноидов. Рассмотрим модель N = (w, +, 0, £). Справедливость утверждения:

(w, +, 0, £) |=

равносильна выполнению стоящего в правой части равенства предложения для модели языка . Предложение означает, что для любых
p, q, r Î w верно , интерпретируемое как .

Замечание. Альфред Тарский был первым, ясно осознавшим необходимость определения истинности предложения для модели. Он предложил следующий метод, отличный от рассматриваемого нами.

Пусть А – модель языка первого порядка L. Рассмотрим произвольную функцию . Будем называть её А- оценкой и представлять в виде бесконечной последовательности , i-й член которой является значением переменной , даваемой оценкой b. Определяется оценка b(t) для каждого терма:

1) если t есть переменная , то ;

2) если t есть константа с, то ;

3) если t есть n­-арная операция, то .

Выполнение формулы q в модели А при оценке b записывается как A |= q[b] и определяется по индукции:

1) A |= , если и только если ();

2) A |= Øq [b], если и только если A |= q[b] ложно;

3) A |= (q Ú y)[b], если и только если A |= q[b] или A |= q[y].

4) A |= $ q()[b], если и только если q выполнена хотя бы на одной последовательности , отличной от b не более чем в одной i-й компоненте

Наконец, модель А называется удовлетворяющей формуле q, если A |= q[b] для всякой оценки b.

Возвращаясь к нашему первоначальному определению, отметим следующее утверждение, доказательство которого ясное, но громоздкое:

Пусть – языки первого порядка. Для любой модели А языка обозначим через множество А, рассматриваемое как модель языка . Тогда для любого предложения q языка утверждение A |= q истинно, если и только если |= q.