Логические основы работы системы Пролог-Д.

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

Математическая логика является теоретической основой логического программирования. Цель данного раздела определить начальные понятия математической логики, необходимые для изложения принципов работы с системой Пролог-Д.

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

Для решения задачи с помощью Пролога-Д достаточно описать знания об этой задаче, а процесс построения решения при этом сводится к некоторой рутинной процедуре.

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

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

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

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

Терм - это переменные, константы и функции вида

 

f(t₁,t₂,...,t_n),(t₁,t₂,...,t_n) ,             (2.1)

                                 

 где каждое t_i – терм; 

 f - n-арный функциональный символ или функтор.                           

 Арностью называют число аргументов. Особенность функции (2.1) в том, что она принимает значение элемента предметной области Dⁿ , или иными словами представляет собой некоторое отображение совокупности из n (n - ки) элементов из предметной области в элемент области.

Отношения, определяемые над объектами, отличаются от функций. Отношение определяет совокупность элементов из предметной области и представляет собой отображение из D ⁿ в множество {ИСТИНА, ЛОЖЬ}. Например, отношение мама(x, y) определяет совокупность пар (x, y), таких, что элементы множества людей x и y находятся в отношении родства мама. Множество пар (x, y) это множество матерей и детей. В математической логике отношениям даются имена, называемые предикатными символами, а сами отношения называются предикатами в последнем примере предикатный символ-мама.

Дадим более строгое понятие предиката.

Предикат - это выражение вида

 

 P(t₁,t₂,...,t_m),                (2.2)

                                             

где каждое t_i – терм;

P - m-арный предикатный символ.

Формально предикат (2.2) можно читать либо как "m - ка (t₁,t₂,...,t_m) принадлежит отношению Р", либо как высказывание Р справедливо для m-ки (t₁,t₂,...,t_m).

В логике имеется набор связок.

Пример

&, , , <- , <->, которые читаются как "и", "или", "не", "если", "тогда и только тогда".

      

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

Пример

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

 

(AB) означает (A<-B),                           

(A\/B) означает (A)<-B,      

(A<->B) означает (A<-B)(B<-A),

 

где А и В - суть формулы.

 

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

 

xА означает ((x(А))),             (2.6)

 

где х - переменная;

А- формула.                    

Пример

Приведем примеры формул

мама(x, y)мама(y, z);

F1F2F3F4, если F1,F2,F3,F4 - формулы.

Q(F1,F2), если F1 и F2 - формулы, а Q - квантор существования () или общности ().

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

Предложение - это формула, в которой каждая переменная находится в области действия квантора общности.

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

Предложения, построенные в соответствии с введенными выше правилами, образуют язык логики первого порядка. В этом языке термы представляют собой объекты, а предикаты отношения между объектами. С помощью этого языка можно описать все задачи, решаемые на ЭВМ. На основе языка логики первого порядка можно построить различные языки логического программирования, различающиеся по правилам формирования предложения. Среди множества всевозможных предложений особое значение имеют предложения, содержащие связки "и" и одну связку "если". Такие предложения называются дизъюнктами. Дизъюнкт - это предложение вида

 

A₁A₂...A_kB₁B₂...B_n,               (2.7)   

 

где A₁,A₂,...,A_k,B₁,B₂,...,B_n - предикаты или литеры;

 - связка "и";

<- - связка "если".

Особое значение для Пролога-Д имеет понятие дизъюнкта Хорна, играющий важную роль при составлении баз.

Дизъюнктом Хорна называется такой дизъюнкт, у которого k равно 0 или k равно 1. При k равно n равно 0 получается пустой дизъюнкт, обозначаемый символом Л.

Если k равно 0, то из формулы (2.7) получается дизъюнкт

 

     B₁B₂...B_n,                   (2.8)                                           

 

Этот дизъюнкт называется вопросом.

Среди множества всех дизъюнктов особую роль играют те, для которых k равно 1. Если при этом еще и n равно 0, то такой дизъюнкт называется фактом A₁.

Если же n больше0, дизъюнкт называется правилом

 

A₁<-B₁B₂...B_n,                    (2.9)                       

 

где A – голова;

B₁B₂...B_n, - цели, образующие тело правила.

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

Базой знаний (БЗ) будет называться всякое (непустое) множество фактов и правил.

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

 

          (x>y)<-(|x|>|y|),           (2.10)                                  

 

где знак x>y - означает отношение "x больше y";

знак |x| - абсолютную величину x, истинна, если x и y  принадлежат множеству положительных чисел и ложна, если x и y принадлежат множеству отрицательных чисел.

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

Для интерпретации множества предложений S выбирается множество объектов D, называемое областью интерпретации.

Интерпретация множества предложений S над D состоит из следующих трех соответствий.

 

Пример

а) каждой константе (числовой или литеральной) ставится в соответствие некоторый элемент из D.

б) каждому n-арному функтору из S сопоставляется отображение n-ки из Dⁿ в D.

в) каждому n-арному предикатному символу из S сопоставляется отображение n-ки из области Dⁿ в множество {ИСТИНА, ЛОЖЬ}.

База знаний и следующий за ней вопрос представляют собой программу на Прологе-Д.

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

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

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

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

 

Пример

Рассмотрим программы логических основ в Прологе с использованием формул сокращения, написать базу данных о городах государств, используя связки «не» и «или».

Представим базу знаний, она содержат информацию о названиях государств и городах, которые принадлежат этим государствам. Используя связки «не» и «или» запишем два правила (строка 5 и 6), характеризующие принадлежность государства к российскому или иностранному и зададим вопрос, используя связку «или», к базе

 

?ИЛИ(российское(x),иностранное(x));

 

 Таким образом, при запуске Пролога будет найден российский или иностранный город, причем чтобы он принадлежал материку Россия.