81 ПРЕДСТАВЛЕНИЕ ЗНАНИЙ В ИНФОРМАЦИОННЫХ СИСТЕМАХ

ВВЕДЕНИЕ

 

Информационные системы (ИС) входят в число важнейших компонентов науки и производства. Они широко используются для обучения и решения конкретных задач в различных областях человеческой деятельности: в автоматизированных системах управления (АСУ) и научных исследований (АСНИ), системах автоматизации проектирования (САПР), информационно-поисковых системах (ИПС), системах управления базами данных (СУБД), экспертных системах (ЭС), системах поддержки принятия решения (СППР) и т.д.

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

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

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

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

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

 

1. Формально-логическая модель

1.1. Общие положения

В основе формально-логической модели знаний лежит понятие формальной теории :

= < ,,, >,

где счетное множество базовых символов (алфавит) теории ;

– подмножество выражений теории , называемых формулами теории;

– выделенное множество формул, называемых аксиомами теории ;

конечное множество отношений {,…,} между формулами,

4

называемыми правилами вывода.

Чтобы придать формуле содержание, ее интерпретируют как утверждение, распространяющееся на некоторую область  (область интерпретации).

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

Формула называется теоремой, если существует доказательство, в котором она является последней.

 

1.2. Синтаксис языка предикатов первого порядка

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

Алфавит языка предикатов первого порядка:

-          разделители:  запятая - “,” , открывающая скобка - “(” , закрывающая скобка - “)” ;

-          константы – строчные буквы – “ ”,…;

-          переменные – прописные (заглавные) буквы – “ ” ,…;

-          предикаты – заглавные буквы;

-          функции (не предикаты) – строчные буквы – “ ”,…;

-          логические операции:

1)      Ø - отрицание,

2)      Ù - коньюнкция,

3)      Ú - дизъюнкция,

4)      ® - импликация (если…то…),

5)      « - эквивалентность (…тогда и только тогда, когда…),

6)      $ - квантор существования (сушествует…),

7)  " - квантор общности (для любого…).

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

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

Терм – выражение, включающее константы, переменные и n-местные функции от термов.

Атом – элементарная функция – это выражение, включающее константы, переменные, функции и предикаты.

Правильная формула (ПФ) – это атом, Ø, Ú, Ù, ($), ("), где , – ПФ; – переменная; ($) означает: существует , для которого справедливо ; (") означает: для любого  справедливо .

Правило вывода – процедура, которая из одной или нескольких ПФ производит другие ПФ.

5

Исходные ПФ в теории называются аксиомами.

 

1.3. Семантика языка предикатов первого порядка

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

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

Некоторые ПФ эквивалентны друг другу. Ниже представлена таблица 1.1    эквивалентных    (построчно)    ПФ.   Эквивалентные   ПФ   совпадают независимо от их интерпретации.

Формы записи ПФ разнообразны.  Обычно ПФ представляются как дизъюнкция литералов. Литерал - это атом или его отрицание. Литерал, не    содержащий    переменных,    называется   конкретным.  Формулу, представляющую собой дизъюнкцию литералов, называют предложением (дизъюнктором). В каждом литерале отсутствуют операции (включая кванторы)   и   область   действия  знака  отрицания  уменьшена  до  одной предикатной буквы (пример: Ø()). Каждый квантор в пределах области действия по закону немых переменных можно связать со своей переменной. Пример:

(")(()Ú($)())=(")(()Ú($)().

Квантор существования в ПФ можно исключить с помощью функций Сколема.  Пример ПФ:  (")($)(,)  –  “Для  всех    существует такое, что (,)”. Пусть имеется функция =(), отображающая каждый  в  (функция Сколема). Тогда вместо исходной ПФ получаем (")(,()).

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

((")(Ø()ÚØ(,)Ú((,)Ù((")((Ø(,(,)))Ú

Ú(,))))))Ú((")())=(")(")(")(Ø() ÚØ(,) Ú

Ú((,)Ù(Ø(,(,))Ú(,)))Ú()).

Матрицу  в  свою очередь с помощью законов ассоциативности и дистрибутивности операций Ú и Ù можно привести к коньюнктивной нормальной форме как коньюнкцию конечного множества дизъюнкций литералов. Например:

(")(")(")((Ø()ÚØ(,)Ú()Ú(,))Ù(Ø()Ú

6

Таблица 1.1. Эквивалентные ПФ

 

Исходная ПФ

Эквивалентная ПФ

Вид закона

  • Ø(Ø)

 

 

®

  • ØÚ

 

«

(®)Ù(®)

 

  • Ø(Ù)
  • ØÚØ

Закон де Моргана

  • Ø(Ú)
  • ØÙØ

Закон де Моргана

Ù (Ú)

(Ù)Ú(Ù)

Закон дистрибутивности

Ú (Ù)

(Ú)Ù(Ú)

Закон дистрибутивности

Ú

Ú

Закон коммутативности

Ù

Ù

Закон коммутативности

(Ú)Ú

Ú(Ú)

Закон ассоциативности

(Ù)Ù

Ù (Ù)

Закон ассоциативности

®

  • Ø® Ø

Контрапозиционный закон

ÙØ

0

 

ÚØ

1

 

Ù0

0

 

Ù1

 

 

Ú 0

 

 

Ú 1

1

 

  • Ø($())

"(Ø())

 

  • Ø("())

$(Ø())

 

"(()Ù())

"()Ù"()

 

$(()Ú())

$()Ú$()

 

"()

"()

Закон немых переменных

$()

$()

Закон немых переменных

 

ÚØ(,)Ú()ÚØ(,(,))Ú(,))).

Если учесть, что все переменные в ПФ связаны, то кванторы общности относятся ко всей матрице и их можно опустить. Остается матрица. В ней коньюнкции  ПФ  можно    заменить    на    множество   ПФ (по    числу   символов коньюнкции плюс единица). Пример для последней формулы:

 

7

Ø()ÚØ(,)Ú(,)Ú(),

Ø()ÚØ(,)Ú()ÚØ(,(,))Ú(,).

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

Ø()ÚØ(,)Ú(,)Ú(),

Ø()ÚØ(,)Ú()ÚØ(,(,))Ú(,).

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

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

 

1.4. Унификация

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

Заменой (возможно использование и других символов)  называют   конечное   множество   упорядоченных   пар {|,…,|} = , где пара | означает, что переменная  заменяется термом . Применение  к   выражению   обозначают  как .  Пример:  =((),,),  =

= {|, |},  = {|, ()|}, = {|, ()|}. Тогда = =((),,), =((),,()), =((),,()).

Композицией двух замен  и  называется замена =o. Для этого:

1)  применяют  к термам в ;

2)  исключают из  пары | такие, что  являются переменной в ;

3)  собирают пары, полученные в пп.1, 2.

8

Пример: = {|,(,,)|},  = {|,|,()|,()|, ()|}. После выполнения п.1 находим = {|,(,(),)|}. Пункт  2  дает   =  {|,()|,()|}. Результатом п.3 является ={|,(,(),)|,|,()|,()|}. Очевидно, что применение к литералу последовательно замен  и  дает такой же результат, что и применение замены .

В общем случае o¹o. Композиция замен ассоциативна: (o)o=o(o).

Множество выражений {} = {} является унифицируемым, если существует такая замена (унификатор), что все  оказываются идентичными.     Пример:         =   {|,|,|,|,|,()|},

{} ={(,(),()),(,(),()),(,(),()),(,

(),)}. Для  имеем: =(,(),()),  = =(,(),()),… . Значит,  - унификатор.

Может существовать множество унификаторов  для {}. Простейшим унификатором  множества {} называют такой, что для любого  существует дополнительная замена  такая, что =o. Для последнего примера = {|,|,|,|,()|}, =o{|}.

 

1.5.  Принцип резолюций

 

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

Пусть имеются два конкретных предложения: 1Ú2Ú…Ú и Ø1Ú2Ú3Ú…Ú. Из них можно вывести новое предложение, называемое резольвентой, как дизъюнкция исходных предложений без дополняющих друг друга пар типа 1 и Ø1. Второй частный случай – пустое предложение:  и Ø – признак противоречия (пустая резольвента).

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

Недостатком формально-логической модели являются жесткие ограничения, свойственные всем формальным моделям.

 

9

2. ПРОДУКЦИОННАЯ МОДЕЛЬ

2.1. ОбщиЕ положения

Продукционная модель основана на  правилах продукции типа

Если < условие >, то < заключение >,

где “Если “, “то “ – операторы;

< условие > (анцедент) - это: посылка, утверждение, предшествующий, основание;

< заключение > (консеквент) - это: действие, следствие, последующий, гипотеза; генерируется при истинности условия.

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

Сложное продукционное правило может иметь одно заключительное суждение , являющееся следствием двух других исходных (силлогизм). Например, правило “отделения” (modus ponens):

Если ® истинно и истинно,  то истинно,

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

[Если , то и если , то ], то [если , то ].

Таблицы принятия решения. Эта форма (модель) представления множества продукционных правил. Пример: обработка деталей (табл. 2.1).

В таблице прочерк указывает на отсутствие необходимости таких сведений в условной части.

Пример использования таблицы принятия решений: если класс точности ³ 4 и класс чистоты £  6 и несоосность 0.01, то план обработки - П1 (условная часть содержит три посылки).

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

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

 

2.2. Прямой и обратный поиск

 

Поиск новых знаний в продукционных моделях может быть прямым и обратным.   Рассмотрим    указанные    методы   применительно   к   теории

10

Таблица 2.1. Таблица принятия решения

 

 

 


Операнд

 

Знак

1

2

3

4

5

6

Класс точности

³

4

2

2

1

3

1

Класс чистоты

£

6

8

8

9

12

12

Вид термооб-работки

=

-

01 или 02

03 или 04

-

01 или 02

-

Несоос-ность

³

0.01

0.02

0.01

0.01

-

-

План обработ-ки

 

 

П1

 

П2

 

П3

П4

 

П5

 

П6

 

 

предикатов.

Прямая дедукция: если , , …,,  - логические выражения, то  является логическим следствием из , , …, тогда и только тогда, когда логическое выражение ÙÙ…ÙÙØ тождественно ложно. Выводы применяют к фактам и правилам. Алгоритм завершает работу при достижении цели (прямая цепочка рассуждений – от фактов к целям).

Пример задачи по методу  “от фактов к цели”.

Факт 1: Иванов – преподаватель математического факультета (формализованная запись - преп.(матем.,иванов)).

Факт 2: Петрова – студентка факультета информатики (студ.(информ.,петрова)).

Правило 1: если  - преподаватель факультета  и  - студентка факультета  при <> (это неравенство есть добавочный неиндексированный факт), то  может быть экзаменатором для  ((преп.(,)Ùстуд.( , )ÙØравно(, ))®экзам.( , )).

Цель 1 (запрос): Может ли Иванов быть экзаменатором у Петровой (экзам.(иванов,петрова))?

Утвердительный ответ на поставленный вопрос  имеет вид следующей теоремы:

(факт1Ùфакт2Ùправило1)®цель1.

Доказательство теоремы сводится к доказательству истинности данного логического выражения. С помощью табл. 1.1  перепишем теорему как

  • Ø (факт1Ùфакт2Ùправило1)Úцель1.

Истинность этого выражения соответствует ложности следующего выражения:

11

(факт1Ùфакт2Ùправило1)ÙØцель1,

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

Этап 1. Преобразуем правило 1 в дизъюнкты с помощью табл.1.1:

  • Øпреп.( ,)ÚØстуд.( , )ÚØ( Øравно(, ))Úэкзам.( , ).

Рассмотрим далее два предложения – факт 1 и последнее правило 1. Применим к выделенным предложениям принцип резолюций. Заменив в найденной резольвенте переменные на известные константы, имеющиеся в факте 1, получим правило 2:

Øстуд.( , )Ú равно(матем., )Úэкзам.(иванов, ).

Этап 2. Аналогично вышеизложенному из факта 2 и правила 2 резолюцией получаем факт 3:

экзам.(иванов,петрова) Ú равно(матем.,информ.).

Так как  и - разные факультеты (этот факт отражен в правиле 1 неравенством <>), то равно(матем.,информ.)=Л (ложь) и в факте 3 остается факт 4: экзам.(иванов,петрова).

Этап 3. Поскольку цель1=экзам.(иванов,петрова), с получением факта 4 искомая цель разрешена. Очевидно, что методом резолюций были обработаны все предложения в части (факт1Ùфакт2Ùправило1) теоремы.  Заменив указанную часть на факт 4, получим вместо формулы (факт1Ùфакт2Ùправило1)ÙØцель1 выражение  факт4ÙØцель1= =экзам.(иванов,петрова)ÙØэкзам.(иванов,петрова), являющееся ложным. Теорема доказана.

Вывод факта 4 (подтверждение цели 1) соответствует фактическому завершению обработки исходных данных.

Если не пользоваться принципом резолюций, то на первом этапе доказательства теоремы согласно таблице 1.1 в формуле (факт1Ùфакт2Ùправило1)ÙØцель1 коньюнкция факт1Ùправило1 дает предложение факт1Ùправило2, на втором этапе вместо коньюнкции  факт2Ùправило2 получаем факт2Ùфакт4. В итоге оказывается (факт1Ùфакт2Ùправило1)ÙØцель1 = (факт1Ùфакт2Ùфакт4)ÙØцель1 = =преп.(матем.,иванов) Ù студ.(информ.,петрова) Ù экзам.(иванов, петрова)ÙØэкзам.(иванов,петрова)=Л (ложь), так как ложна последняя коньюнкция. Теорема доказана посредством  эквивалентных формул.

Обратная дедукция: если  , , …,,  - логические выражения, то  является логическим следствием из , , …, тогда и только тогда, когда логическое выражение ØÚØÚ…ÚØÚ тождественно истинно (общезначимо). Выводы применяют к цели  и правилам, чтобы получить новые частичные цели. Алгоритм завершает работу, когда все частичные цели приведут к тем или иным известным фактам (обратная цепочка рассуждений – от целей к фактам).

12

В системах обратной дедукции правила и цели преобразуют в коньюнкты, чтобы применить правило согласия, двойственное правилу резолюций. Применяя его к коньюнкциям Ù1 и ØÙ2, получают коньюнкцию 1Ù2. Докажем предыдущую теорему методом обратной дедукции. Для этого преобразуем с учетом табл. 1.1 ранее используемую формулу Ø(факт1Ùфакт2Ùправило1)Úцель1:

Øфакт1ÚØфакт2ÚØправило1Úцель1.

Последнее полностью соответствует теореме обратной дедукции. Вначале используем принцип резолюций.

Этап 1. Преобразуем часть Øправило1 к виду

преп.(,)Ùстуд.( , )ÙØ равно(, )ÙØэкзам.( , )

и подставим ее в последнюю формулу теоремы:

  • Øфакт1ÚØфакт2Ú(преп.(,)Ùстуд.( , )Ù

ÙØ равно(, )ÙØэкзам.( , ))Úцель1.

С учетом двойственности правила согласия правилу резолюций из  цели 1 и отрицания правила 1 выводим новую цель 2:

преп.(,иван.)Ùстуд.( ,петрова)ÙØ равно(, ),

где осуществлена замена переменных на известные константы цели 1.

Этап 2. Из цели 2 и отрицания факта 1 выводим цель 3:

студ.( ,петрова)ÙØравно(матем., ).

Этап 3. Из цели 3 и отрицания факта 2 находим факт 3:

  • Ø равно(матем.,информ.).

Получили известный (неиндексированный) факт и факт истинный. Теорема доказана.

Если следовать только правилам эквивалентных формул,  то на первом этапе доказательства теоремы дизъюнкция Øправило1Úцель1 дает предложение цель2Úцель1, на втором этапе имеем Øфакт1Úцель2=цель3Úцель2, на третьем этапе получаем Øфакт2Úцель3=факт3Úцель3. В итоге вместо Øфакт1ÚØфакт2Ú ÚØправило1Úцель1 оказывается факт3Úцель3Úцель2Úцель1=И (истинно), так как факт3=И. Теорема доказана.

Типичными представителями продукционной модели с прямым выводом знаний являются диагностические системы, а моделей с обратным поиском решения – системы проектирования.

 

2.3. Язык программирования PROLOG

2.3.1. общие положения

 

PROLOG (Пролог) – язык программирования, созданный специально для работы с базами знаний, основанными на фактах и правилах. В языке Пролог реализован механизм возврата для выполнения обратной цепочки рассуждений (от целей к фактам). При этом вначале предполагается, что некоторые выводы или заключения верны, а затем эти предположения проверяются. Если предположение не подтверждается, выполняется возврат в исходную точку (точка возврата - ТВ) и выдвигается новое предположение. Находятся все возможные решения. При необходимости число вариантов ответа ограничивается средствами языка.

 

13

2.3.2. Описание фактов

 

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

-          имена объектов (сущностей) и отношений состоят из латинских букв, цифр, знаков подчеркивания и начинаются со строчной буквы;

-          первым в предложении указывается имя отношения, за которым в скобках указываются имена объектов, разделяемых запятыми;

-          факт заканчивается точкой, порядок перечисления объектов в скобках произволен, но постоянен.

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

Аргументы могут быть представлены константами или переменными. Пример (для удобства чтения наряду с латинскими будем использовать русские буквы): вопрос “отец(виктор,X)” переводится как “отцом каких детей является Виктор?”. Для нахождения ответа просматриваются имена всех имеющихся в наличии объектов, отец которых – Виктор. Ответов может быть несколько, например: 1) X =таня, 2) X=оля.

Подвопросы в предложениях  отделяются запятыми (союз “и”). Примеры:

  1. нравится(виктор,анна),нравится (анна,виктор) – нравятся ли Виктор и Анна друг другу?.
  2. нравится(виктор,X),нравится(анна,X) – что нравится обоим – Виктору и Анне?.

Факты в программе на языке Пролог записываются в разделе clauses.              Пример программы на языке Пролог, содержащей факты:

domains

имя=symbol

predikates

отец(имя,имя)

муж(имя,имя)

clauses

отец(виктор,таня).

отец(виктор,оля).

отец(виктор,даша).

отец(владимир,виктор).

отец(владимир,сергей).

муж(виктор,анна).

муж(владимир,люда).

Здесь domains - определение аргументов, predikates - формат предикатов, clauses – факты и правила. На запрос отец(X,Y) Пролог отвечает в соответствии с принципом поиска всех решений:

X=виктор, Y=таня

X=виктор, Y=оля

14

X=виктор, Y=даша

X=владимир, Y=виктор

X=владимир, Y=сергей.

На запрос отец(виктор,Y) Пролог отвечает:

Y=таня

Y=оля

Y=даша.

На вопрос отец(виктор,владимир) Пролог отвечает:

False.

2.3.3. Описание правил

Правило формируется в том случае, если некоторый факт зависит от группы других фактов. Правило состоит из заголовка и тела. Они соединяются символом “:-” или “if” (если). Пример: предложение “Виктору нравится любой студент, которому нравится учеба” записывается как “нравится (виктор,X):-студент(X),нравится(X,учеба)”. Правило является в большинстве случаев более компактным и очевидным описанием, чем простое множество фактов, подчиняющееся данному правилу. Пример. Пусть имеется программа с базой знаний в виде группы фактов в разделе clauses:

отец(павел,юлия).

мать(юлия,михаил).

Для того чтобы узнать, кто является дедом Михаила по материнской линии, нужно задать вопрос: отец(X,Y),мать(Y,михаил). Ясно, что проще оформить запрос как дед(X,михаил). Тогда в программе нужно сформулировать соответствующее правило: дед(X,Y):-отец(X,Z), мать(Z,Y), которое читается как “X является дедом Y, если X является отцом Z, и Z является матерью Y”.

Факты правил сами могут быть раскрыты в виде правил. Рассмотрим следующую  программу, содержащую факты и правила:

domains

имя=symbol

predikates

отец(имя,имя)

супруг(имя,имя)

дед(имя,имя)

мать(имя,имя)

clauses

10 отец(андрей,алексей).

20 отец(федор,мария).

30 отец(алексей,лариса).

40 отец(алексей,владимир).

50 супруг(алексей,мария).

60 дед(X,Y):-

отец(X,Z),

отец(Z,Y).

70 дед(X,Y):-

15

отец(X,Z),

мать(Z,Y).

80 мать(X,Y):-

супруг(Z, X),

отец(Z, Y).

Один из фактов (подцель) правила 70 – “мать(Z,Y)”. Эта подцель при необходимости может быть решена в правиле 80. Для этого необходимо, чтобы Z стало X . Однако Z уже есть в правиле 80 и не должно смешиваться с Z подцели. Поэтому Пролог в процессе решения задачи автоматически переименовывает переменные правила 80: X1 вместо X, Y1 вместо Y, Z1 вместо Z, строя таблицу соответствия новых и старых переменных.

 

2.3.4. Интерпретатор Пролога

 

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

domains

имя=symbol

predikates

отец(имя,имя)

дед(имя,имя)

clauses

10 отец(алексей,владимир).

20 отец(андрей,алексей).

30 дед(X,Y):-

отец(X,Z),

отец(Z,Y).

Пусть задан вопрос: дед(X,Y). Он помещается в стек вопросов (целей) с состоянием

40 дед(X,Y).

В первом цикле интерпретатор просматривает сверху вниз пункты программы 10-30. Он пытается унифицировать первый литерал из стека  (в данном примере литерал всего один) с первыми литералами предложений 10-30. Только правило 30 в нашем примере может быть унифицировано с предложением 40. Перед унификацией интерпретатор переименовывает переменные в пункте 30: X®X1, Y®Y1, Z®Z1. Унификация предложений 40 и 30 требует замену: X вместо X1, Y вместо Y1. После унификации литерала из стека вопросов 40 и правила 30 содержимое стека замещается условной частью правила 30:

40отец(X,Z1),отец(Z1,Y).

16

Во втором цикле первый литерал в 40a  унифицируется с фактом 10: “алексей” заменяется X, а “владимир” - Z1. Таким образом, рассматриваемый литерал отец(X,Z1)=отец(алексей,владимир) соответствует факту 10, не содержит переменных (цель решена) и его можно удалить из стека. Тогда в стеке остается нерешенным второй литерал из 40a:

40отец(владимир,Y).

В третьем цикле предложение 40b  не унифицируется ни с одним из пунктов 10, 20, 30. Интерпретатор оказывается в тупике и возвращается к ближайшему состоянию 40a (точка возврата ТВ), из которого был начат последний процесс решения целей, для поиска других вариантов.

В четвертом цикле первый литерал в 40a  унифицируется уже со следующим после 10 фактом 20: “андрей ” заменяется на X, алексей ” на Z1. Литерал отец(X, Z1) становится конкретным фактом 20. Второй литерал из 40a остается в стеке вопросов:

40отец(алексей,Y).

В пятом цикле литерал 40c  унифицируется с фактом 10 и “владимир ” заменяется на Y. Цель разрешена. После удаления литерала отец(алексей,Y) из стека других целей в нем не оказывается. Найден вариант ответа:

X=андрей, Y=владимир.

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

Предикат “отсечение”. Специальное средство “!” позволяет обходить при возврате некоторые цели.

Пример запроса 1: отец(X,Y),!. Здесь две цели (два подвопроса). Пролог решает первую цель по первому подходящему факту и в соответствии с алгоритмом переходит ко второй цели, которая указывает, что невозможно возвращаться назад и процесс прекращается.

Пример запроса 2: цель1,цель2,!,цель3,цель4. Последовательно анализируется одна за другой четыре цели. При поиске решения в случае неудачи возвраты возможны только по цепочке 4-3, но не далее. Пример программы:

10 отец(a,b).

20 отец(b,c).

отец(c,d).

предок(X,Y):-

отец(X,Y).

предок(X,Y):-

отец(X,Z),

предок(Z,Y).

Запрос: отец(X,Y),!,отец(Y,Z). Интерпретатор решает первую цель и уже по факту 10 находит X=a, Y=b. Теперь необходимо удовлетворить вторую цель. Так как Y=b, то только  факт 20 унифицируется с этой целью: Z=c. Для поиска всех решений надо вернуться по цепочке целей стека вопросов к первой цели. Но перед ней стоит знак “!”. Возврат запрещен, хотя очевиден другой вариант: X=b, Y=c, Z=d . Таким образом, ответ следующий: X=a, Y=b, Z=c. Один вариант решения.

17

 

2.3.5. Операции

 

1.  Арифметические операции:  “+”,  “-”,  “*”,  “/”. Пример: расстояние1=расстояние2+расстояние3.

Порядок аргументов в выражениях значения не имеет.

2.  Функции: X mod Y – остаток от деления X на Y;

X div Y -  целая часть от деления X на Y;

abs(X) – абсолютная часть числа X;

exp(X) – e в степени X;

sgrt(X) – квадратный корень из X;

sin(X), cos(X), tg(X), arctg(X).

Приоритеты: 1) “+”,  “-“;  2) “*”,   “/”; 3) mod, div; 4) одноместные “+”,  “-“.

3.  Логические операции:

-          умножение – “,”,

-          сложение – “;”,

-          отрицание – “not” – предикат.

4.  Операции отношения: “>”,  “>=”,  “<”,  “<=”,  “=”,  “<>” или  “><”.

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

predicates

fact(real,real)

clauses

10 fact(1,1).

20 fact(X, Y):-

X>1,

Z=X-1,

fact(Z,X1),

Y=X*X1.

Запрос оформим как fact(5,X). Во время первого цикла решения задачи Пролог анализирует  стек вопросов, состояние которого есть сам запрос. Очевидно, что исходное предложение-запрос после сравнения его с фактом 10 и правилом 20 программы  может быть унифицировано только с правилом, так как в факте 10 первый аргумент “1” не соответствует первому аргументу “5” запроса. После унификации имеем для программного  правила X=5, Y=X. Далее стек вопросов должен быть обновлен  условной частью правила 20: X>1,Z=X--1,fact(Z,X1),Y=X*X1. Анализ составляющих стека с учетом предыдущих замен переменных дает: 5>1,Z=5-1=4, fact(4,X1),X=5*X1 или, после отбрасывания из стека конкретных фактов, fact(4,X1),X=5*X1.

18

Во втором цикле решения задачи первая цель из стека вновь унифицируется только с правилом программы, что приводит к замене в нем X на 4 и Y на X1 и т.д. В дальнейшем состояние стека обновляется только новыми значениями своих аргументов: fact(3,X1.1),X1=4*X1.1, где X1.1- новое значение аргумента X1 в fact(Z,X1); fact(2,X1.2),X1.1=3*X1.2; fact(1,X1.3),X1.2=2*X1.3. Новая первая цель  fact(1,X1.3) унифицируется уже с фактом программы, что дает X1.3=1. После отбрасывания полученного конкретного факта fact(1,1) стека, являющегося решением его первой цели fact(1,X1.3), в нем остается: X1.2=2*X1.3. Уравнение дает X1.2=2*1=2. Освобождение от указанного факта дает пустой стек. Последовательная подстановка X1.2, X1.1, X1 в соответствующие предыдущие состояния стека приводит к варианту ответа X=Y=120. Попытка найти другие решения задачи при унификации fact(1,X1.3) и правила программы приводит к замене в нем X=1, Y= X1.3 и к неудовлетворению неравенства X>1 условной части правила. Работа программы закончена.

 

2.3.6. Обработка списков и строк символов

 

Список в Прологе представляется множеством элементов, разделенных запятой и ограниченных квадратными скобками. Пример:

X=[a,b,c,d].

Для разделения списка на части используется предикат "½". Он делит список на "голову" и "хвост" (подсписок, являющийся исходным списком без элементов головы). Так, если 1) X=[a,b,c,d] и X=[Y½Z], то, например, Y=a (здесь в качестве головы берется только первый элемент исходного списка), Z=[b,c,d]; 2) X=[a] и X=[Y½Z], то Y=a, Z=[ ] - пустой подсписок.

Принадлежность элемента списку. Принадлежность элемента X списку Y записывается в виде предиката принадлежит(X,Y). Для определения истинности этого предиката вначале проверяется идентичность X и первого элемента списка Y. Если они совпадают, то можно записать: принадлежит (X,[X½_ ]), где "_" - анонимная переменная, соответствующая остальной части списка Y за вычетом его первого элемента, равного X. Если идентичности X и первого элемента списка Y нет, просматривается хвост “_” списка Y на предмет наличия в нем X, что оформляется как принадлежит [X,_½Z], где “_” – уже первый элемент списка Y, а  Z – остальная его часть-хвост. Поскольку анализ хвоста проводится вначале тоже путем проверки идентичности X и первого элемента подсписка Z, то можно записать правило: принадлежит [X,_½Z] :- принадлежит [X,Z]. Ясно, что программа приходит к решению первоначальной задачи: принадлежит(X,[X½_ ]), где “_” – соответствует списку Z за вычетом его первого элемента. Программа работы оказывается рекурсивной:

10 принадлежит(X,[X½_ ]).

20 принадлежит [X,_½Z] :-

принадлежит [X,Z].

Пример. Имеется запрос: принадлежит(седло,[руль,рама,колесо, седло]). Процедура поиска решения имеет следующий порядок.

Первый цикл. Унификация начального состояния стека вопросов (запроса) и факта 10 невозможна, так как требуется замена X=седло (первый аргумент в 10) и X =руль (голова списка [X½_ ]=[руль, рама,колесо, седло]). После унификации содержимого стека и правила 20 имеем: X=седло, [ _½Z]=[руль,рама,колесо,седло], т.е. “_”=[руль], Z=[рама,колесо, седло]. Содержимое стека обновляется: принадлежит(седло, [рама,колесо,седло]).

19

Второй цикл. Унификация последнего содержимого стека и факта 10 невозможна, так как седло¹рама. Унификация с предложением 20 дает X=седло, Z=[колесо,седло]. Новое содержимое стека: принадлежит(седло, [колесо,седло]).

Третий цикл. Унификация литерала принадлежит(седло, [колесо,седло]) с фактом 10 невозможна, так как седло¹колесо. Унификация  с правилом 20 дает: X=седло, Z=[седло]. Содержимое стека: принадлежит(седло,[седло]).

Четвертый цикл. Унификация последнего литерала с фактом 10 дает X=седло, “_”=[ ] и седло=седло. Вариант решения найден. Унификация с правилом 20 невозможна, так как в [ ] нет элемента седло. Таким образом, других решений нет.

Выбор общих элементов в двух списках. Выбор общих элементов  из двух списков X и Y сводится к поиску всех элементов Z, каждый из которых принадлежит как X , так и Y:

общий(X,Y,Z):-

принадлежит(Z,X),

принадлежит(Z,Y).

Выбор n-го элемента списка. Выбор n-го элемента E из какого-либо списка возможен  последовательным вычитанием n-1 первых элементов из этого списка с одновременным уменьшением  исходного числа N=n в счетчике С. Решение будет найдено, если элемент оставшегося частичного списка L будет первым :

10 n(1,E,[E ½_ ]).

20 n(N,E,[ _½L]):-

С=N-1,

n (С, E,L).

Пример. Имеем запрос: n(3,E,[a,b,c,d]), где E неизвестный аргумент.  Порядок поиска третьего элемента E в списке [a,b,c,d]) следующий.

Первый цикл. Исходное состояние стека вопросов: n(3,E,[a,b,c,d]). Унификация его с фактом 10 программы невозможна, так как 3¹1. Унификация с правилом 20 дает N=3, L=[b,c,d]. Новое состояние стека вопросов: n(2,E,[b,c,d]).

Второй цикл. Унификация литерала n(2,E,[b,c,d]) с фактом программы невозможна, так как 2¹1. Унификация с правилом 20 дает N=2, L=[c,d]. Новое состояние стека: n(1,E,[c,d]).

20

Третий цикл. Унификация литерала n(1,E,[c,d]) с фактом 10 дает E=c. Следовательно, последнее состояние стека становится равным n(1,c,[c,d]). Стек пустеет. Вариант решения E=c найден. Дополнительная унификация ближайшего состояния стека, содержащего  нерешенные цели (n(1,E,[c,d])) уже с правилом 20 ведет к последовательному сокращению  L до пустого списка и, соответственно, к окончанию работы программы. Таким образом, других решений нет.

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

10 append([ ],L,L).

20 append([X|L1],L2,[X|L3]):-

append(L1,L2,L3).

Пример. Введем  запрос: append([a,b.c],[d,e,f],L), где L – неизвестный искомый список. В первом цикле решения задачи, так как [a,b.c]¹[ ], унификация запроса (исходное состояние стека вопросов) возможна только с правилом 20: [X|L1]=[a,b.c] (т.е. X=a, L1=[b,c]), L2=[d,e,f], [X|L3]=L. Новое состояние стека вопросов: append=([b,c],[d,e,f],L3).

Во втором цикле унификация последнего предложения возможна также только с правилом 20. Вводя новые обозначения для  переменных, имеем: X=X.1=b, L1=L1.1=[c], L2=L2.1=[d,e,f], [X1|L3.1]=L3. Новое состояние стека: append=([c],[d,e,f],L3.1).

В третьем цикле аналогично изложенному получим X.2=c, L1.2=[ ], L2.2=[d,e,f], [X2|L3.2]=L3.1. Состояние стека: append=([ ],[d,e,f],L3.2).

В четвертом цикле последний литерал унифицируется с фактом 10 программы: L=[d,e,f] (второй аргумент) и L=L3.2 (третий аргумент). Следовательно, L3.2=[d,e,f] и состояние стека становится равным append=([ ],[d,e,f],[d,e,f]) – конкретный факт 10. Освобождаем стек и двигаемся по цепочке целей назад: L3.1=[X2|L3.2]=[c,d,e,f], L3=[X1|L3.1]=[b,c,d,e,f], L=[X|L3]=[a,b,c,d,e,f]. Исходное состояние стека становится конкретным фактом 10. Вариант ответа найден. Дополнительная унификация предпоследнего стекового литерала append=([ ],[d,e,f],L3.2) уже с правилом 20 невозможна, так как в данном литерале первый аргумент “[ ]” нельзя представить сочетанием головы и хвоста.

Данная программа позволяет решить обратную задачу: определить при известном списке одну из его частей: append(L,[d,e,f],[a,b,c,d,e,f]), где L – неизвестный присоединенный список. Последовательность поиска ответа такова.

Первый цикл. Унификация литерала append(L,[d,e,f],[a,b,c,d,e,f]) с фактом 10 - append([ ],L,L) - невозможна, так как [d,e,f]¹[a,b,c,d,e,f]. Унификация с правилом 20 дает [X|L1]=L, L2=[d,e,f], [X|L3]=[a,b,c,d,e,f], X=a, L3=[b,c,d,e,f]. Новое состояние стека: append=(L1,[d,e,f],[b,c,d,e,f]).

Второй цикл. Как и в первом цикле, с учетом переименования имеем: [X.1|L1.1]=L1, L2.1=[d,e,f], [X.1|L3.1]=[b,c,d,e,f], X.1=b, L3.1=[c,d,e,f]. Состояние стека: append=(L1.1,[d,e,f],[c,d,e,f]).

Третий цикл. Аналогично: [X.2|L1.2]=L1.1, L2.2=[d,e,f], [X.2|L3.2]=[c,d,e,f], X.2=c, L3.2=[d,e,f]. Состояние стека: append(L1.2,[d,e,f],[d,e,f]).

Четвертый цикл. Последний литерал унифицируется с фактом 10: [ ]= =L1.2. После унификации последнее состояние стека становится конкретным. Двигаемся назад по цепочке целей: L1.1=[ X.2|L1.2]=[c], L1=[X.1|L1.1]=[b,c], L=[X|L1]=[a,b,c]. Один вариант ответа найден. Дополнительная унификация литерала append(L1.2,[d,e,f],[d,e,f]) с правилом 20 невозможна, так как приведет к последовательному сокращению третьего списка в этом литерале и, в конце концов, к остановке работы интерпретатора.

21

Рассматриваемая база знаний дает возможность осуществить разложение списка на подсписки: append(L1,L2,[a,b,c,d,e,f]). Процедура поиска решений следующая.

Первый цикл. Унификация литерала append(L1,L2,[a,b,c,d,e,f]) с фактом 10 дает: [ ]=L1, L=L2, L=[a,b,c,d,e,f], т.е. L2=[a,b,c,d,e,f]. Один вариант ответа найден: L1=[ ], L2=[a,b,c,d,e,f].

Второй цикл. Возврат к стеку append(L1,L2,[a,b,c,d,e,f]). Унификация этого литерала уже с правилом 20 дает: [X|L1.1]=L1, L2.1=L2, [X|L3]=[a,b,c,d,e,f], X=[a], L3=[b,c,d,e,f]. Состояние стека вопросов: append(L1.1,L2.1,[b,c,d,e,f]).

Третий цикл. Унификация литерала append(L1.1,L2.1,[b,c,d,e,f]) с фактом 10 дает [ ]=L1.1, L=L2.1, L=[b,c,d,e,f], т.е. L2.1=[b,c,d,e,f]. Возврат по цепочке целей: L2.1=L2=[b,c,d,e,f], L1=[X|L1.1]=[a]. Найден второй вариант ответа: L1=[a], L2=[b,c,d,e,f].

Четвертый цикл. Возврат к стеку append(L1,L2,[a,b,c,d,e,f]). Поскольку все факты и правила просмотрены, увеличиваем длину головы до двух элементов. Унификация литерала append(L1,L2,[a,b,c,d,e,f]) с фактом 10 не дает новых решений. Унификация с правилом дает следующее: [X|L1.1]=L1, L2.1=L2, [X|L3]=[a,b,c,d,e,f]), т.е. X=[a,b], L3=[c,d,e,f]. Новое состояние стека: append(L1.1,L2.1,[c,d,e,f]).

Пятый цикл. Унификация литерала append(L1.1,L2.1,[c,d,e,f]) с фактом 10 дает: [ ]=L1.1, L=L2.1, L=[c,d,e,f], т.е. L2.1=[c,d,e,f]. Тогда в предыдущем состоянии стека L1=[X|L1.1]=[a,b], L2=L2.1=[c,d,e,f]. Найден второй вариант ответа и т. д. Последовательно увеличивая длину головы списка, находим все варианты ответов:

L1                                                          L2

[ ]                                                            [a,b,c,d]

[a]                                                          [b,c,d]

[a,b]                                                       [c,d]

[a,b,c]                                    [d]

[a,b,c,d]                                 [ ].

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

10 меньший([X],X).

20 меньший([X,Y|Z],R):-

X<=Y,

меньший([X|Z],R);

X>Y,

22

меньший([Y|Z],R).

Рассмотрим запрос: меньший([b,c,a,e],L), где Lнаименьший элемент в списке [b,c,a,e]. Процедура поиска элемента:

Первый этап. Унификация с 10 невозможна, так как [b,c,a,e] – список, а X – элемент. Унификация с 20 допустима при [X,Y|Z]=[b,c,a,e], R=L, т. е. X=b, Y=c, Z=[a,e], R=L. Новое состояние стека: b<=c,меньший([b|[a,e]],L) (слагаемое X>Y,меньший([Y|Z],R) правила 20 не учитывается вследствие ложности неравенства X>Y). Первое неравенство не требует доказательства, поэтому в стеке остается: меньший([b|[a,e]],L).

Второй этап. Унификация литерала меньший([b|[a,e]],L) с 10 невозможна. Унификация с 20 дает: [X.1,Y.1|Z.1]=[b|[a,e]], R=L.1, т.е. X.1=b, Y.1=a, Z.1=[e], R=L.1. Новое состояние стека: b>a, меньший([a|[e]],L.1). После удаления факта b>a в стеке остается: меньший([a|[e]],L.1).

Третий этап. Унификация последнего предложения с литералом 10 невозможна. Унификация с 20 дает: [X.2,Y.2|Z.2]=[a|[e]], R=L.2, т.е. X.2=a, Y.2=e, Z.2=[ ], R=L.2. Состояние стека, так как a<e, равно: меньший([a|[ ]],L.2).

Четвертый этап. Унификация литерала меньший([a|[ ]],L.2) с фактом 10 возможна при L.2=a. Возврат назад по цепочке целей к исходному  состоянию стека дает ответ: L=R=a. Других решений нет.

Выбор наибольшего элемента. Аналогичен предыдущему поиску при замене знаков неравенств “<”, “>” соответственно на “>” и “<”.

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

10 перевести([ ],[ ]).

20 перевести([С_А|Ф_А],[С_Р|Ф_Р]):-

словарь(С_А,С_Р),

перевести(Ф_А,Ф_Р).

40 словарь(“I”,”я”).

50 словарь(“study”,”изучаю”).

60 словарь(“language”,”язык”).

70 словарь(“PROLOG”,”Пролог”).

80 словарь(“in”,”в”).

90 словарь(“the university”,”университете”).

Здесь записано правило перевода 20: выбрать первое слово С_А английской фразы Ф_А, найти ему соответствующее русское слово С_Р в словаре и поставить в начало русского перевода Ф_Р. Введем запрос: перевести([“I”, ”study”, ”language”, ”PROLOG”, ”in”, ”the university”], P). .Процедура перевода:

Первый цикл. Унификация запроса с фактом 10 невозможна. Унификация с правилом 20 дает: [С_А|Ф_А]=[“I”,”study”, ”language”,”PROLOG”,”in”,”the university”], [С_Р|Ф_Р]=P, т.е. С_А=“I”, Ф_А=[”study”,”language”,”PROLOG”,”in”,”the university”]. Новое состояние стека вопросов: словарь=(“I”,Р), перевести([”study”,”language”, ”PROLOG”,”in”,”the university”],Ф_Р).

23

Второй цикл. Унификация литерала словарь=(“I”,Р) с фактом 40 дает: ”я”=Р. В стеке остается: перевести([”study”,”language”,”PROLOG”,”in”,”the university”],Ф_Р).

Третий цикл. Унификация стекового литерала возможна только с правилом 20: [С_А.1|Ф_А.1] = [”study”, ”language”, ”PROLOG”, ”in”, ”the university”], [С_Р.1|Ф_Р.1] = Ф_Р, т.е. С_А.1 = ”study”, Ф_А.1 = [”language”, ”PROLOG”, ”in” , ”the university”] и т.д. до исчерпания всех слов. При этом последнее состояние стека унифицируется с фактом 10. Возврат по цепочке целей назад увеличивает длину искомой переменной  P = =[С_Р|Ф_Р], Ф_Р=[С_Р.1|Ф_Р.1],… до следующей предельной величины: P= = [“я”, ”изучаю”, ”язык”, ”Пролог”, ”в”, “университете”]. Других решений нет.



 
используется для склеивания двух строк