<<
>>

Представление знаний с помощью логики предикатов

Данный подход к представлению классов объектов и отношений между ними базируется на использовании понятий исчисления предикатов. Суть заключается в следующем: взаимосвязи между различными объектами описываются с помощью предикатов.
Если Р есть «-местная предикатная переменная, а х2, х„ — предметные переменные (аргументы предиката), то, по определению, выражение есть атомарная (элементарная) формула. Содержательно эта формула означает высказывание, гласящее, что объекты Хь х2,..., хп связаны отношением Р.

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

Например, факт «Петров работает программистом» можно представить следующим образом:

Работает (Петров, Программист)

Причем теперь в системе все предикаты такого типа должны в списке аргументов на первом месте содержать фамилию служащего, а на втором месте — название должности, например:

Работает (Иванов, Лаборант)

Работает (Кузнецов, Слесарь) и т.п.

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

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

В высказывании, записанном в нотации исчисления предикатов, некоторый объект может быть представлен как КОНСТАНТА, т.е. как конкретный индивидуум или класс индивидуумов, или как ПЕРЕМЕННАЯ, в результате чего конкретный индивидуум или класс индивидуумов остаются незаданными, например:

Является (X, Специалист по ЭВМ).

Одна из возможных интерпретаций этого предиката может быть такой: имеется некоторый объект X, который является специалистом по ЭВМ.

Когда переменной ставится в соответствии определенное имя некоторого объекта (т.е. некоторой константы), то говорят, что происходит порождение экземпляра этой переменной.

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

И (and, л, &),

ИЛИ (or, v,),

НЕ (not, —.),

ИМПЛИКАЦИЯ (-»).

Импликация читается как:

ЕСЛИ ..., ТО ....

Для того чтобы в исчислении предикатов можно было манипулировать переменными, введены дополнительные структуры — кванторы. Кванторы служат для указания меры, в какой экземпляры переменных должны быть истинны, чтобы высказывание в целом тоже было истинным:

V — квантор общности; 3 — квантор существования.

Например, пользуясь кванторами, предложение «все специалисты по ЭВМ являются операторами» можно представить следующим образом:

(VX) (Специалист по ЭВМ (X) -» ОПЕРАТОР (X)), а предложение «некоторые специалисты по ЭВМ являются операторами»: (ЗХ (Специалист по ЭВМ (X) -» ОПЕРАТОР (X)).

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

(VX) (3Y) (Служащий (X) -» Руководит (Y, X))

может быть интерпретировано как «каждым служащим X руководит некоторое лицо Y». А утверждению

(3Y) (VX) (Служащий (X) -» Руководит (Y, X))

соответствует интерпретация «есть такое лицо Y, которое руководит всеми».

Конструирование сложных высказываний из элементарных с помощью логических связок и кванторов подчиняется определенным правилам, называемым правилами вывода. По правилам вывода можно из исходных, так называемых, правильно построенных формул (ППФ), строить новые правильно построенные формулы.

Рассмотрим определение ППФ (далее будем говорить логическая формула).

1. Атомарный предикат является логической формулой.

2. Если А, В — логические формулы, то А л В, A v В, ~U, ~]в, А -» 5, В -> А также являются логическими формулами.

3. Если С(Х) — логическая формула, то и (VX)C(X), и (ЗХ) С(Х) также являются логическими формулами.

4. Все формулы, полученные повторением конечного числа раз формул 1, 2, и 3, являются логическими формулами.

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

Рассмотрим некоторые правила вывода.

1. Из двух логических формул А и А -> В выводится новая логическая формула В (Modus ponens). Для описания правил вывода во многих случаях используется нотация, когда над чертой записывается группа выражений, выступающих в качестве посылки, а под чертой записывается выражение, которое из них выводится:

А->В,А В ’

Например: «Если моя программа правильна, то она будет работать; моя программа правильна; следовательно, она будет работать».

2. Modus tollens (отрицательный способ рассуждений):

А-> В, ~ В ~А ’

Например: «Если моя программа правильна, то она будет работать; моя программа не будет работать; следовательно, она неправильна».

3. Двойное отрицание:

А

~(~А)

Например: «Моя программа работала; следовательно, моя программа не не работала».

4. Введение конъюнкции:

А, В

АлВ' -

Например: «Моя программа работала, она правильна; следовательно, моя программа работала и она правильна».

5. Заключение истинности суждения независимо от посылки:

А —> В\ ~ А —> В В ’

Например: «Если моя программа правильна, то она будет работать; если моя программа неправильна, то она будет работать; моя программа будет работать».

6. Специализация. Она означает, что если некоторому классу объектов присуще какое-либо свойство, то любой объект этого класса будет обладать этим же свойством:

(УХ)ЩХ),Л \У(А) '

Например: «Все предметы, являющиеся ЭВМ, надежны; 1ВМ РС — ЭВМ; следовательно, 1ВМ РС надежна».

Правила вывода, которые из известных выражений выводят некоторое новое выражение, называют правилами дедуктивных выводов.

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

1) установить соответствие между константами логики предикатов и сущностями описываемой ПО (в качестве констант выступают имена сущностей);

2) установить соответствие между атомарными предикатами и отношениями, между сущностями, имеющими место в ПО;

3) выполнить описание функциональных отношений ПО с помощью формул логики предикатов;

4) задать значения истина или ложь в зависимости от выполнения или

невыполнения отношений ПО, описанных логическими формулами. ‘

Пример. БД представлена совокупностью трех фактов:

1: Руководит (Петров, Иванов) — интерпретация: Петров руководит Ивановым;

2: Руководит (Иванов, Кузнецов) — интерпретация: Иванов руководит Кузнецовым;

3: Руководит (Кузнецов, Яковлев) — интерпретация; Кузнецов руководит Яковлевым.

Эти факты истинны, поскольку имеют место в данной ПО, и потому их представляют в базе данных.

Далее описывают два прикладных правила (т.е. функциональных отношения), которые имеют место в рассматриваемой ПО.

Правило 1: V(X, Y) (Руководит (X, Y) -» Отчитывается (Y, X)) — интерпретация: «Для всех значений X и Y, если X руководит Y, то Y отчитывается перед X».

Правило 2: V(X, Y, Т) (Руководит (X, Y) л Отчитывается (Т, Y) -> Отчитывается (Т, X)), где X, Y, Т — переменные; интерпретация: «Для всех значений X, Y, Т, если X руководит Y и Т отчитывается перед Y, то Т отчитывается перед X».

Теперь посмотрим, как в такой модели можно обрабатывать запросы пользователей.

Например, поступает следующий запрос: «Проверить, имеет ли место в ПО факт «Яковлев отчитывается перед Ивановым» (т.е. иначе сделать заключение, что «Яковлев отчитывается перед Ивановым».

Итак, в данной базе данных непосредственно такого факта нет. Однако предикат, описывающий интересующее нас отношение, встречается в правилах 1 и 2. Применим правило 1 к факту 3. Выполнив подстановку значения констант из факта 3 на позиции соответствующих переменных в правиле 1, получим следующую логическую формулу:

Руководит (Кузнецов, Яковлев) —> Отчитывается (Яковлев, Кузнецов).

Применяя к ней и факту 3 правило вывода Modus ponens, получим логическую формулу

Отчитывается (Яковлев, Кузнецов),

описывающую тот факт, что Яковлев отчитывается перед Кузнецовым. Так как применялось правило вывода и исходные выражения были истинными, то, следовательно, и данное заключение является истинным. Итак, данный факт имеет место в данной ПО, хотя в явном виде он в базе и не представлен.

Применяя к этому факту (промежуточному результату) и факту 2 правило 2 и выполнив подстановку значений констант из фактов на позиции соответствующих переменных в правиле 2, получим следующую логическую формулу:

Руководит (Иванов, Кузнецов) л Отчитывается (Яковлев, Кузнецов) —>

—> Отчитывается (Яковлев, Иванов).

Применяя к факту 2 и к факту (Отчитывается Яковлев, Кузнецов) правило вывода «введение конъюнкции», получим логическую формулу Руководит (Иванов, Кузнецов) л Отчитывается (Яковлев, Кузнецов).

Применяя к ней и к формуле

Руководит (Иванов, Кузнецов) л Отчитывается (Яковлев, Кузнецов) ->

—> Отчитывается (Яковлев, Иванов)

правило вывода Mondus ponens, получим логическую формулу

Отчитывается (Яковлев, Иванов),

описывающую тот факт, что Яковлев отчитывается перед Ивановым.

Так как применялось правило вывода и исходные посылки были истинными, то данное заключение является истинным. Теперь можно дать утвердительный ответ на запрос, действительно ли в ПО имеет место факт, что Яковлев отчитывается перед Ивановым.

5.4.

<< | >>
Источник: Григорьев Ю.А., Ревунков Г.И.. Банки данных. 2002

Еще по теме Представление знаний с помощью логики предикатов:

  1. Позиции-предикаты
  2. Позиции-предикаты
  3. Журналистика и «общество знаний».
  4. 2.6. Диагностика исходного уровня знаний о профессии педагога
  5. Идеализация своих знаний о мире.
  6. Идеализация своих знаний о себе.
  7. Идеализация своих знаний о других.
  8. Идеализация своих знаний о правильном образе жизни.
  9. Логики
  10. ESTJ и ENTJ Экстраверты-логики
  11. ГЛАВА 1 Логика трансформации