Самара, 2015 г

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

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

Вычисление результата решения проблемы соответствует тако­му доказательству существования искомого объекта, когда требуе­мый объект строится явно.

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

Алгоритм = Логика + Управление,

где «Логика»» обозначает ту часть программы, которая моделирует структуру предметной области, а «Управление» реализуется интерпре­татором, который делает выводы из логической части программы.

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

Синтаксис логического способа представления знаний. Правила в логическом представлении имеют вид

Р₀←Р₁,..,Р_п (1)

где Р₀, Р₁,..., Р_n — атомарные формулы.

Определение 1. Логическая формула называется атомарной, если она имеет вид P(t_1,…,t_n), где Р — n-арный предикатный сим­вол, a t_1, t_2,…, t_n — либо переменная, либо константа, либо состав­ной, терм вида f (t₁ t₂,…, t_n), где f — n-арный функциональный символ.

Определение 2. Термами называют некоторые сущности, кото­рые могут быть простыми (простой терм вида 0 и сложными (со­ставной терм вида f (t_1, t₂,.., t_n)).

В формуле (1) Р₀ называют целью, a P₁, Р₂,…, Р_n —телом правила. Предикаты Р₁, Р₂,…, Р_n — условия, которые должны быть выполнены, чтобы достижение цели Р₁ стало успешным.

Когда n=0 (тело пусто и отсутствуют предварительные условия достижения цели Р₀), правило (1) называется фактом. Если пра­вило имеет вид

←Q₁,Q₂,...,Q_n, (2)

где Q — атомарные формулы и n>0, то оно называется запросом. Запрос интенсионально определяет множество таких объектов, ко­гда формула (2) истинна.

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

При использовании логических методов сначала анализируется структура предметной области, затем выбираются соответствующие обозначения и в заключение формируются логические формулы, представляющие закономерности рассматриваемой области. Мно­жество таких формул, по существу, будет являться логической про­граммой, содержащей информацию о ПО. В частности, в качестве языка логического программирования можно использовать ПРОЛОГ, а совокупность логических формул, состоящую из запроса, множе­ства фраз программы и интерпретатора языка, можно рассматри­вать как алгоритм решения задач приложений. Причем запрос и логические правила программы представляют собой множество на­чальных формул алгоритма, а интерпретатор обеспечивает правила преобразования этих формул.

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

Семантика логического программирования. Для выяснения смыс­ла логических программ необходимо каждой программе приписать некоторое значение, вычисляемое программой. Возможны три под­хода к определению семантики логических программ: декларатив­ная семантика, процедурная (или операционная) семантика и вы­числительная семантика.

Декларативная семантика определяет такие значения конкрет­ных отношений, заданных логическими формулами, когда они ста­новятся истинными.

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

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

Рассмотрим логическую формулу

P ← Q, R, (3)

где Р, Q и R — некоторые предикаты.

С точки зрения декларативной семантики Р истинно, если Q и R истинны, а с точки зрения процедурной семантики необходимо сначала установить истинность Q (решить подзадачу Q), а за­тем — установить истинность R (решить подзадачу R). Таким обра­зом, различие между декларативной и процедурной семантикой за­ключается в том, что процедурная семантика определяет не только логические связи между заголовком логической формулы и усло­виями в ее теле, но также и порядок, в котором эти условия обра­батываются. Так, для формулы (3) сначала должна быть установ­лена истинность Q, а затем истинность R.

Декларативный смысл логической программы определяет ис­тинность Р вне зависимости от порядка обработки условий Q и R, так как все условия соединены логической операцией & и должны соблюдаться одновременно.

Логический вывод. Принцип резолюции. Определение 3. Логиче­ский вывод — это получение некоторой формулы исходя из множе­ства других логических формул путем применения правил вывода.

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

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

P(a,b) v Q(c,d), (4)

_­­­⌐P(a,b) v R(c), (5)

то можно получить их резольвенту в виде

Q(c,d) v R(c). (6)

Фактически принцип резолюции распространяет общепринятое правило вывода modus ponens на дизъюнкты с произвольным чис­лом литер. Действительно, так как P→Q равносильно ⌐P v Q, то исходя из истинности Р в соответствии с принципом резолюции непосредственно следует истинность Q.

Если есть множество логических формул Q и некоторая формула Р, то для проверки выводимости Р из Q следует применить следую­щую процедуру. Берем отрицание Р исходной формулы и, выбирая некоторую формулу из множества £2, содержащую позитивную лите­ру Р, строим их резольвенту, которая аналогичным образом может быть использована для построения другой резольвенты, и т. д.

Повторяя данную процедуру, можно в конце концов вывести некоторую формулу F, состоящую из одного предиката, и противо­положную формулу ⌐F, резольвента которых даст пустую формулу. Это означает противоречие и, следовательно, выводимость перво­начальной формулы Р из множества формул Ω.

Фактически в основе приведенной выше процедуры использу­ется доказательство от противного: если в результате отрицания ис­ходной посылки мы получим противоречие, то это значит, что ис­ходная посылка истинна.

Для сопоставления логических формул, содержащих перемен­ные, необходима специальная процедура, называемая подстанов­кой. Содержательно подстановка применяется к некоторому логи­ческому выражению и заменяет в нем каждое вхождение перемен­ной X_i на терм t_i. Обозначим подстановку символом 0, тогда Θ={х₁:=t,х₂:=t₂,...,x_n:=t_n}. Подстановка Θ называется унифи­катором атомарных формул P_i и Р₂, если P_i = ΘР₂. С помощью процедуры унификации удается провести сопоставление двух ато­марных формул P_i и Р₂.

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

В качестве примера рассмотрим множество дизъюнктов вида

P(a,Y) v Q(a,Y), (7)

Q(X,b) v⌐ R(X,b), (8)

W(b), (9)

R(a,b). (10)

Требуется установить выводимость из заданного множества хорновских дизъюнктов формулы Р(а, b). Для этого берем отрица­ние формулы Р(а, b) и строим ее резольвенту с формулой (7).

Резольвента ⌐Q(a, b) может быть найдена, если использовать подстановку

Θ₁ = {Y:= b}.

Полученная формула может быть унифицирована с предикатом Q(X, b) формулы (8) путем использования подстановки

Θ₂={Y:=a},

что позволяет вывести новую резольвенту

⌐R(а, b). (11)

Резольвента формул (10) и (11) дает пустой дизъюнкт, что означает противоречие. Так как добавление Р(а,b) к исходному множеству дизъюнктов приводит к противоречию, то это значит, что Р(а, b) является их следствием.

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

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

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

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

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

Список используемой литературы

Гаскаров, Д.В. Интеллектуальные информационные системы. Учеб. для вузов. — М.: Высш. шк., 2003. — 431 с: ил.