Глава 3

§ 23. Предикаты и кванторы

 

 

   В предыдущих параграфах мы видели, как алгебра логики по­зволяет нам записывать высказывания в виде формул и делать выводы. Однако с помощью алгебры логики невозможно доказать некоторые довольно простые утверждения. Рассмотрим такие высказывания:

«Все люди смертны».

«Сократ — человек».

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

   В начале этой главы было сказано, что утверждение «В городе N живёт более 2 миллионов человек» нельзя считать логическим высказыванием, поскольку непонятно, о каком городе идёт речь. В этом предложении содержится некоторое утверждение, завися­щее от N; если вместо N подставить название города, можно бу­дет определить, истинно оно или ложно. Такое утверждение, за­висящее от переменной, называют логической функцией или предикатом.

   Предикат (от лат. praedicatum — заявленное, упомянутое, сказанное) — это утверждение, содержащее переменные.

   Предикаты часто обозначаются буквой Р, например:

   P(N) = «В городе N живёт более 2 миллионов человек».

   Если мы задаём конкретные значения переменных, предикат превращается в логическое высказывание. Например, для преди­ката P(N) мы получим истинное высказывание для

N= «Москва» и ложное — для N = «Якутск».

   Предикат, зависящий от одной переменной, — это свойство объекта. Например, только что рассмотренный предикат P(N) характеризует свойство города. Вот ещё примеры предикатов-свойств:

Простое(х) = «х — простое число»;

Студент(х) = «х — студент»;

Спит(х) = «х всегда спит на уроке».

 

   Предикаты могут зависеть от нескольких переменных, напри­мер:

Больше(х,у)= «х больше у»;

Живёт(х,у) = «х живёт в городе у»;

 Любит(х,у) = «х любит у».

   Это предикаты-отношения, они определяют связь между дву­мя объектами.

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

Кванторы широко применяются в математике. Например, для натуральных п справедлива запись:

 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).

Аналогично можно показать, что хР(х) = хР(х).

   Где можно использовать язык предикатов? Самая подходящая для этого область информатики — системы искусственного интел­лекта, в которых моделируется человеческое мышление. В таких системах часто применяется язык логического программирования Пролог, в котором программа представляет собой набор данных и правила вывода новых результатов из этих данных.