§ 23. Предикаты и кванторы
В предыдущих параграфах мы видели, как алгебра логики позволяет нам записывать высказывания в виде формул и делать выводы. Однако с помощью алгебры логики невозможно доказать некоторые довольно простые утверждения. Рассмотрим такие высказывания:
«Все люди смертны».
«Сократ — человек».
Каждый из нас понимает, что если оба эти высказывания истинны, то Сократ тоже смертен. Однако алгебра высказываний не позволяет это доказать. В таких случаях приходится использовать другой математический аппарат, с которым мы познакомимся в этом параграфе.
В начале этой главы было сказано, что утверждение «В городе N живёт более 2 миллионов человек» нельзя считать логическим высказыванием, поскольку непонятно, о каком городе идёт речь. В этом предложении содержится некоторое утверждение, зависящее от N; если вместо N подставить название города, можно будет определить, истинно оно или ложно. Такое утверждение, зависящее от переменной, называют логической функцией или предикатом.
Предикат (от лат. praedicatum — заявленное, упомянутое, сказанное) — это утверждение, содержащее переменные.
Предикаты часто обозначаются буквой Р, например:
P(N) = «В городе N живёт более 2 миллионов человек».
Если мы задаём конкретные значения переменных, предикат превращается в логическое высказывание. Например, для предиката P(N) мы получим истинное высказывание для
N= «Москва» и ложное — для N = «Якутск».
Предикат, зависящий от одной переменной, — это свойство объекта. Например, только что рассмотренный предикат P(N) характеризует свойство города. Вот ещё примеры предикатов-свойств:
Простое(х) = «х — простое число»;
Студент(х) = «х — студент»;
Спит(х) = «х всегда спит на уроке».
Предикаты могут зависеть от нескольких переменных, например:
Больше(х,у)= «х больше у»;
Живёт(х,у) = «х живёт в городе у»;
Любит(х,у) = «х любит у».
Это предикаты-отношения, они определяют связь между двумя объектами.
Предикаты нередко используются для того, чтобы задать множество, не перечисляя все его элементы. Так множество положительных чисел может быть задано предикатом, который принимает истинное значение для положительных чисел и ложное для остальных: Р(х)=(х> 0). Множество пар чисел, сумма которых равна 1, задается предикатом Р(х,у) = (х+у = 1), который зависит от двух переменных.
Существуют предикаты, которые справедливы (истинны) для всех допустимых значений переменных. Например, это предикат Р[х) = (х2 > 0), определённый на множестве всех вещественных чисел. В таком случае используют запись 
хР(х), это означает: «При любом х предикат Р(х) справедлив». Знак — это буква «А», повёрнутая «вверх ногами» (от англ. all — все); он обозначает любой», «всякий», «для любого», «для всех». Символ называют квантором всеобщности.
Квантор (от лат. quantum — сколько) — это знак или выражение, обозначающее количество.
Выражения «любой», «для всех» и т. п. также можно считать кванторами, они равносильны знаку .
Кванторы широко применяются в математике. Например, для натуральных п справедлива запись:
n: 1+2+…+n=(n(n+1))/2.
Часто используют ещё один квантор — квантор существования 
(зеркальное отражение буквы «Е», от англ. exist — существовать). Знак означает «существует», «хотя бы один». Например, если Р(х) = (х - 5> О), то можно записать хР(х), что означает «cуществует х, такой что х-5>0». Это уже высказывание, а не предикат, потому что можно установить его истинность. Высказывание хР(х) — истинно, так как существует х, удовлетворяющий данному условию, например х = 6. Запись хР(х) — это тоже высказывание, но оно ложно, потому что неравенство л:.-5>0 верно не для всех х.
Логическое выражение может включать несколько кванторов. Например, фразу «Для любого х существует у, такой что х + у = О» можно записать как х у(х + у -0). Это утверждение истинно (на множестве чисел), потому что для любого х существует -х, число с обратным знаком. Переставлять местами кванторы нельзя, это меняет смысл выражения. Например, высказывание у х(х + у =0) означает: «Существует такое значение у, что для любого х выполняется равенство х + у = 0», это ложное высказывание.
Теперь давайте вернёмся к Сократу, точнее, к двум высказываниям, приведённым в начале параграфа. Как записать утверждение «Все люди смертны»? Можно сказать иначе: «Для любого х верно: если х — человек, то х смертен». Вспоминаем, что связка «если..., то» записывается как импликация, а выражение «для любого х» — в виде квантора x, Поэтому получаем:
x(P(x)→Q(x)),
где Р(х) — «х — человек», Q(x)= «х - смертен». Так как утверждение Р(х)→Q(x) верно для любого х, оно также верно при подстановке х = Сократ:
Р(Сократ)→Q(Сократ) = 1.
Поскольку Сократ — человек, то Р(Сократ) = 1. Поэтому с помощью таблицы истинности для импликации мы находим, что Q(Сократ) = 1, т. е. «Сократ смертен».
Если построить отрицание для высказывания с квантором или , мы увидим, что один квантор заменяет другой. Например, отрицание высказывания хР(х) («Неверно, что для любого х выполняется Р{х)») можно сформулировать так: «Существует хотя бы один х, для которого не выполняется Р(х)» и может быть записано в виде хР(х). Здесь, как и раньше, черта сверху обозначает отрицание. Таким образом,
xP(x)=xP(x).
Аналогично можно показать, что хР(х) = хР(х).
Где можно использовать язык предикатов? Самая подходящая для этого область информатики — системы искусственного интеллекта, в которых моделируется человеческое мышление. В таких системах часто применяется язык логического программирования Пролог, в котором программа представляет собой набор данных и правила вывода новых результатов из этих данных.