Определение предиката. Кванторы. Формулы логики предикатов
Предикат – это повествовательное предложение, содержащее предметные (индивидные) переменные, замена которых на константные значения превращает рассматриваемое предложение в высказывание – истинное или ложное. Другими словами, выражение P(x1, x2, ... , xn), содержащее предметные переменные x1ÎM1, x2ÎM2,… xnÎMn, называется n-местным предикатом, если оно выражает некоторое n-местное отношение на множествах M1, M2,…Mn.
Например, если x, y – предметные переменные, принимающие значения из множества M={Солнце, Земля, Луна, Марс}, то предложение "x вращается вокруг y" можно рассматривать как 2-местный предикат P(x, y). Множество истинности P(x, y) – это множество упорядоченных пар (кортежей) rP={(Земля, Солнце), (Луна, Земля), (Марс, Солнце)}, на которых P(x, y)=1. Множество rP выражает бинарное отношение на множестве M небесных тел, например, "Земля rP Солнце". Можно сказать, что P(x, y) – это предикат отношения rP .
Если все переменные x1, x2, ... , xn принимают конкретные значения, то предикат есть не что иное, как высказывание, Таким образом, высказывание является частным случаем предиката.
Предикат называется тождественно истинным, если значение его для любых аргументов есть "истина"; тождественно ложным, если значение его для любых аргументов есть "ложь"; выполнимым (опровержимым), если существует, по крайней мере, один набор его аргументов, для которого значение предиката есть "истина" ("ложь").
Над предикатами можно производить обычные логические операции и получать при этом другие предикаты. Таким образом, можно говорить об алгебре предикатов. Кроме операций логики высказываний, в логике предикатов используются особые логические символы – кванторы.
Квантор общности. Пусть P(x) – некоторый предикат, определенный для каждого x Î М. Тогда выражение "xP(x) является истинным высказыванием, если P(x) истинно для всякого x Î М, и ложным в противном случае. Символ "x называется квантором общности. Выражение "xP(x) читается: "Для всех x имеет место P(x)". В обычной речи квантору общности соответствуют слова: все, всякий, каждый, любой. Возможно отрицание квантора общности: Ø"xP(x): "Не для всех x имеет место P(x)".
Квантор существования. Пусть P(x) – некоторый предикат, x Î М. Тогда выражение $xP(x) является истинным высказыванием, если P(x) истинно хотя бы для одного x Î М, и ложным в противном случае. Символ $x называется квантором существования. Выражение $xP(x) читается: “Существует x, для которого имеет место P(x)”. В обычной речи квантору существования соответствуют слова: некоторый, несколько. Возможно отрицание квантора существования: Ø$xP(x): "Не существует x, для которого имеет место P(x)".
Кванторы существования и общности называются двойственными кванторами. Переменная, стоящая под знаком квантора, называется также связанной переменной. Несвязанная переменная называется свободной.
Кванторы применяются и к многоместным предикатам, при этом число свободных переменных уменьшается на единицу. Одноместный предикат при связывании переменной квантором становится 0-местным предикатом, т. е. высказыванием.
Формула логики предикатов определяется индуктивно следующим образом:
1) всякая формула логики высказываний есть формула логики предикатов;
2) предметные переменные x, y, z, ... есть формулы;
3) предикаты P(x), Q(x, y), ... , а также выражения с кванторами "xP(x), $xR(x), "x$yQ(x, y),... есть формулы;
4) если F1 и F2 – формулы, то выражения ØF, (F1ÙF2), (F1ÚF2), (F1®F2), (F1«F2) тоже являются формулами, в которых свободные переменные формул F1 и F2 остаются свободными, а связанные переменные формул F1 и F2 остаются связанными;
5) других формул, кроме построенных по правилам пунктов 1 – 4, нет.
Пусть A – формула, содержащая свободную переменную x. Тогда "xA, $xA – формулы, причем в первом случае A является областью действия квантора общности, а во втором – областью действия квантора существования.
Формулы F и G, определенные на некотором множестве М, называются равносильными на этом множестве, если при любых подстановках констант вместо переменных они принимают одинаковые значения. Формулы, равносильные на любых множествах, называются просто равносильными.
Переход от одних формул к равносильным им другим формулам логики предикатов может быть произведен по нижеследующим правилам.
1. Все равносильности, имеющие место для логики высказываний, переносятся на логику предикатов.
2. Знак отрицания можно ввести под знак квантора, заменив квантор на двойственный.
Ø("xA(x) º $x(ØA(x)).
Ø($xA(x)) º "x(ØA(x)).
3. Вынос квантора за скобки.
Пусть формула A(x) содержит переменную x, а формула B не содержит переменной x, и все переменные, связанные в одной формуле, связаны в другой. Тогда
"xA(x)ÚB º"x(A(x)ÚB).
"xA(x)ÙB º"x(A(x)ÙB).
$xA(x)ÚB º$x(A(x)ÚB).
$xA(x)ÙB º$x(A(x)ÙB).
4. Дистрибутивность квантора общности относительно конъюнкции и квантора существования относительно дизъюнкции.
Пусть формула B, так же, как и формула A, зависит от х. Тогда
"xA(x) Ù "xB(x) º "x(A(x)ÙB(x)).
$xA(x) Ú $xB(x) º $x(A(x)ÚB(x)).
Дистрибутивные законы для квантора общности относительно дизъюнкции и квантора существования относительно конъюнкции не имеют места.
5. Перестановка одноименных кванторов.
"x"yA(x,y) º "y"xA(x,y).
$x$yA(x,y) º $y$xA(x,y).
Разноименные кванторы переставлять нельзя.
6. Переименование связанных переменных.
Заменяя связанную переменную формулы A другой переменной, не входящей в эту формулу, всюду: в кванторе и в области действия квантора – получим формулу, равносильную A.
Формула есть перевод содержательного рассуждения в формальное рассуждение. Формула имеет смысл только тогда, когда имеется какая-нибудь интерпретация входящих в нее символов. Каждая интерпретация состоит в указании множества М изменения предметных переменных и задании отношения между переменными с помощью предикатов.
Для данной интерпретации формула представляет собой высказывание, если переменные связаны кванторами, а если есть свободные переменные, то формула есть предикат, который может быть истинным для одних значений переменных из области интерпретации и ложным для других.
Формула A называется выполнимой в данной интерпретации, если существует набор значений переменных (a1, a2, ... , an) 
M, для которого A(a1, a2, ... , an) = 1. Формула A называется истинной в данной интерпретации, если A(x1, x2, ... , xn) = 1 на любом наборе своих переменных (x1, x2, ... , xn) M. Формула A называется общезначимой или тождественно-истинной, если она истинна в каждой интерпретации. Формула A называется выполнимой, если существует интерпретация, для которой она выполнима.
Проблема разрешимости для логики предикатов, так же, как и для логики высказываний, заключается в том, чтобы установить, является ли произвольная формула тождественно истинной.