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

Существует человек, который любит всех людей» (рис. 17).

Существует человек, который кого-то любит» (рис. 16).

Все люди любят всех людей» (рис. 15).

4.

5.

6.

- «для всякого человека существует человек, который его любит» или «каждого человека кто-то любит» (рис. 18).

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

2.4.5. Численные кванторы

В математике часто встречаются выражения вида «по меньшей мере n» («хотя бы n»), «не более чем n», «n и только n», где n – натуральное число.

Эти выражения, называемые численными кванторами, имеют чисто логический смысл; они могут быть заменены равнозначными выражениями, не содержащими числительных и состоящими только из логических терминов и знака =, обозначающего тождество (совпадение) объектов.

Пусть n = 1.

Предложение «По меньшей мере один объект обладает свойством Р» имеет тот же смысл, что и предложение «Существует объект, обладающий свойством Р», т.е.

$х (Р(х)). (1)

Предложение «Не более чем один объект обладает свойством Р» равнозначно предложению «Если есть объекты, обладающие свойством Р, то они совпадают», т.е.

"х "у ((Р(х) Ù Р(у)) ® х = у). (2)

Предложение «Один и только один объект обладает свойсвом Р» равнозначно конъюнкции предложений (1) и (2), т.е.

$х (Р(х)) Ù "х "у ((Р(х) Ù Р(у)) ® х = у).

Рассмотрим случай n = 2.

Предложение «По меньшей мере два объекта обладают свойством Р» означает то же, что и предложение «Существуют несовпадающие объекты, обладающие свойством Р», т.е.

$х $у (Р(х) Ù Р(у) Ù х ¹ у). (3)

Предложение «Не более чем два объекта обладают свойством Р» равнозначно предложению «Каковы бы ни были объекты x, y, z, если все они обладают свойством Р, то по меньшей мере два из них совпадают», т.е.

"х "у "z ((P(x) Ù P(y) Ù P(z)) ® (x = y Ú x = z Ú y = z)). (4)

Предложение «Два и только два объекта обладают свойством Р» совпадают по смыслу с конъюнкцией предложений (3) и (4).

Совершенно аналогично обстоит дело с численными кванторами при n > 2.

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

Зададим сначала алфавит символов, их которых будем составлять формулы:

• предметные переменные: х, у, z, x_i, y_i,z_i (i – натуральное число)$
• предикатные буквы: P, Q, R, …;
• символы операций – отрицания, конъюнкции, дизъюнкции, импликации, эквиваленции, суммы по модулю два;
• кванторы общности и существования;
• вспомогательные символы – скобки, запятая.

Определение.

1. Всякий нуль-местный предикатный символ – формула.
2. Всякий n–местный предикатный символ – формула.
3. Если F – формула, а x - предметная переменная, то "x(F) и $x(F) – формулы.
4. Если F₁ и F₂ – формулы, то - формулы.
5. Никаких других формул в логике предикатов нет.

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

Пример 62.

1. Р; Q(x, y, z); R(x₁, x₂) – элементарные формулы.
2. "х (Р(x, y, z); "x ($y (P(x, y, z))); - составные формулы.

Формула F в формулах вида "x(F) и $x(F) называется соответственно областью действия квантора "x или $x.

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

Определение. Переменная называется свободной в формуле, если хотя бы одно ее вхождение в этой формуле свободно.

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