Дискретная математика:
логика, группы, графы, фракталы

Акимов О.Е.

1.5. Операции над предикатами и кванторами

О предикатах, кванторах и многоместных функциях

Предикат — это функциональное высказывание, а высказывание — предикатная константа. Логика предикатов — это расширение логики высказываний за счет использования предикатов в роли логических функций. Эти функции несколько отличаются от функций, которые мы использовали в логике Буля. Булева функция однородна, т.е. для нее область значений функции и область изменений аргументов по типу одна и та же — логическая (либо истина, либо ложь). Для предикатов же область значений функции — логическая, а область изменений аргументов — предметная. Таким образом, эта функция неоднородна. Приведем примеры предикатных функций. Пусть имеется ряд простых высказываний:

Р₁ = «Иван читает Достоевского»,
Р₂ = «Петр читает Достоевского»,
... ... ... ... ... ... ... ... ... ... ... ... ... ...,
Р_n = «Степан читает Достоевского».

Вместо высказываний Р₁, Р₂, ... , Р_n мы могли бы ввести одноместный предикат Р(х), для которого переменная х принимала бы значения из предметной области —

х = {Иван, Петр, ... , Степан},

а сама предикатная функция передавалась бы словами:

Р(х) = « х читает Достоевского».

Теперь изменим исходный ряд высказываний:

Р₁ = «Иван читает Достоевского»,
Р₂ = «Петр читает Толстого»,
... ... ... ... ... ... ... ... ... ... ... ...
Р_n = «Степан читает Чехова».

Здесь можно было бы ввести уже двухместный предикат — Р(х, у) = « х читает у », с дополнительной предметной областью —

у = {Достоевский, Толстой, ... , Чехов}.

Введем трехместный предикат Р(х, у, z), который означает, что « х есть сумма у и z ». Допустим, в процессе вычислений переменная х приняла конкретное значение, равное 5. Тогда трехместный предикат превратится в двухместный:

Р(5, у, z) = Р'(у, z) = « 5 есть сумма у и z ».

При х = 5 и у = 3 получим одноместный предикат:

Р(5, 3, z) = Р'(3, z) = Р''(z) = « 5 есть сумма 3 и z ».

Наконец, если добавить условие z = 2 , то исходный предикат становится нульместным предикатом (константой или высказыванием), который в данном случае принимает истинное значение:

Р₁ = Р(5, 3, 2) = « 5 есть сумма 3 и 2 » = 1.

Но могло быть, что z = 1, тогда имели бы ложное высказывание:

Р₀ = Р(5, 3, 1) = « 5 есть сумма 3 и 1 » = 0.

Таким образом, при замещении переменной х_i предметной постоянной a_i происходит превращение n-местного предиката Р(х₁ ... х_i ... х_n) в (n – 1)-местный — Р(х₁ ... a_i ... х_n). Приписав конкретные значения всем аргументам предикатной функции — Р(а₁ ... a_i ... a_n), мы тем самым получаем предикатную константу, к которой применимы все законы логики высказываний.

Функциональная природа предиката влечет за собой введение еще одного понятия — квантора. Роль его выясним на следующих двух примерах:

1) «Все люди смертны. Сократ человек.
Следовательно, Сократ смертен».

2) «Некоторые люди гениальны. Сократ человек.
Следовательно, Сократ гениален».

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

Итак, ключевыми словами в наших примерах являются «все» и «некоторые». Когда какое-нибудь правило распространяется на всех индивидуумов, оно, естественно, распространяется и на Сократа. Когда же правило касается только некоторых, оно может оказаться в отношении Сократа как раз и неверным.

Термин «все х» обозначается в логике предикатов ∀х и называется квантором общности (символ ∀ есть перевернутая буква А, которая является начальной буквой английского слова All — «все»). Термины «некоторые х» или «существует хотя бы одно значение х» обозначаются через ∃х и называются квантором существования (символ ∃ есть перевернутая буква Е, первая буква английского слова Exist — «существование»).

Выставляя кванторы перед предикатами, мы как бы усиливаем или ослабляем их действие. Так, выражение ∀х Р(х) означает: «для всех без исключения х свойство Р истинно», а выражение ∃х Р(х) означает: «существует по крайней мере одно значение х, для которого свойство Р истинно». Мы не будем использовать так называемые свободные переменные, т.е. не будем рассматривать предикатные функции, аргументы которых не связаны ни квантором общности, ни квантором существования. Сказать «для всех х свойство Р истинно» — это все равно, что сказать «конъюнкция всех значений предикатной функции равна единице»:

∀х Р(х) = P(a) ∧ P(b) ∧ P(c) ∧ ... = 1.

Квантор существования означает дизъюнкцию всех значений предикатной функции:

∃х Р(х) = P(a) ∨ P(b) ∨ P(c) ∨ ... .

Оба квантора можно отрицать и выражать один через другой на основе закона де Моргана:

∀х Р(х) = P(a) ∧ P(b) ∧ P(c) ∧ ... =
= P(a) ∨ P(b) ∨ P(c) ∨ ... = ∃х Р(х),

∃х Р(х) = P(a) ∨ P(b) ∨ P(c) ∨ ... =
= P(a) ∧ P(b) ∧ P(c) ∧ ... = ∀х Р(х).

Отсюда

∀ х Р(х) = ∃х Р(х),         ∃х Р(х) = ∀х Р(х).

Осмыслить формулы отрицания кванторов поможет следующий пример. Пусть предикат Р(х) означает, что «х является простым числом». Когда х будет пробегать ряд натуральных чисел —

х = {1, 2, 3, 4, 5, 6, ...},

предикатная функция пробежит ряд истинных и ложных значений:

Р(1) = 0, Р(2) = 1, Р(3) = 1, Р(4) = 0, Р(5) = 1, Р(6) = 0, Р(7) = 1, ...

Убедимся в справедливости первой формулы для отрицания квантора общности:

∀х Р(х) = «не все х простые числа» = «существуют такие х,
которые являются непростыми числами» = ∃х Р(х) = 1.

Оба эти высказывания истинны. Теперь убедимся в справедливости второй формулы для отрицания квантора существования:

∃х Р(х) = «нет ни одного х, которое было бы простым» =
= «все х являются непростыми числами» = ∀х Р(х) = 0.

Эти высказывания ложны.