РАЗДЕЛ 2
МОДЕЛИ ПРЕДСТАВЛЕНИЯ ЗНАНИЙ В ДБД
2.1. Элементы логико-предикативных моделей
Введем три бесконечных алфавита Var, Const и Pred. Все элементы Var являются строками алфавитно-цифровых символов, которые начинаются с прописной буквы. Const содержит множество строк, начинающихся со строчной буквы или с цифры. Множество строк, которые начинаются со строчной буквы, задают алфавит Pred. Var, Const и Pred определяют, соответственно, множество имен переменных, констант, и имен предикатов. Заметим, что Const ? Pred ? ?, однако по контексту программы Дейталога всегда ясно, что имеет место - либо константа, либо имя предиката.
Алфавит Pred разделен на два непересекающихся подмножества ЕPred и IPred. Элементы ЕPred определяют множество имен экстенсиональных (заранее заданных) предикатов, а элементы IPred - множество имен интенсиональных (вычисляемых) предикатов.
Как отмечалось, в чистом Дейталоге допускаются только простые, не содержащие функциональных символов, термы. Таким образом, терм в чистом Дейталоге представляет собой константу или переменную; множество термов Term есть объединение множеств Var и Const. Терм называют основным, если он включает в себя только константы. Множество всех основных термов совпадает с множеством Const. Это множество называют универсумом Эрбрана.
Атом p(t1,...,tn) состоит из n-арного предикатного символа p и списка аргументов (t1,...,tn), где каждый ti есть терм. Основным атомом называется атом, у которого все аргументы являются основными термами. Литералом называется атом p(t1, ..., tn) или его отрицание - ?p(t1, ..., tn). Основным литералом называется основной атом или отрицание основного атома. Литерал называется отрицательным, если он содержит атом с отрицанием.
Подстановкой ? называется конечное множество вида {X1/t1, ..., Xn/tn}, где все переменные Xi различны и каждый терм ti таков, что Xi ? ti. Если ? - подстановка и t - терм, то t? есть ti, если t/ti ? ?, или t, если t/ti ? ?. Подстановка называется основной, если все термы t1,..., tn являются константами. Если L - литерал, то L? обозначает литерал, где каждый терм ti заменен ti?. Например,
L = ?p(a, X, Y, b), ? = {X/c, Y/X}, L? = ?p(a, c, X, b).
Если для пары литералов L и M существует подстановка ? и L? = M?, то говорят, что L и M унифицируемы, а ? называют унификатором. Очевидно, два литерала могут иметь сколь угодно много подстановок. Заметим, что унифицироваться могут только литералы с одинаковыми предикатными символами, и с одинаковой арностью.
Пусть ? = {X1/t1, ..., Xn/tn} и ? = {Y1/u1, ..., Ym/um} подстановки. Композиция подстановок ?? получается из множества
{X1/t1?, ..., Xn/tn?, Y1/u1, ..., Ym/um}
исключением всех элементов, для которых Xi = Yj. Отметим, что композиция подстановок ассоциативна, но не коммутативна.
Подстановка ? называется более общей по отношению к подстановке ? тогда и только тогда, когда существует такая подстановка ?, что ?? = ?. Пусть L и M - литералы; наиболее общим унификатором (НОУ) L и M называется более общий по отношению ко всем прочим унификатор. Алгоритм поиска НОУ двух литералов приведен в [86, 87].
Дизъюнктом называется конечный список литералов. Дизъюнкты отображаются во множественной нотации, например,
{ ?p(X, Y), q(X, Y) }.
Отметим, что в отличие от множества элементы дизъюнкта могут дублироваться.
Основной дизъюнкт не содержит переменных в своих литералах. Если дизъюнкт состоит из одного литерала, то его называют простым. Дизъюнкт называется отрицательным, если он содержит только отрицательные литералы. Если дизъюнкт состоит только из положительных литералов, то его называют положительным.
Если C = {L1,...,Ln} - дизъюнкт, то C? = {L1?,...,Ln?}. Если C и D - дизъюнкты и ? такая подстановка, что C? = D, то D называют экземпляром C. Например, p(X, a) есть экземпляр p(X, Y) с подстановкой {Y/a}.
Множество всех положительных основных простых дизъюнктов, которые могут быть образованы с использованием предикатных символов из Pred и констант из Const, называют базисом Эрбрана и обозначают через HB. Экстенсиональная часть базиса Эрбрана записывается как ЕHB, интенсиональная часть записывается как IHB. Конечное подмножество ЕHB называют экстенсиональной базой данных, и обозначают EDB. Интенсиональная база данных IDB есть конечное подножество IHB.
Программа ДБД состоит из конечного множества дизъюнктов. Язык ДБД определяет класс допускаемых в программе дизъюнктов. В программе чистого Дейталога используются дизъюнкты хорновского класса, т.е. дизъюнкты, имеющие не более одного положительного литерала:
1. Положительные простые дизъюнкты, которые иначе называются фактами, например, {p(X, b)}, {q(c, d)}. Факт называют основным, если он не содержит переменных. Чистый Дейталог допускает использование только основных фактов.
2. Дизъюнкты с одним положительным литералом и, по крайней мере, с одним отрицательным литералом, например, {p(X), ?q(X)}. Такие дизъюнкты называют правилами.
3. Отрицательные дизъюнкты или цели, например, {?q(X)}. Цель, состоящая из одного отрицательного литерала, называется простой.
Дизъюнкт легко преобразовать в формулу логики предикатов первого порядка, пользуясь следующими правилами:
1) все переменные дизъюнкта связываются квантором всеобщности;
2) литералы дизъюнкта объединяются в одну формулу с помощью дизъюнкции.
Нетрудно видеть, что факты являются атомарными формулами, а правила - импликациями.
Множеству дизъюнктов {C1, C2, ..., Cn} соответствует формула логики предикатов первого порядка
C?1 ? C?2 ? ... ? C?n,
где C?i - логическая формула для Ci.
Таким образом, программе Дейталога соответствует формула логики предикатов, представленная в виде КНФ. Общеизвестно, что любая логическая формула может быть представлена в виде КНФ. Форма, в которой каждая дизъюнкция КНФ представлена отдельно, называется клаузальн