Методические указания для выполнения лабораторных работ по дисциплине «Базы данных и знаний»




НазваниеМетодические указания для выполнения лабораторных работ по дисциплине «Базы данных и знаний»
страница4/6
Дата публикации05.03.2013
Размер0.66 Mb.
ТипМетодические указания
skachate.ru > Экономика > Методические указания
1   2   3   4   5   6
^

2. ПРОГРАММЫ НА Прологе-Д -ЭТО ЛОГИЧНО




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



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

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

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

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

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

1.Примерами констант могут быть:

1, 2, 33, 14565 - числовые константы;

ав, АНТ25, ПРОЛОГ - литеральные константы.

2.Примерами переменных могут быть:

x, y, z, X, ы, Й.

3.Примерами функций могут быть:

автор(Толстой, Казаки), Сумма(2,3).

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

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

f(t 1,t 2,...,t n), (t 1,t 2,...,t n )  Dn

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

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

Более строго понятие предиката можно сформулировать следующим образом:

Предикат - это выражение вида P(t1,t2,...,tm),

где каждое ti - терм, а P - m-арный предикатный символ. Формально предикат P(t1,t2,...,tm) можно читать либо как "m - ка (t1,t2,...,tm) принадлежит отношению Р", либо как высказывание Р справедливо для m-ки (t1,t2,...,tm).

В логике имеется набор связок: &, , ¬, <- , <->, которые читаются как "и", "или", "не", "если", "тогда и только тогда", соответственно. Связки можно применить для образования логических формул, объединяя предикаты и другие формулы. Необходимо отметить, что логические связки:, &, , ¬, <- , <-> могут быть выражены друг через друга с помощью следующих соотношений, называемых формулами сокращения:
( A  B ) означает ¬ ( A <- B ),

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

( A <-> B ) означает ( A <- B )( B <- A ),
где А и В - суть формулы. Наряду со связками существуют кванторы общности () и существования (). Кванторы определяют пределы изменения переменных. Формула, стоящая после квантора называется областью действия этого квантора. Для кванторов тоже существуют формулы сокращения:
x А означает (¬(x (¬А))).
Примерами формул служат выражения:
мама(x, y)мама(y, z);

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

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

Таким образом, понятие формулы можно сформулировать таким образом:

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

С помощью этого понятия можно сформулировать понятие предложение:

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

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

В качестве примера предложения можно привести выражение:
бабушка(x, y)<-мама(x, z)мама(z, y).
Содержательно это предложение означает, что бабушка это мама мамы. Перед этим предложением стоят знаки кванторов общности по переменным x, y, z. Их присутствие означает, что формула выполнена для всех x, y, z.

Предложения, построенные в соответствии с введенными выше правилами образуют, язык логики первого порядка. В этом языке термы представляют собой объекты, а предикаты отношения между объектами. С помощью этого языка можно описать все задачи, решаемые на ЭВМ. На основе языка логики первого порядка можно построить различные языки логического программирования, различающиеся по правилам формирования предложения. Среди множества всевозможных предложений особое значение имеют предложения, содержащие связки "и" (  ) и одну связку "если" ( <- ). Такие предложения называются дизъюнктами. Более точное определение. Дизъюнкт - это предложение вида:
A1A2...Ak<-B1B2...Bn, (2.1)
где A1,A2,...,Ak,B1,B2,...,Bn - предикаты или литеры.

Особое значение для Пролога-Д имеет понятие дизъюнкта Хорна.

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

Если k = 0, то из формулы (1) получается дизъюнкт вида:
B1B2...Bn,
Этот дизъюнкт называется вопросом.

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

A1.
Если же n>0, дизъюнкт называется правилом:
A1<- B1B2...Bn,
где A - голова, а B1B2...Bn, - цели, образующие тело правила.

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

Введенные определения позволяют установить следующую иерархию:

формула



предложение



дизъюнкт



дизъюнкт Хорна
/   \
факт правило вопрос пустой

дизъюнкт
Рисунок 2.1.1. Иерархия определений.
Базой знаний будет называться всякое (непустое) множество фактов и правил.

Записанная в базе знаний информация представлена в некоторой формально - логической системе и предназначена для изучения информации посредством применения определенного процесса рассуждений, базирующегося на логическом выводе. Эти рассуждения основаны на понятии логического следствия. Известно, что логическое следствие из заданной совокупности допущений или предположений истинно, если истинны эти предположения. Однако одна и та же формула может быть истинной или ложной в зависимости от ее содержательного значения. Например, логическая формула:
(x>y)<-(|x|>|y|),
где знак x>y - означает отношение "x больше y", а знак |x| - абсолютную величину x, истинна, если x и y принадлежат множеству положительных чисел и ложна, если x и y принадлежат множеству отрицательных чисел. В математической логике существует понятие интерпретации, а в разных интерпретациях одна и та же формула может принимать разные значения.

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

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

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

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

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

Примером интерпретации для множества предложений, описывающих родственные отношения:
{мама(Саша, Оля), мама(Петя, Маша), сын(x, y)<-мама(y, x)}

являются следующие правила.
1. Область интерпретации D={Саша, Оля, Петя, Маша};

2. Функторы отсутствуют.

3. Отображение а). мама(x, y)->^ {ИСТИНА, ЛОЖЬ},

б). сын(x, y)->{ИСТИНА, ЛОЖЬ}.
Точное определение логического следствия, основано на понятии выполнимости формулы (предложения). Формула (предложение) выполняется в интерпретации над множеством D тогда и только тогда, когда это предложение в данной интерпретации принимает значение ИСТИНА. Соответственно множество предложений S выполняется в данной интерпретации тогда и только тогда, когда выполняется любое предложение из S. S логически влечет некоторое предложение s, тогда и только тогда, когда для любой интерпретации над любой областью D из выполнимости множества S следует выполнимость в ней s. Если вернуться к последнему примеру, то множество предложений:
S={мама(Саша, Оля), мама(Петя, Маша), сын(x, y)<-мама(y, x)}
логически влечет s =сын(Маша, Петя). Это обозначается S = s. 30
Смысл отношения = состоит в том, что если S = s, то это происходит из-за внутренней структуры предложений множества S, независимо оттого, что могут обозначать составляющие их части в той или иной интерпретации. Использование интерпретаций это один способ получения понятия логического следствия, которое, в конечном счете, не зависит от этих интерпретаций.

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

Пусть S - некоторое множество дизъюнктов и U - дизъюнкт. Необходимо определить является ли U логическим следствием из S. Для этого множество S дополняется отрицанием ¬U. Если окажется, что объединение множеств S и {¬U} противоречиво, то U логически следует из S.

Предположим, что даны два дизъюнкта C1 и C2 из S, а L1 и L2 - комплементарные литеры из C1 и C2 соответственно (литеры U и ¬U называются комплементарными). Дизъюнкция C1 и C2 (C1C2), в которой предварительно вычеркнуты литеры L1 и L2, называется резольвентой.

^ Принцип резолюции основан на том, что резольвента дизъюнктов C1 и C2 является логическим следствием C1 и C2. Если в результате многократного применения процесса построения резольвент получается пустой дизъюнкт, то множество дизъюнктов S противоречиво. Более того, для противоречивого множества дизъюнктов применениями процесса построения резольвент всегда можно получить пустой дизъюнкт (Л).

Иллюстрацией этого процесса может быть следующий пример.

Множество дизъюнктов S задано следующим образом:
P¬Q1¬Q2 (2.2)

P¬Q3 (2.3)

U¬Q3 (2.4)

U¬P¬R (2.5)

R (2.6)

Q1 (2.7)

Q3 (2.8)
Для доказательства того, что U является логическим следствием из S, к множеству S добавляется дизъюнкт
¬U. (2.9)
Тогда получаются резольвенты:
¬Q3 (2.10)
из (2.9) и (2.4), а:
Л - пустой дизъюнкт (2.11)
из (2.10) и (2.8.).

Следует отметить, что возможен и другой логический вывод.

В данном примере U логически следует из S.

Предположим, что в рассматриваемом примере дизъюнкт (2.9) и предложение (2.4) имеют вид:
¬U(F(a)) (2.9')

U(x)\/¬Q3(x) (2.4')
Не существует какой-либо литеры в (2.9'), комплементарной какой-либо литере в (2.4'). Однако, после подстановки в (4') вместо x - F(a), получается:
U(F(a))¬Q3(F(a)) (2.4'')
Теперь U(F(a)) и ¬U(F(a)) комплементарны друг другу. Следовательно, получается резольвента ¬Q3(F(a)). Следующее определение вводит понятие подстановки.

Подстановка - это конечное множество вида:
(t1/v1,...,tn/vn),
где vi - переменные, а ti - термы.

В приведенном примере (2.9'), (2.4') использована подстановка (F(a)/x).

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

Унификацией двух выражений Е1 и Е2 с переменными v1,...,vn (или без них) называется нахождение такой подстановки (может быть и пустой), что выражения Е1 и Е2 совпадут. Такая подстановка называется унификатором. Если оказалось, что для данных термов не существует унификатора, то термы не унифицируемы.

^

2. Процедурная семантика Пролога-Д или исполнение программы.


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

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

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

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

Сущность метода резолюций можно проиллюстрировать на примере
P<-Q1,Q2; (3.1.)

P<-Q3; (3.2.)

U<-Q3; (3.3.)

U<-P,R; (3.4.)

R; (3.5.)

Q1; (3.6.)

Q3; (3.7.)

?U; (3.8.),
где выражения (3.1.)-(3.4.)-представляют собой запись правил, а (3.5.) - (3.8.) - запись фактов. Все вместе это предложения базы знаний. Обратите внимание, что предложения (3.1.)-(3.8.) записаны в иной форме, чем предложения (2.2.)-(2.9.). Обе эти записи эквивалентны. Система Пролог-Д среди предложений(3.1.) - (3.8.) отыскивает первое по порядку вхождение U. В данной программе таковым оказывается предложение (3.3.). Далее делается попытка удовлетворить условия правила (3.3.). Для этого вновь просматриваются предложения базы знаний с целью поиска первого предложения, определяющего Q3. Таковым предложением оказывается формула (3.7.).

Так система находит первое решение. Отличительной особенностью системы Пролог-Д является то, что она автоматически отыскивает все возможные решения. В данном случае альтернативные решения получаются за счет правила (3.4.), в котором тоже определяется U. Приведенный процесс схематично иллюстрирует работу системы Пролог-Д, не затрагивая некоторые проблемы, например, влияние порядка предложений в базе знаний на результат работы программы, это будет более подробно рассмотрено в следующем разделе.
1   2   3   4   5   6

Похожие:

Методические указания для выполнения лабораторных работ по дисциплине «Базы данных и знаний» iconМетодические указания для выполнения лабораторных работ и курсового...
Лабораторная работа №1 «Построение структуры базы данных»
Методические указания для выполнения лабораторных работ по дисциплине «Базы данных и знаний» iconМетодические указания по выполнению лабораторных работ Дисциплина...
Методические указания предназначены для выполнения лабораторных работ по дисциплине «Программирование на языке высокого уровня» студентов...
Методические указания для выполнения лабораторных работ по дисциплине «Базы данных и знаний» iconС. А. Журова информационные технологии
Методические указания предназначены для выполнения лабораторных работ по курсам Информационные системы и Информационные технологии....
Методические указания для выполнения лабораторных работ по дисциплине «Базы данных и знаний» iconМетодические указания к выполнению лабораторных работ по дисциплине...
Методические указания к выполнению лабораторных работ по дисциплине «Системы автоматизированного проектирования в электроснабжении»...
Методические указания для выполнения лабораторных работ по дисциплине «Базы данных и знаний» iconМетодические указания по выполнению лабораторных работ для студентов...
Методические указания по выполнению лабораторных работ по дисциплине «Статистика» предназначены для всех специальностей
Методические указания для выполнения лабораторных работ по дисциплине «Базы данных и знаний» iconМетодические указания к проведению лабораторных работ. Специальность...
Методические указания предназначены для оказания методической помощи студентам 1-го курса при выполнение лабораторных работ по курсу...
Методические указания для выполнения лабораторных работ по дисциплине «Базы данных и знаний» iconМетодические рекомендации по выполнению лабораторных работ
Перечень тем теоретического курса, необходимых для выполнения лабораторных работ
Методические указания для выполнения лабораторных работ по дисциплине «Базы данных и знаний» iconРоссийской Федерации Московская финансово-юридическая академия Московский...
Методические указания предназначены для студентов специальности «Прикладная информатика в экономике» исодержат задания и указания,...
Методические указания для выполнения лабораторных работ по дисциплине «Базы данных и знаний» iconМетодические указания к выполнению контрольных работ по дисциплине...
Методические указания предназначены для студентов заочного отделения по направлению подготовки 051000. 62 Профессиональное обучение...
Методические указания для выполнения лабораторных работ по дисциплине «Базы данных и знаний» iconМетодические указания для выполнения контрольных работ по дисциплине «социология»
Задания и методические указания для выполнения контрольных работ по дисциплине «Социология» (гос – 2000, гос – 2005) для студентов...

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2014
контакты
skachate.ru
Главная страница