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

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

1. Символы исчисления предикатов включают в себя: а) символы предметных переменных x ₁, x ₂,…, x_n, …; б) символы предметных констант a ₁, a ₂,…, a_n, …; в) символы или имена предикатов A , A ,… A , …; г) символы или имена функций f , f ,… f , …; д) знаки логических операций Ø, É; е) символы кванторов ", $; ж) скобки и запятую – (,),.

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

2. Понятие формулы исчисления предикатов определяется в два этапа [4].

1) Термы:

а) предметные переменные x ₁, x ₂,…, x_n,... и константы a ₁, a ₂,…, a_n, …;

б) если fⁿ – имя функции, а t ₁, t ₂,…, t_n – термы, то fⁿ (t ₁, t ₂,…, t_n) – тоже терм.

2) Формулы:

а) если Aⁿ – имя предиката, а t ₁, t ₂,…, t_n – термы, то Aⁿ (t ₁, t ₂,…, t_n) – формула; все вхождения переменных в формулу Aⁿ (t ₁, t ₂,…, t_n) являются свободными;

б) если A (x) – формула, содержащая свободное вхождение переменной x, то выражения с кванторами " xA (x), $ xA (x) – формулы;

в) если A и B – формулы, то Ø A, A É B – формулы, в которых свободные переменные формул A и B остаются свободными, а связанные переменные формул A и B остаются связанными.

Так же, как и в исчислении высказываний, можно ввести знаки других логических операций (&, Ú, ~), используя соответствующие равносильности.

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

Подстановка терма y в формулу A (x) называется правильной, если и только если:

а) y является предметной константой;

б) у является предметной переменной, и все вхождения y, полученные в результате подстановки, оказываются свободными в полученной в результате подстановки формуле. Например, в формулу " y (P (x, y) É Q (x)) вместо x можно подставить либо константу a: " y (P (a, y) É Q (a)), либо переменную z: " y (P (z, y) É Q (z)), но нельзя подставить переменную y, так как после подстановки получим формулу: " y (P (y, y) É Q (y)), в которой переменная y оказывается связанной.

3. Аксиомы исчисления предикатов.

А1. A É (B É A).

А2. (A É (B É C)) É ((A É B) É (A É C)).

А3. (Ø B É Ø A) É ((Ø B É Ø A) É B).

А4. " xA (x) É A (y), где формула A (x) не содержит переменной y.

А5. A (x) É $ yA (y), где формула A (x) не содержит переменной y.

4. Правил вывода в исчислении предикатов четыре:

П1 – modus ponens (m. p.) – правило заключения:

;

П2 – правило связывания квантором общности:

, где формула B не содержит переменной x;

П3– правило связывания квантором существования:

, где формула B не содержит переменной x;

П4 – правило переименования связанной переменной. Связанную переменную в формуле A можно заменить (в кванторе и во всех вхождениях в области действия квантора) другой переменной, не являющейся свободной в A. Например, для формулы " xF (x) É $ xG (x) применяя правило переименования, получим формулу " yF (y) É $ zG (z).

Для правил П2 и П3 условие, что формула B не содержит переменной x, является существенным. Это подтверждает следующий пример.

Пример 3.4.

Даны два предиката: B (x) = " x делится на 6"; A (x) = " x делится на 3".

Тогда B (x) É A (x) = "Если x делится на 6, то x делится на 3" = И для всех x.

Однако B (x) É " xA (x) = "Если x делится на 6, то все x делятся на 3" не всегда истинно. Таким образом, применение правила П2 неправомерно, если B зависит от x.

Если же к формуле B (x) É A (x) применить правило П3, то получим $ xB (x) É A (x). После применения правила П2 получим $ xB (x) É " xA (x) = "Если некоторые x делится на 6, то все x делятся на 3" = Л. Таким образом, применение правила П3 также неправомерно, если B зависит от x.

Для исчисления предикатов верны правила вывода 1 – 14 исчисления высказываний (раздел 3.2).

Дополнительные правила вывода для исчисления предикатов следующие:

1. Введение квантора общности: , где A (y) – результат правильной подстановки переменной y вместо x в A (x).

2. Удаление квантора общности: , где A (y) – результат правильной подстановки терма y вместо x в A (x).

3. Отрицание квантора общности: .

4. Введение квантора существования: , где A (y) – результат правильной подстановки терма y вместо x в A (x).

5. Удаление квантора существования: , где A (x) – результат правильной подстановки переменной x вместо y в A (y).

6. Отрицание квантора существования: .

Верна также теорема дедукции. Если Г – множество формул, A и B – формулы, и Г, A „ B. Тогда Г „ A É B.

Сформулируем без доказательства важные утверждения для исчисления предикатов

Теорема 3.1. Аксиомы исчисления предикатов – общезначимые формулы.

Теорема 3.2. Любая выводимая в исчислении предикатов формула является общезначимой.

Пример 3.5.

Обосновать правильность рассуждения, построив вывод.

а) Всякое нечетное натуральное число является разностью квадратов двух натуральных чисел. 5 – натуральное число. Следовательно, 5 – разность квадратов двух натуральных чисел

Пусть M – множество натуральных чисел. Введем предикаты:

A (x) = “ x – нечетное число”.

B (x) – “ x – разность квадратов двух чисел”.

Требуется построить вывод:

" x (A (x) É B (x)), A (5) ├ B (5).

Построим вывод.

(1) " x (A (x) É B (x)) – гипотеза;

(2) A (5) – гипотеза;

(3) A (5) É B (5) – из (1) и удаления ";

(4) B (5) – из (2) и (3) по m. p.

б) Все словари полезны. Все полезные книги высоко ценятся. Следовательно, все словари высоко ценятся.

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

A (x) = “ x – словарь”.

B (x) = “ x – полезен”.

C (x) = “ x высоко ценится”.

Требуется построить следующий вывод:

" x (A (x) É B (x)), " x (B (x) É C (x)) ├ " x (A (x) É C (x)).

Построим этот вывод.

(1) " x (A (x) É B (x)) – гипотеза;

(2) " x (B (x) É C (x)) - гипотеза;

(3) A (y) É B (y) – из (1) и удаления ";

(4) B (y) É C (y) – из (2) и удаления ";

(5) A (y) É C (y) – из (3) и (4) по правилу силлогизма;

(6) " x (A (x) É C (x)) – из (5) и введения ".

в) Всякий совершеннолетний человек, находящийся в здравом уме, допускается к голосованию. Джон не допущен к голосованию. Значит, он либо несовершеннолетний, либо не находится в здравом уме.

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

A (x) = “ x – совершеннолетний”.

B (x) = “ x находится в здравом уме”.

C (x) = “ x допущен к голосованию”.

Введем константу d, обозначающую имя "Джон".

Требуется построить следующий вывод:

" x (A (x)& B (x) É C (x)), Ø C (d)) ├ Ø A (d) Ú Ø B (d).

Построим этот вывод.

(1) " x (A (x)& B (x) É C (x)) - гипотеза;

(2) Ø C (d)) - гипотеза;

(3) A (d)& B (d) É C (d) - из (1) и удаления ";

(4) Ø C (d)) É Ø(A (d)& B (d)) – из (3) и правила контрапозиции;

(5) Ø C (d)) É Ø A (d) Ú Ø B (d) – из (4) и отрицания конъюнкции;

(7) Ø A (d) Ú Ø B (d) – из (2) и (5) по m. p.

(8)