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

Понятие предиката

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

Утверждения делаются об определенных объектах; множество таких объектов называют предметной областью, а отношения, которые устанавливаются между n объектами – n-местным предикатом:

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

С точки зрения математики, n-местный предикат представляет собой функцию от нескольких переменных, областью определения которой является предметная область, а областью значений – «истина» и «ложь» (1 и 0).

Операции над предикатами

Для предикатов определен тот же набор операций, что и для высказываний:

• конъюнкция предикатов образует новый предикат, принимающий значение «истина» для тех аргументов, при которых оба исходных предиката представляют собой истинные высказывания. Иными словами, область истинности конъюнкции предикатов – пересечение областей истинности исходных предикатов;
• дизъюнкция предикатов образует новый предикат, принимающий значение «истина» для тех аргументов, при которых хотя бы один из исходных предикатов представляет собой истинное высказывание. Иными словами, область истинности дизъюнкции предикатов – объединение областей истинности исходных предикатов;
• отрицание предиката образует новый предикат, истинный для тех значений аргумента, для которых исходный предикат является ложным высказыванием, и ложный для тех значений, для которых исходный предикат истинный;
• импликация предикатов образует новый предикат, ложный на тех и только тех наборах аргументов, при которых первый из исходных предикатов (посылка) обращается в истинное высказывание, а второй (заключение) – в ложное;
• эквиваленция двух предикатов образует новый предикат, истинный для тех и только тех наборов аргументов, при которых оба исходных предиката превращаются в истинное выражение или оба исходных предиката обращаются в ложное выражение.

Наряду с перечисленными операциями, общими для высказываний и предикатов, для предикатов определены специфические операции – навешивание кванторов (квантора существования и квантора всеобщности).

Квантор всеобщности связывает переменную и обращает одноместный предикат в истинное выражение в том случае, если предикат истинен для всех значений аргумента из предметной области. В случае с n-местным предикатом (n>1) переменные могут связываться кванторами по отдельности, т.е., например, при связывании одной из переменных в двухместном предикате будет получен одноместный предикат, который будет истинным выражением при условии истинности при каждом значении связанной переменной и выбранном значении свободной переменной.

Квантор существования действует подобно квантору всеобщности, но для истинности предиката не требуется истинность при всех значениях связанной переменной – достаточно истинности хотя бы при одном ее значении.

Рассмотрим одноместный предикат: «Население Москвы не меньше населения х», где х – российский город. Свяжем переменную х квантором всеобщности и получим истинное высказывание: «Население Москвы не меньше населения любого российского города». Важно, что здесь используется «не меньше»: если бы использовалось «больше», при х= «Москва» (Москва – тоже один из российских городов, соответственно, принадлежит области определения аргумента) высказывание было бы ложным.

Рассмотрим другой одноместный предикат: «Население Белгорода больше населения х», где х – российский город. Свяжем переменную х квантором существования: «Существуют российские города такие, что население Белгорода больше населения этого города». Получено истинное высказывание (т.к. существуют города с населением меньше, чем в Белгороде; при этом существование городов с большим населением не делает высказывание ложным).

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

• «хотя бы n объектов обладает свойством P» - «существуют объекты х1, х2, … хn такие, что P(x1), P(x2)…P(xn) и х1, х2 …хn не совпадают»;
• «не более n-1 объектов обладает свойством P» - «для любых x1, x2 … xn если P(x1), P(x2)…P(xn), то x1 совпадает с х2, или х1 совпадает с х3, или ….).

Кванторы существования и двойственности называют двойственными по отношению друг к другу. Это значит, что при применении отрицания предиката, переменная в котором связана квантором, квантор меняется на двойственный ему: существования – на всеобщности, а всеобщности – на существования.

Например, отрицание для выражения «Все яблоки красные» - «Неверно, что все яблоки красные», или, что эквивалентно, «Некоторые яблоки не красные». Квантор всеобщности «все» был заменен на квантор существования «некоторые».

Отрицание выражения: «Некоторые кошки умеют говорить» - «Неверно, что некоторые кошки умеют говорить», или «Все кошки не умеют говорить». В этом случае квантор существования был заменен на квантор всеобщности.