§ 8. Формулы логики предикатов

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

• Предметные переменные: ;

• Нульместные предикатные переменные: ;

• n-местные (n≥1) предикатные переменные: с указанием числа свободных мест в них;

• Символы логических связок: ;

• Кванторы: ;

• Вспомогательные символы: открывающая и закрывающая скобки, запятая.

Определение формулы логики предикатов (по индукции)

1. Каждая нульместная предикатная переменная есть формула.

2. Если - n-местная предикатная переменная, то– формула, в которой все предметные переменныесвободны.

3. Если F – формула, то - тоже формула. Свободные (связанные) предметные переменные в формулете и только те, которые являются свободными (связанными) вF.

Характер предметных переменных при переходе от формулы  F  к      не меняется.

4. Если - формулы, и если предметные переменные, входящие одновременно в эти формулы, свободны в любых из них, то выражения

также являются формулами.

5. Если F – доказуемая формула и x – предметная переменная, входящая в F свободно, то выражения итакже являются формулами, в которых переменнаяx связанная, а все остальные переменные – предметные, входящие в формулу F свободно или связанно, остаются и в новых формулах такими же соответственно.

6. Никаких других формул логики предикатов нет.

Определение. Формулы, определенные в пунктах 1-2, называются элементарными (атомарными). Формулы, не являющиеся элементарными, называются составными.

Пример. - элементарные формулы.

На основании пунктов 1, 3, 4 всякая формула алгебры высказываний будет также и формулой логики предикатов.

Определение. Формулы, в которых нет свободных предметных переменных, называются замкнутыми. Формулы, содержащие свободные предметные переменные – открытыми.

Примеры замкнутых формул: ,

§ 9. Классификация формул логики предикатов

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

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

Пример. Дадим интерпретацию формуле .

В качестве множества M возьмем множество всех мужчин, а вместо предикатной переменной подставим конкретный предикат, определенный наM: «x есть брат y». Тогда исходная формула превратится в следующее высказывание

(«x есть брат y») –«у каждого мужчины есть брат». Высказывание, очевидно, ложное.