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

качестве аксиомы, что мера каждого вырожденного элементарного интервала равна 0. Значит, при подсчете меры произвольного интервала достаточно учитывать только меры невырожденных элементарных интервалов.

В пространствах с мерой [Халмош, 1953] много трудностей связано с необходимостью соблюдения трех требований:

1)пересечение любых измеримых объектов должно принадлежать к классу измеримых объектов;

2)возможность представить любой объект как объединение непересекающихся объектов;

3)объединение всех измеримых объектов пространства должно быть в точности равно самому этому пространству, т.е. не должно быть при этом никаких пропусков, например, некоторых точек.

Для соблюдения первого требования традиционно [Колмогоров, 1972; Халмош, 1953] выбираются интервалы одного типа, например, только открытые или только полуоткрытые. Если взяты открытые интервалы, то не выполняется третье требование, поскольку точки при этом не учитываются. Если задать только замкнутые интервалы, то не удовлетворяется второе требование (сопряженные замкнутые интервалы имеют общую точку). Иногда применяют полуоткрытые интервалы [Халмош, 1953], но на практике это связано с определенными трудностями, и они используются редко. В то же время, если объединить в один класс открытые интервалы (пустой интервал тоже принадлежит этому классу) и добавить к ним вырожденные непустые интервалы с нулевой мерой (в одномерном пространстве – точки), то можно легко построить систему, в которой все три требования выполняются.

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

160

описанных структур на плоскости (рис. 5.1).

Пусть в двумерном пространстве XY заданы интервалы, ограниченные точками a, b, ..., h на атрибуте Y и точками i, j, ..., p на атрибуте X. В качестве базовых примем следующие открытые интервалы:

на оси Y: (a, c); (b, d); (e, g); (f, h); на оси X: (i, k); (j, l); (m, o); (n, p).

Рис. 5.1. Система брусов на плоскости

Систему S из 8-ми замкнутых брусов, изображенных на рис. 5.1, можно записать как объединение двух C-кортежей (или C-систему) в пространстве XY:

В системах с вырожденными интервалами соблюдаются все приведенные выше требования пространств с мерой, и в то же время имеется возможность преобразования их в систему с однородными элементами.

Каждая компонента системы S есть совокупность открытых интервалов и точек, представимая как совокупность замкнутых интервалов. Их декартово произведение дает уже систему замкнутых прямоугольников, изображенных на рис. 5.1. Извлекая из нее все точки, выделяем систему S1 открытых брусов:

В системах S и S1, где интервалы, формирующие компоненты, не пересекаются, сравнительно легко определяется мера каждого C-кортежа, исходя из свойств декартовых произведений (см. п. 1.4). Например, систему S1 можно представить как объединение двух C-кортежей C1 и C2. Для C-кортежа

161

C1 = [{(a, c), (e, g)} {(i, k), (n, p)}]

(C1) = ( ((a, c)) + ((e, g))) ( ((i, k)) + ((n, p))).

Однако в более общем случае, когда компоненты C-кортежей состоят из пересекающихся интервалов, вычисление меры сильно затрудняется. Подобная ситуация возникает при необходимости вычислить меру С-системы на основе известных мер входящих в нее С-кортежей, имеющих непустые пересечения друг с другом. Тогда при вычислениях приходится вносить поправки, и система существенно усложняется. На рис. 5.1 пересечение двух C-кортежей, из которых состоит C-система S (или S1), представлено в виде четырех малых прямоугольников, являющихся пересечением соответствующих пар больших прямоугольников. Вычисляя меру объединения этих же C-кортежей необходимо учитывать, что их пересечение непусто, и вводить соответствующие поправки. Для простых систем типа изображенной на рис. 5.1 можно при этом опираться на пространственное воображение. В более сложных системах с большим числом брусов в пространстве, имеющем большое число атрибутов, требуются более мощные формальные методы вычисления меры. Такие методы разработаны в алгебре кортежей, к ним, в частности, относится ортогонализация и метод квантования интервалов, к описанию которого мы и переходим.

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

Пусть область определения некоторого атрибута есть замкнутый интервална числовой оси и задано конечное множество E = {Ei} замкнутых интервалов таких, что Ei . На числовой оси границы интервалов представлены множествами координат начальных и конечных точек. Если эти координаты расположить в порядке возрастания, то получим разбиение системы интервалов на кванты, т.е. точки и открытые интервалы. Ясно, что при этом интервал разбивается на некоторое комбинированное множество,

162

содержащее m открытых интервалов и m + 1 изолированных точек, из которых две являются концевыми точками интервала .

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

Пример процедуры квантования для четырех интервалов E1, E2, E3, E4, показан на рис. 5.2. Для наглядности интервалы Ei вынесены за пределы координатной оси.

Рис. 5.2. Квантование системы интервалов

Здесь интервал , ограниченный точками P и Q, содержит внутренние точки a, b, ..., h. Соответственно каждый интервал Ei может быть представлен множеством квантов, например, замкнутый интервал E3 включает точки и открытые интервалы: E3 = {c, d, e, f, (c, d), (d, e), (e, f)}. Если нас интересуют только метрические свойства описываемых объектов, то E3 можно представить как множество {(c, d), (d, e), (e, f)} открытых непересекающихся интервалов. После аналогичного квантования в каждом измеримом атрибуте метрическое пространство преобразуется в АК-объект, его компоненты – обычные множества, содержащие открытые интервалы и точки.

Дадим некоторые определения.

Несовместными называются интервалы при условии, что их пересечение пусто или характеризуется нулевой мерой.

Например, замкнутые интервалы [c, d] и [d, e] из приведенного выше примера имеют непустое пересечение (точка d), но представляют несовместную пару, поскольку их пересечение имеет меру 0.

Элементаризация (квантование) непрерывного или дискретнонепрерывного пространства есть изоморфное преобразование систем интервалов каждого непрерывного атрибута в системы попарно несовместных интервалов.

При преобразовании произвольной системы интервалов ( , E) отдельного атрибута в элементарную систему интервалов ( , F), где E = {Ei} – множество

163

исходных интервалов, а F = {Fr} – множество квантов, для любого Ei соблюдается соотношение

Ei = Fk ,

k

где Fk – некоторые кванты из F. Причем мера для исходного интервала Ei вычисляется по формуле (в силу аддитивности меры):

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

Теорема 5.1. Если каждая компонента C-кортежа имеет конечную меру, то мерой C-кортежа является произведение мер его компонент.

Доказательство. Для доказательства достаточно рассмотреть C-кортеж, состоящий из двух компонент. Случай, когда каждая из компонент состоит из единственного непрерывного интервала, тривиален, так как здесь утверждение теоремы непосредственно следует из метрических свойств декартового произведения. Рассмотрим случай, когда каждая компонента представляет собой объединение конечного числа интервалов. Тогда, применив МКИ, преобразуем системы E1 и E2 интервалов в каждом атрибуте в конечные системы F1 и F2 открытых элементарных интервалов. Таким образом, C-кортеж равен декартову произведению F1 F2. Ясно, что каждый элемент (F1i, F2j) этого декартова произведения представлен открытым прямоугольником Gij с мерой (Gij) = (F1i) (F2j). Поскольку все Gij попарно не пересекаются, то

число атрибутов, доказывается аналогично, при этом структура пространственных элементарных объектов (точки, линии, k-мерные брусы) определяется числом непрерывных атрибутов. Конец доказательства.

164