Дискретно-непрерывная математика (стр. 9 )

Язык логики предикатов содержит скобки, символы логики высказываний кванторы предметные

(индивидные) переменные предметные

(индивидные) константы предикатные буквы

и функциональные буквыВерхний

индекс предикатной или функциональной буквы указывает число аргументов, а нижний индекс служит для различения букв с одним и тем же числом аргументов. В приведенном выше примере s является предметной константой, а М и D — одноместными предикатными буквами. Функциональные буквы обозначают предметные функции, аргументами и значениями которых являются индивиды, например, «+», «возраст» и т. д.

(a) всякая предметная переменная или предметная константа есть терм;

(b) если fni— функциональная буква и t1, ..., tn — термы, то

есть терм;

(c) выражение является термом только в том случае, если это следует из правил (а) и (b).

Предикатные буквы, примененные к термам, порождают элементарные формулы, или точнее: если Рni- предикатная буква, a

t1, ..., tn — термы, то— элементарная формула.

Формулы исчисления предикатов определяются следующим образом:

(a) всякая элементарная формула есть формула;

(b) если А и В — формулы и х - предметная переменная, то каждое из выражений и есть формула;

(c) выражение является формулой только в том случае, если это следует из правил (а) и (b).

Заметим, что можно не включать в число основных символов для квантора существования, так как можно определить как сокращенную запись для Также мы знаем, что посредством можно определить связки

В выражении называется областью действия

кванторапо переменной х. Заметим, что А может и не содержать переменной х, в таком случае обычно считается, что содержательный смысл А и одинаков.

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

Переменная называется свободной (связанной) переменной в данной формуле, если существуют свободные (связанные) ее вхождения в эту формулу. Таким образом, переменная может быть одновременно свободной и связанной в одной и то же формуле.

Терм t называется свободным для переменной хi в формуле А, если никакое свободное вхождение хi в А не лежит в области действия никакого кванторагде xj - переменная, входящая в t.

1.6.2. Интерпретация и аксиоматизация

Формулы имеют смысл только тогда, когда имеется какая-нибудь интерпретация входящих в нее символов. Сформулируем наиболее распространенную, теоретико-множественную семантику опи­санного выше языка логики предикатов первого порядка.

Под интерпретацией понимается всякая система, состоящая из непустого множества D, называемого областью интерпретации, и какого-либо соответствия, относящего каждой предикатной букве Рnj некоторое n-местное отношение в D, каждой функциональной букве fni - некоторую n-местную операцию в D (т. е. функцию, отображающую Dn в D) и каждой предметной постоянной аi — некоторый элемент из D.

( Всякое «-местное отношение в D может рассматриваться как некоторое подмножество множества Dn всех п-ок элементов из D. Например, если D есть множество людей, то отношение между двумя людьми, состоящее в том, что первый из них приходится отцом другому, можно отождествить с множеством всех упорядоченных пар (людей) (x, у) таких, что х является отцом у. )

При заданной интерпретации предметные переменные пробегают область D этой интерпретации, а связкам и кванторам придается их обычный смысл.

Для данной интерпретации всякая формула без свободных переменных (или, иначе, замкнутая формула) представляет собой высказывание, которое истинно или ложно, а всякая формула со свободными переменными выражает некоторое отношение на области интерпретации; это отношение может быть выполнено (истинно) для одних значений переменных из области интерпретации и не выполнено (ложно) для других.

Например, если мы берем в качестве области D множество целых положительных чисел и интерпретируем Р21 (у, Z) как у ≤ z, то представляет свойство (т. е. отношение с одним

аргументом) «для каждого целого положительного у, у ≤ z», которое выполнено только для числа 1.

Как отмечает Э. Мендельсон, понятия выполнимости и истинности интуитивно ясны, но, следуя [Tarski 1936], они могут быть уточнены следующим образом. Пусть дана некоторая интерпретация с областью D, и пусть ∑ есть множество всех счетных последовательностей элементов из D. Определим, что значит, что формула A выполнена на последовательности s = (b1, b2, ...) из ∑ при данной интерпретации.

Предварительно определим одноместную функцию s* со значениями из D и определенную на множестве всех термов.

(1) Если терм t есть предметная переменная хi, то

(2) Если терм t есть предметная константа, то s (t) совпадает с интерпретацией этой константы в D.

(3) Если fni есть функциональная буква, интерпретируемая операцией g в D, и t1, ..., tn — термы, то

Таким образом, s*— это функция, определяемая последовательностью s и отображающая множество всех термов в D. Если говорить неформально, то для любой последовательности s = (b1, b2, ...) и для любого терма t, s*(f) есть элемент множества D, который получается в результате подстановки при каждом i элемента bi на места всех вхождений переменной хi, в терм t и затем выполнения всех операций интерпретации, соответствующих функциональным буквам терма t.

Теперь, следуя индуктивным шагам определения формулы, перейдем к основному определению.

(i) Если А есть элементарная формула и

Qnj есть соответствующее ей отношение в интерпретации, то формула А считается выполненной на последовательности s в том и только в том случае, когдато есть если n-ка

(s*(t1), ..., s*(tn)) принадлежит отношению Qnj.

(ii) Формула выполнена на s т. т.т., когда формула А не выполнена s.

(iii) Формула выполнена на s т. т.т., когда формула А

не выполнена s или когда формула В выполнена на s.

(iv) Формула выполнена на s т. т.т., когда формула А выполнена на любой последовательности из ∑. отличающейся от s не более чем своей i-ой компонентой.

Иначе говоря, формула А выполнена на последовательности

s = (b1\, b2, ...) из ∑ т. т.т., когда подстановка при каждом i символа, представляющего bi, на места всех свободных вхождений хi в А приводит к истинному в данной интерпретации высказыванию.