Язык исчисления предикатов. Термы и формулы

Исчисление предикатов первого порядка

Исчисление предикатов первого порядка. 1

Понятие алгебраической системы.. 1

Язык исчисления предикатов. Термы и формулы.. 1

Интерпретации. Выполнимость, истинность, логическая общезначимость. 2

Аксиомы и правила вывода исчисления предикатов 1-го порядка. 5

Понятие теории 1-го порядка. 9

Теория 1-ого порядка с равенством.. 9

Приложение. Интерпретации и состояния. 12

Понятие алгебраической системы

Язык исчисления предикатов. Термы и формулы

Алфавит теории (ИП 1-ого порядка) включает следующие множества символов:

1) множество индивидных переменных;

2) множество индивидных констант;

3) множество функциональных символов;

4) множество предикатных символов;

5) множество логических символов, содержащее оба квантора и обозначения логических связок и обе логические константы (0 и 1);

6) множество вспомогательных символов: скобки и т. п.

Множества предполагаются счетными, причем множество есть дизъюнктное объединение множеств функциональных символов арности . При этом все символы из отождествляются с индивидными константами, т.е. . Аналогично , где - множество предикатных символов арности .

Замечание. Строго говоря, указанные множества нельзя считать алфавитами, так как алфавит должен быть конечным. Однако можно их элементы закодировать в виде слов в конечном алфавите. Конкретные способы такой кодировки мы не обсуждаем. Мы предполагаем также, что элементы множеств пронумерованы. Записывая , мы имеем в виду переменную с номером и т.д.

Чтобы определить понятие формулы в ИП, введем сначала понятие терма.

1) Каждая переменная из и каждая константа из есть терм.

2) Если слова суть термы, а , то слово есть терм.

3) Никаких других термов не существует.

Замечание. Часто используют упрощенные формы записи термов при или . В последнем случае как правило используют так называемую инфиксную форму записи: вместо пишут .

Формула ИП определяется так.

1) Всякое слово вида , где , а - термы, есть формула.

2) Если слово есть формула, то слова , где , суть формулы.

3) Если слова и суть формулы, то слова , ,

, , , , суть формулы.

4) Никаких других формул не существует.

Формулы, определенные согласно п. (1), называются атомарными.

Интерпретации. Выполнимость, истинность, логическая общезначимость[1]

Интерпретация считается заданной, если фиксирована алгебраическая система и пара отображений и , сопоставляющие каждому функциональному и предикатному символу операцию и предикат системы соответственно, причем каждому функциональному (предикатному) символу арности сопоставляется операция (предикат) той же арности . Множество называется областью интерпретации.

Пусть задана последовательность элементов множества . Определим понятие значения терма в интерпретации на последовательности . Будем использовать при этом обозначение , опуская, как правило, упоминание интерпретации .

Если , то , т.е. значение -ой переменной равно -ому члену последовательности. Таким образом, задание последовательности означает приписывание значений индивидным переменным так, что переменная получает значение .

Если для некоторого и некоторых термов , то . В частности, при .

Определим теперь понятие истинностного значения формулы в интерпретации на последовательности . Будем использовать при этом обозначение , опуская, как правило, упоминание интерпретации .

Для атомарной формулы по определению .

Далее:

;

.

И, наконец, истинностное значение тогда и только тогда, когда для любой последовательности , отличающейся от последовательности , быть может, только в -ом члене, имеет место равенство .

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

Формула называется выполнимой в интерпретации , если существует последовательность , для которой . Формула называется истинной в интерпретации , если для каждой последовательности имеет место . Формула называется логически общезначимой, если она истинна в каждой интерпретации.

Рассмотрим некоторые примеры логически общезначимых формул.

Утверждение 1. Всякая тавтология логически общезначима.

Доказательство. Тривиально.

Перед рассмотрением дальнейших примеров необходимо ввести некоторые определения.

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

Так в формуле первое вхождение переменной связанное, а второе свободное; первое вхождение переменной - свободное, а второе связанное. В формуле же все вхождения переменных связанные.

Введем теперь понятие терма, свободного для переменной формуле. Говорят, что терм свободен для переменной в формуле , если никакое свободное вхождение переменной в формулу не находится в области действия никакого квантора по переменной, входящей в терм.

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

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

Утверждение 2. Формула , при условии, что терм свободен для переменной в формуле , является логически общезначимой.

Доказательство. Зафиксируем произвольно интерпретацию и последовательность элементов области интерпретации. Достаточно тогда доказать, что при том, что . Действительно, последнее равенство означает, что для любой последовательности , отличающейся от разве лишь в -ом члене, . Но после замены свободных вхождений переменной термом , поскольку он свободен для в формуле , не возникает никаких новых связанных вхождений переменных[3]. Следовательно, может измениться лишь значение переменной , и тогда истинностное значение формулы останется таким же, как и истинностное значение формулы .

Утверждение 3. Если формула не содержит свободных вхождений переменной , то формула является логически общезначимой.

Доказательство аналогично доказательству утверждения 2.