В данном курсе лекций описание формальной теории исчисления предикатов носит конспективный характер, в частности, многие сложные доказательства опущены. В то же время, основное внимание уделено прагматическим аспектам теории, которые могут принести большую пользу инженеру-программисту. Напомним еще раз наиболее важные аспекты исчисления предикатов.
Предикат — повествовательное предложение, содержащее предметные переменные, определенные на соответствующих множествах. При замене переменных конкретными значениями (элементами) этих множеств предложение обращается в высказывание, т.е. принимает значение «истинно» или «ложно». Обозначение предиката, содержащего п переменных (n-местного предиката): Р(х1, х2,…, хn), при этом предполагается, что х1 Î М1, х2 ÎМ2, …, хn Î Мn.
С помощью логических связок (и скобок) предикаты могут объединяться в разнообразные логические формулы — предикатные формулы. Исследование предикатных формул и способов установления их истинности является основным предметом логики предикатов. Логика предикатов вместе с входящей в нее логикой высказываний является основой логического языка математики. С ее помощью удается формализовать и точно исследовать основные методы построения математических теорий. Логика предикатов является важным средством построения развитых логических языков и формальных систем (формальных теорий).
Логика предикатов, как и логика высказываний, может быть построена в виде алгебры логики предикатов и исчисления предикатов. Здесь, как и в случае логики высказываний, для знакомства с основными понятиями логики предикатов воспользуемся языком алгебры, а не исчислений. Такой выбор обусловлен рядом причин:
• Исследование предикатных формул алгебры логики, выполнение их преобразований значительно проще, чем в исчислении предикатов.
• Ограничения в использовании аппарата алгебры обусловлены тем, что предметные области (множества, на которых определены предметные переменные предикатов) теоретически могут быть и бесконечными. В таких случаях стандартный метод проверки истинности предикатов и формул в целом, требующий подстановки всех возможных значений предметных переменных, не может быть осуществлен в строгом смысле (точнее, процедура вычисления истинности может быть бесконечной и не дать ответа за конечное время). Однако в практических ситуациях при описании реальных систем, процессов, явлений в качестве предметных областей, как правило, используются конечные множества. Поэтому проблема бесконечности в значительной степени теряет свою актуальность.
n — местный предикат — это функция Р(х1, х2,…, хn) от п переменных, принимающих значения из некоторых заданных предметных областей, так что х1 Î М1, х2 Î М2, ., хn Î Мn, а функция Р принимает два логических значения — «истинно» или «ложно» (обозначения: {И, Л}, {1, 0}). Таким образом, предикат Р(х1,х2,…,хn) является функцией типа Р: М1 x М2 x … x Мn → B, где множества М1, М2, …, Мn называются предметными областями предиката; х1, х2,…, хn — предметными переменными предиката; В — двоичное (бинарное) множество: В = {И, Л} или {1,0}. Если предикатные переменные принимают значения на одном множестве, то Р: Мn→В.
Соответствия между предикатами, отношениями и функциями:
1. Для любых М и п существует взаимно однозначное соответствие между n -местными отношениями и п — местными предикатами Р(х1, х2,…, хn), Р: Мn→В:
• каждому n — местному отношению R соответствует предикат Р(х1, х2,…, хn) такой, что Р(a1, a2,…, an) = 1, если и только если (a1, a2,…, an) Î R;
• всякий предикат Р(х1, х2,…, хn) определяет отношение R такое, что (a1, a2,…, an) Î R, если и только если Р(a1, aх2,…, an) = 1.
При этом R задает область истинности предиката Р.
2. Всякой функции f(х1, х2,…, хn), f: Мn → М, соответствует предикат Р(х1, х2,…, хn, хn+1), Р: Мn+1→В, такой, что Р(a1, a2,…, an, an+1 ) = 1, если и только если f(a1, aх2,…, an) =an+1.
Понятие предиката шире понятия функции, поэтому обратное соответствие (от (n+1)-местного предиката к n — местной функции) возможно не всегда, а только для таких предикатов Р’ для которых выполняется условие, связанное с требованием однозначности функции.