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

фирмы, или таблицы, отображающие дискретные (дискретизированные) функции либо отношения типа "больше", "предшествует", "является потомком" и т.д. Например, отношение "меньше" для множества {1, 2, 3} целых чисел можно представить как множество пар чисел {(1, 2), (1, 3), (2, 3)} или как табл. 1.11:

Таблица 1.11

В виде многоместных отношений можно представить многие предложения естественного языка. Например, предложение "Петров взял в библиотеке книгу Шолохова "Тихий Дон"" математически можно выразить как элемент (кортеж) отношения "Взятые в библиотеке книги" (ВК): ВК (Фамилия читателя, Автор книги, Название книги).

Способ представления текстов отношениями позволяет применять логический анализ с помощью средств и методов математической логики. При этом используется специальная терминология: имя отношения (в нашем примере ВК) и его структура (схема, т.е. число и состав атрибутов этого отношения) в математической логике называется предикатом. Более точно, предикатом является не само отношение, а отображение некоторого универсального отношения на множество {T, F} логических констант T (истинно) и F (ложно). Например, если универсум содержит пары (a, c), (a, d), (b, c) и (b, d), а отношение P – только две пары (a, c) и (b, c), то предикату P(x, y) соответствует табл. 1.12.

Таблица 1.12

Для моделирования и анализа многоместных отношений часто используется структура, которая называется "декартово произведение

60

множеств" (прямое произведение множеств). Дадим ее определение.

Пусть задана некоторая совокупность из n одинаковых или различных множеств X, Y, ..., Z. Тогда декартово произведение этих множеств есть совокупность всех возможных n-местных элементарных кортежей, у которых на первом месте стоит элемент множества X, на втором – элемент множества Y,

..., а на последнем – элемент множества Z. Декартово произведение множеств X, Y, ..., Z обозначается X Y ... Z.

Декартово произведение n одинаковых множеств X записывается как Xn. Для совокупности множеств, именованных одинаковыми символами с разными индексами (например, S1, S2, ..., Sn), используется символ многократного произведения , в этом случае декартово произведение S1 S2 ... Sn можно

n

записать как Si .

i 1

Рассмотрим несколько примеров декартовых произведений. Для двух множеств X = {a, b}, Y = {b, c} декартово произведение имеет вид:

X Y = {(a, b), (a, c), (b, b), (b, c)}.

Здесь множество X Y содержит пары элементов, у которых (в отличие от множеств) порядок строго определен (т.е. их нельзя менять местами). Чтобы отличить (упорядоченные) пары от множеств, их заключают не в фигурные, а в простые круглые скобки.

Исходные множества могут быть заданы непрерывными интервалами, в этом случае декартовым произведением является область, ограниченная соответствующим прямоугольником на плоскости. Например, на рис. 1.6 затемненный прямоугольник вместе со своими границами изображает декартово произведение отрезков AB и CD, находящихся на разных координатных осях. Отрезки можно представить как бесконечную совокупность точек. Каждая из точек имеет координату – действительное число, равное расстоянию от начала координат до этой точки. Тогда элементы декартова произведения – всевозможные пары чисел, которые обозначают координаты точек, расположенных на плоскости в пределах этого прямоугольника. Ясно, что число таких пар бесконечно.

61

Рис. 1.6. Декартово произведение отрезков

Возможны более сложные структуры, формируемые с помощью декартова произведения (рис. 1.7 и 1.8). На рис. 1.7 структурой из 4-х затемненных прямоугольников отображается декартово произведение множеств интервалов {AB, CD} {EF, GH}. На рис. 1.8 совокупность горизонтальных отрезков на координатной плоскости, обозначенных жирными линиями, изображает декартово произведение множества {AB, CD} отрезков одной координатной оси на множество {F, G, H} точек другой оси. Если в качестве элементов декартовых произведений использовать только точки (например, {A, B, C} {G, H}), то на плоскости само декартово произведение будет отображаться как множество точек. Аналогичные структуры можно строить не только на плоскости, но и в трехмерном, четырехмерном и т.д. пространствах.

Рис. 1.7. Декартово произведение интервалов

Рис. 1.8. Декартово произведение интервалов и точек

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

Если декартово произведение формируется из N конечных множеств, то

62

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

Определение 1.5. N-местным отношением называется подмножество элементарных кортежей некоторого декартова произведения из N множеств.

Например, отношение "меньше" на множестве чисел {1, 2, 3} (табл. 1.11) с точки зрения этого определения является подмножеством элементарных кортежей, выбранных из декартова произведения {1, 2, 3} {1, 2, 3}.

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

3 3 4 = 36 элементарных кортежей.

Приведем основные свойства декартовых произведений [Бурбаки, 1965]. Подробные сведения об этих свойствах и об их практическом применении содержатся также в [Мелихов, 1971].

1. Пересечение декартовых произведений.

Если даны декартовы произведения X1 X2 ... Xn и Y1 Y2 ... Yn, то их пересечение вычисляется как:

(X1 X2 ... Xn) (Y1 Y2 ... Yn)=(X1 Y1) (X2 Y2) ... (Xn Yn).

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

{a, c, d} {b, c} {b, c, f} и {a, b, c, d} {a, c, d} {b, c, d}.

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

63

({a, c, d} {b, c} {b, c, f}) ({a, b, c, d} {a, c, d} {b, c, d}) =

=({a, c, d} {a, b, c, d}) ({b, c} {a, c, d}) ({b, c, f} {b, c, d}) =

={a, c, d} {c} {b, c}.

Нетрудно убедиться, что результат пересечения содержит 6 элементарных кортежей:

(a, c, b); (a, c, c); (c, c, b); (с, c, c); (d, c, b); (d, c, c).

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

2. Пустое декартово произведение

Если при вычислении пересечения декартовых произведений окажется, что

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

{a, c, d} {b, c} {b, c, f} {a, b, d} {a, d} {b, c, d} = {a, d} {b, c} = .

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

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

3. Проверка включения декартовых произведений

Если при сравнении двух декартовых произведений

A = (X1 X2 ... Xn) и B = (Y1 Y2 ... Yn)

окажется, что для всех "мест" соблюдаются соотношения

(X1 Y1), (X2 Y2),..., (Xn Yn),

то справедливо A B, т.е. все элементарные кортежи декартова произведения A обязательно принадлежат также и декартову произведению B. В противном случае отношение A B не соблюдается. Например, если заданы два

64