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

описать следующие компоненты:

1)носитель – некоторую совокупность объектов (например, числа, геометрические фигуры, слова, множества и т.д.);

2)совокупность отношений (например, больше, меньше, равно и т.д.);

3)совокупность операций (например, сложение, умножение, пересечение

идр.);

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

Алгебраическая система, у которой отсутствуют операции ( F = ),

называется моделью или реляционной системой. Алгеброй называется алгебраическая система, у которой P = . Отношения в алгебрах, в отличие от моделей, определяются с помощью операций или представлены как операции. Например, решетка в теоретических работах представлена как алгебра, в которой отношение порядка ( ) задается с помощью операций inf (точная нижняя грань) и sup (точная верхняя грань): a b тогда и только тогда, когда inf(a, b) = a или sup(a, b) = b. Однако в прикладных исследованиях нередко отношения в таких алгебрах являются первичными или используются наряду с операциями. Например, при моделировании решеток используются сети или графы, и результаты операций inf и sup вычисляются с помощью операций на сетях. Любая алгебра (например, группа, кольцо, поле или булева алгебра) содержит, по крайней мере, одно отношение – равенство как запись результата выполнения операции.

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

ите же математические идеи.

В качестве примера моделей рассмотрим частично упорядоченные множества (ч.у.м., посеты, y-множества) <X, >, которые можно представить как частный случай графов, где для элементов носителя задано отношение

10

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

Формально отношение частичного порядка определяется как заданное на множестве X бинарное отношение со следующими свойствами:

1)рефлексивности: a a;

2)транзитивности: если a b и b c, то a c;

3)антисимметричности: из a b и b a следует a = b,

где a, b и c – произвольные элементы X.

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

Используя понятие частично упорядоченного множества, можно описать еще один фундаментальный класс алгебраических систем – решетки. Для этого введем несколько вспомогательных определений.

Пусть X – ч.у.м. с частичным порядком . Элемент x называется нижней гранью для a и b, если x a и x b. Аналогично, y называется верхней гранью для a и b, если a y и b y. Элемент x называется точной нижней гранью для a и b, если x – нижняя грань элементов a и b и для любой другой их нижней грани v выполняется v x. Обозначение: x = inf(a, b). Элемент y называется точной верхней гранью для a и b, если y – верхняя грань элементов a и b и для любой другой их верхней грани u выполняется y u. Обозначение: y = sup(a, b).

Решеткой называется ч.у.м. <X, >, для любых двух элементов a, b которого существует точная нижняя грань inf(a, b) X и точная верхняя грань sup(a, b) X.

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

11

Примечательно, что решетка может быть представлена и как "чистая" алгебра <B, , >, если положить, что a b = inf(a, b), a b = sup(a, b), а отношение заменить следующим образом: a b a b = a или a b = b (знак здесь означает "равносильно"). Далее приведем формальное определение решетки через операции , (в некоторых источниках эти операции обозначаются как и соответственно)

Алгебра <B, , >, где B – непустое множество элементов решетки, а, – двухместные операции (пересечение и объединение), называется решеткой, если для всех a, b, с из B выполняются следующие требования:

1)замкнутость: множество B содержит a b, a b;

2)свойства идемпотентности: a a = a, a a = a;

3)коммутативные законы: a b = b a, a b = b a;

4)ассоциативные законы: a (b с) = (a b) с,

a (b с) = (a b) с;

5) законы поглощения: a (a b) = a, a (a b) = a.

Решетка называется дистрибутивной, если соблюдается хотя бы один из следующих законов:

6) законы дистрибутивности: a (b с) = (a b) (a с), a (b с) = (a с) (a с).

Решетка называется ограниченной, если:

7) 0 B (нуль или нижняя грань решетки) и 1 B (единица или

верхняя грань решетки) такие, что для a B выполняется 0 a = 0, 1 a = 1, a 0 = a, a 1 = a.

Решетки сами по себе часто встречаются в разных прикладных задачах, но еще важнее то, что понятие решетки непосредственно приводит нас к понятию булевой алгебры, значение которой для основ современной двоичной

называется булевой алгеброй (булевой решеткой), если в B, помимо условий

1– 7, выполняются следующее условие:

8)Для каждого элемента a множество B содержит элемент a (дополнение

элемента a) такой, что a a = 1, a a = 0.

Другими словами, булева алгебра является дистрибутивной ограниченной

12

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

9)свойство совместимости: a b = a a b = b;

10)двойственность, законы де Моргана: a b = a b, a b = a b;

11)a = a;

12)0 = 1, 1 = 0;

В любой решетке можно естественным образом ввести частичный порядок. Положим по определению a b равносильно a b = a, что ввиду свойства 9 равносильно a b = b. Ниже приводятся решеточные свойства объединения и пересечения, а также некоторые другие свойства, использующие отношение :

13)a (a b), b (a b);

14)a c и b c, то (a b) c;

15)a b a, (a b) b;

16)c a и c b, то c (a b);

17)0 a, a 1;

18)закон контрапозиции: a b b a.

Большой список литературы по различным вариантам аксиоматических определений булевой алгебры приведен в [Сикорский, 1969].

К булевым алгебрам относятся:

1) алгебра множеств (алгебра Кантора, алгебра классов, алгебра подмножеств, алгебра частей множества) <P(M), , , >, причем M – верхняя грань, Ø – нижняя грань, – естественный частичный порядок, P(M) – булеан (множество всех подмножеств) множества M;

2) алгебра Буля (алгебра логики, алгебра высказываний, алгебра B2) <{0,1}, , , >, причем 1 – верхняя грань, 0 – нижняя грань.

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

Теорема (Стоуна). Всякая конечная булева алгебра B изоморфна алгебре множеств. [Столл, 1968].

С помощью булевых алгебр можно интерпретировать многие известные логические исчисления (системы). Так, например, алгебра множеств была

13

создана для обоснования силлогистики Аристотеля, а алгебра логики служит интерпретацией исчисления высказываний.

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

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

14