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

Традиционная булева алгебра и исчисление высказываний [33] не всегда подходят для выражения логических рассуждений, проводимых людьми, более удобен для этого язык логики предикатов. Под исчислением предикатов понимается формальный язык для представления отношений в некоторой предметной области. Исчисление предикатов подробно обсуждается в ряде книг по теории ИИ [2], [7], [33]. Основное преимущество исчисления предикатов - хорошо понятный мощный механизм математического вывода, который может быть непосредственно запрограммирован. Дальнейшее изложение ведется с учетом того, что читатель знаком с основами булевой алгебры.

Предикатом называют предложение, принимающее только два значения: "истина" или "ложь". Для обозначения предикатов применяются логические связки между высказываниями: ¬ - не, - или, - и, - если, а также квантор существования и квантор всеобщности

x(...) - существует такой x, что ...

x(...) - для любого x

Таким образом, логика предикатов оперирует логическими связками между высказываниями, например, она решает вопросы: можно ли на основе высказывания A получить высказывание B и т.д.

Рассмотрим некоторые примеры. Высказывание "у каждого человека есть отец" можно записать:

x y (человек(x) отец(y,x))

Выражение "Джон владеет красной машиной" записывается, например, так:

x ( владеет(Джон, x) машина(x) красный(x))

Рассмотрим вывод, дающий заключение на основе двух предпосылок:

Предпосылка 1: Все люди смертны

x (человек(x) смертен(x))x (p(x) q(x))

Предпосылка 2: Сократ - человек

p(a)

Заключение: Сократ - смертен

Смертен(Сократ) q(a)

Если обозначить через f функцию одного аргумента, то логическая формула для этого высказывания будет иметь вид:

x (f(x) q(x))

Алфавит логики предикатов состоит из элементов (символов):

x, y, z, u, v, w - переменные;

a, b, c, d, e - константы;

f, g, h - функциональные символы;

p, q, r, s, t - предикатные символы;

¬, , , , , - логические символы.

Запишем на языке исчисления предикатов некоторое выражение:

y x (человек(x) отец(y,x))

Что означает записанное выражение? Ответ очевиден: "у всех людей общий отец".

Приведем пример простого доказательства на языке исчисления предикатов.

Даны следующие факты:

1. "Иван является отцом Михаила" - отец(a,b)

2. "Петр является отцом Василия" - отец(c,d)

3. "Иван и Петр являются братьями" -

w (брат(a,c) отец(w,a) отец(w,c))

Даны следующие определения:

4. "Брат отца является дядей" -

y (дядя(x,u) отец(y,u) брат(y,x))

5. "Сын дяди является двоюродным братом" -

x (дв.брат(z,u) дядя(x,u) отец(x,z))

Требуется доказать, что "Михаил и Василий являются двоюродными братьями":

6. x y (дв.брат(b,d) отец(y,b) брат (y,x) отец(x,d))

Делаем подстановки y = Иван, b = Михаил и x = Петр, d = Василий, видим, что предикаты 1, 2, 3 дают правильное предложение 6.

Рассмотренный нами язык называется исчислением предикатов первого порядка и позволяет связывать знаком квантора переменные, соответствующие объектам из предметной области, но не предикаты или функции.

Исчисление предикатов второго порядка позволяет связывать знаком квантора не только переменные, соответствующие объектам из предметной области, но и предикаты или функции. Примером исчисления предикатов второго порядка может служить выражение "Единственное качество Джона - это честность", которое записывается так:

P (P(Джон) качество(P) P = честность)

На этом мы закончим знакомство с этой моделью и вернемся к ней в следующей лекции при рассмотрении правил вывода, принципа резолюции и методов поиска на основе исчисления предикатов.