Логика - доступно для всех

  • Увеличить размер шрифта
  • Размер шрифта по умолчанию
  • Уменьшить размер шрифта

Исчисление предикатов. Основные понятия и определения.

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Узнать стоимость

 

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

 Предикат - повествовательное предложение, содержащее предметные переменные, определенные на соответствующих множествах.  При замене переменных конкретными значениями (элементами) этих множеств предложение обращается в высказывание, т.е. принимает значение "истинно" или "ложно". Обозначение предиката, содержащего п переменных (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 - местной функции) возможно не всегда, а только для таких предикатов Р’ для которых выполняется условие, связанное с требованием однозначности функции.

Внимание!
Если вам нужна помощь в написании работы, то рекомендуем обратиться к профессионалам. Более 70 000 авторов готовы помочь вам прямо сейчас. Бесплатные корректировки и доработки. Узнайте стоимость своей работы.

 

 

Случайная новость