Материал: Алгебра_кортежей

одним из авторов программы. После вычисления по формуле R = A \G B получим C-систему:

В верхней строке для облегчения анализа записаны имена атрибутов. Рассмотрим, как применить полученную структуру для поиска вариантов Ri и абдуктивного заключения Hi (шаги 2 и 3 алгоритма). Для этого пригодны методы, представленные в подразделе 4.2.

Сформируем набор неполных проекций в R. В данном примере такими проекциями являются: [X1], [X4], [X5], [X7], [X8], [X9], [X10], [X2X3X6]. Выбранные проекции позволяют легко находить АК-объекты Ri и соответствующие им логические формулы. Выберем проекцию [X1X9]. После сокращений она будет равна C-кортежу R[X1X9] = [{1} {0}]. Используя алгоритм вывода произвольных следствий из п.4.2, можно сформировать следующие формулы для Ri:

1)x1 x9 (соответствует C-кортежу Ri);

2)(x1 x9) ( x1 x9);

3)x1 x9 (формулы 2 и 3 соответствуют АК-объектам, которые

покрывают C-кортеж Ri) и т.д.

формуле x2 x3 x6 . Отрицание этой формулы равно x2 x3 x6 , оно подходит в качестве абдуктивного заключения.

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

Пусть А – некоторое искомое высказывание, В – "путешественник сброшен со скалы", С – "путешественник растерзан львами". Запишем посылки на языке исчисления высказываний:

155

1.А В = A В.

2.A С = A C.

Полученные высказывания можно представить как D-систему:

Первая из них означает эквивалентность высказываний А и B, а вторая – А и С. Следовательно, путешественнику нужно сказать либо фразу: "Меня не сбросят со скалы", либо фразу "Меня растерзают львы".

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

156

Глава 5. Управление данными и знаниями на базе алгебры кортежей

В каждой естественной науке заключено столько истины, сколько в ней есть математики.

Иммануил Кант.

Теоретические возможности алгебраического подхода, описанные в предшествующих главах, дают перспективные результаты в различных сферах обработки информации. Ниже представлены некоторые рассмотренные к настоящему времени приложения АК. Вначале освещены вопросы метризации операций с АК-объектами и их применение в вероятностных пространствах. Затем показаны АК-ориентированные способы управления данными и знаниями в современных программных системах: реляционных и дедуктивных СУБД, прикладных системах искусственного интеллекта, использующих семантические сети, аппарат формального анализа понятий, а также в поисковых системах. Изложения тем существенно отличаются друг от друга по степени завершенности, но авторы посчитали целесообразным привести их в книге для иллюстрации широты диапазона применения АК и приглашения исследователей, работающих в перечисленных и других предметных областях, к использованию алгебры кортежей для решения своих профессиональных проблем.

5.1.Метрические аспекты алгебры кортежей

5.1.1.Представление измеримых систем в алгебре кортежей

Понятие меры (A) множества A является естественным обобщением

следующих понятий [Колмогоров, 1972]:

1)длины отрезка;

2)площади плоской фигуры;

3)объема пространственной фигуры;

4)приращения f(b) – f(a) неубывающей функции f(t) на полуинтервале [a,b);

5)интеграла от неотрицательной функции по некоторой линейной, плоской или пространственной области.

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

157

В качестве первой из них возьмем такую меру дискретных множеств, как количество элементов. Эту меру в теории множеств принято называть мощностью множеств, но всеми свойствами меры (о них далее) обладают только мощности конечных множеств. Мощность множества A обозначается как A (см. п.1.4).

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

элементов возрастающего ряда универсума, n(A) – количество элементов множества A, изменяющееся по мере возрастания U. Например, если U – натуральный ряд, а A – множество чисел, кратных 3, то можно доказать, что относительная мощность A стремится к 1/3. Эта мера имеет много общих свойств с вероятностной мерой и легко может быть определена во многих случаях и для бесконечных подмножеств бесконечного множества. Например, относительная мощность подмножества четных чисел во множестве всех чисел натурального ряда равна 1/2, а относительная мощность всех чисел, кратных конечному целому числу k, равна 1/k. Разумеется, с помощью относительной мощности различимы далеко не все подмножества счетных бесконечных множеств. Так, меру 0 имеют все конечные подмножества счетного множества и некоторые бесконечные множества, например, множество квадратов целых чисел. Для бесконечных подмножеств счетного множества, имеющих нулевую меру, можно использовать асимптотическую меру, т.е. аналитическую функцию, стремящуюся к нулю по мере возрастания ряда чисел, но имеющую конечное значение на конечном отрезке.

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

158

Аксиомы меры множеств:

1)мера есть действительное неотрицательное число;

2)если A B = , то (A B) = (A) + (B);

3)для произвольных множеств A и B

(A B) = (A) + (B) (A B).

В качестве примера рассмотрим систему, универсум которой бесконечное множество N положительных целых чисел. Ее подмножества есть числа, кратные каким-то целым конечным числам k. Обозначим такие подмножества Nk. Ясно, что относительная мощность универсума этой системы равна 1, а относительная мощность каждого из множеств Nk равна 1/k. Предположим, нам необходимо определить относительную мощность подмножества, содержащего объединение всех чисел, кратных 2 (N2), и чисел, кратных 3 (N3). Из свойств меры множеств очевидно, что

(N2 N3) = (N2) + (N3) (N2 N3).

Ясно, что N2 N3 представляет собой множество чисел, кратных 6, поэтому (N2 N3) = 1/6. Отсюда

(N2 N3) = 12 13 16 23.

В более общем случае:

(Nm Nk)= m1 1k R(m1,k) ,

где R(m, k) – наименьшее общее кратное чисел m и k.

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

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

159