1.4. Тождества алгебры множеств

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

- дистрибутивность (анг. distribution – распределение, размещение):

(АВ)С=(АВ)(ВС); (АВ)С=(АВ)(ВС);

- ассоциативность:

(АВ)С=А(ВС)=АВС; (АВ)С=А(ВС)=АВС;

- закон де Моргана:

, ,

, (A\В)\С=(А\С)\(В\С), А(В\С)=(АВ)\(АС).

Доказательство справедливости перечисленных выше множеств легко просматривается на геометрической иллюстрации с помощью диаграмм Эйлера – Венна.

1.5. Прямое произведение и проекция множеств

Упорядоченное множество называют кортежом (фр. cortege – торжественное шествие, выезд). Кортеж - последовательность элементов, в которой каждый элемент занимает определенное место. Элементы кортежа называются компонентами. Число элементов кортежа называется его длиной. Множество А=(а₁,а₂,…,а_n) является кортежом длины n с компонентами а₁,а₂,…,а_n. Понятие кортежа соответствует известному понятию вектора. Кортежи длины n называют n-ми, а пустой кортеж длины ноль обозначается ( ) или . В отличие от обычного множества в кортеже могут быть одинаковые элементы.

Кортеж длины три (а₁,а₂,а₃) рассматривается как точка в трехмерном пространстве (рис. 1.6), а его проекции на соответствующие плоскости образуют кортежи длины два (двойки) – (а₁,а₂), (а₁,а₃), (а₂,а₃), т.е.

Пр₁₂(а₁,а₂,а₃) = (а₁,а₂); Пр₁₃(а₁,а₂,а₃)=(а₁,а₃); Пр₂₃(а₁,а₂,а₃)=(а₂,а₃);

Рис. 1.6

Для n-мерного пространства проекция кортежа длины n на оси i, j,…, k определится как Пр_{i, j,…,k}(а₁,а₂,…,а_n)=(а_i,а_j,…,а_k), где 1  i < j <…< k  n.

Прямым произведением множеств А и В является множество С (С=АВ), содержащее упорядоченные пары (двойки, кортежи длины два), первая компонента каждой из которых принадлежит множеству А, а вторая - множеству В. Прямое произведение множеств А и В запишется в виде выражения: С=АВ={(а, в)аА, вВ}.

Истинно высказывание: (а, в)АВаА & вВ. Например, дано А=(а₁, а₂, а₃) и В=(в₁, в₂), тогда С=АВ={(а₁,в₁),(а₁,в₂),(а₂,в₁),(а₂,в₂),(а₃,в₁),(а₃,в₂)}.

Подмножества множества С=АВ называют еще графиками.

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

Если имеется n множеств А₁,А₂,…,А_n, то их прямым произведением называется множество С=А₁А₂…А_n, состоящее из таких кортежей длины n, первая компонента каждого из которых принадлежит множеству А₁, вторая – множеству А₂,…, _n-я компонента принадлежит множеству А_n. Для произвольной _n-ки (а₁,а₂,…,а_n), принадлежащей прямому произведению множеств С=А₁А₂…А_n, причем а₁А₁, а₂А₂,…, а_nА_n, истинно высказывание (а₁,а₂,…,а_n)А₁А₂…А_nа₁А₁, а₂А₂,…, а_nА_n.

Если определить прямое произведение одного и того же множества А r раз, то мы получим множество С, которое явится r–й степенью множества А. Формально это будет записано в виде: С=А^r=АА…А.

Определим также, что А₀={}.

Пусть А – произвольное множество. Подмножество АА² называется диагональю множества А, если оно состоит из пар вида (а,а), где аА. Если А=(а₁,а₂,а₃), то А={(а₁,а₁), (а₂,а₂), (а₃,а₃)}.

Определим операцию проектирования множества. Пусть А – множество, состоящее из кортежей длины r. Тогда проекцией множества А будет называться множество проекций кортежей из множества А.

Рассмотрим пример. Пусть множество А состоит из трех троек

,

причем каждой тройке соответствует точка в трехмерном пространстве. Тогда проекции множества А на оси 1,2 и 3 определятся множествами Пр₁А= , Пр₂А= , Пр₃А= . Если обозначить Пр₁А=А₁, Пр₂А=А₂, Пр₃А=А₃, то очевидно, что А₁А₂А₃=А. Тогда, если С=АВ, то Пр1С=А, Пр2С=В, а если DАВ, то Пр1DА, Пр2DВ.