1.2. Операции над множествами

Во многих задачах рассматриваются системы подмножеств заданного множества U, называемого универсальным множеством или универсумом.

Включение множеств  обладает свойствами:

а) рефлексивности: XX;

б) транзитивности: если XY, YZ, то XZ;

в) антисимметричности: если XY, YX, то X=Y.

Включение  обладает свойством транзитивности.

На подмножествах X и Y некоторого универсума заданы теоретико-множественные операции.

1) Объединение: XY={x: xX или xY}, отсюда

max{Y,X}XYY+X.

2) Пересечение: XY={x: xX и xY}, отсюда

0XYmin{Y,X}.

Множества, не имеющие общих элементов, называют непересекающимися, в этом случае записывают: XY=.

Система R множеств замкнута относительно некоторой операции , если из включений X,YR следует включение XYR. Кольцом множеств называется система множеств, замкнутая относительно операций объединения и пересечения. Множество всех подмножеств универсума образует кольцо. Множество элементов n-множества при n>1 не образует кольца.

3. Разность: X\Y={x: xX и xY}, отсюда

0X\YX.

Если YX, то множество X\Y называют дополнением множества Y до X.

4) Дополнение множества X (обозначается ): =U\X, отсюда

 =U-X.

5) Симметрическая разность: XY=(XY)\(XY).

6) Декартово произведение: XY={(x,y): xX, yY}, отсюда

XY=XY.

Декартовым произведением множеств X₁,…,X_m называется множество наборов {(x₁,…,x_m)}, где x_iX_i, , mN. Несложно доказать (математическая индукция), что

X₁…X_m=X₁…X_m.

Декартово произведение m одинаковых сомножителей X…X обозначается X^m и называется m-й декартовой степенью множества X. Элемент (x₁,…,x_m) множества X^m называют словом длины m в алфавите X или последовательностью (набором) длины m над множеством X. Число различных слов длины m в алфавите порядка n равно n^m.

Система всех подмножеств множества X называется булеаном множества X, обозначается 2^X.

Утверждение 1.1. Если X есть п-множество, то 2^X=2ⁿ.

t Любому подмножеству Y множества X={x₁,…,x_n}) взаимно однозначно соответствует вектор _Y=(₁,…,_n)V_n, в котором _i=1  x_iY, . Следовательно, 2^X={0,1}ⁿ=2ⁿ. u

Расстоянием (Хэмминга) между наборами x,yX^m (обозначается dist(x,y)), где x=(x₁,…,x_m), y=(y₁,…,y_m), называется количество чисел i{1,…,m}, для которых x_iy_i. Для любых x,y,zX^m выполнено:

1. dist(x,y)=dist(y,x);

2. dist(x,y)>0 при xy и dist(x,x)=0;

3. dist(x,y)dist(x,z)+dist(z,y) (неравенство треугольника).

Приведем свойства операций над подмножествами X,Y,Z универсума U.

1. Идемпотентность:

XX=X, XX=X.

2) Коммутативность:

XY=YX; XY=YX.

3) Ассоциативность:

(XY)Z=X(YZ); (XY)Z=X(YZ).

4. Дистрибутивность:

X(YZ)=(XY)(XZ); X(YZ)=(XY)(XZ).

5) Поглощение:

(XY)X=X; (XY)X=X.

6) Свойства нуля:

X=X; X=.

7) Свойства единицы:

XU=U; XU=X.

8) Свойства дополнения:

X =U; X =.

9) Инволютивность:

=X.

10) Законы де Моргана:

; .

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

X X

Y Y

Рис.1.1. Диаграммы Венна объединения и пересечения множеств

Такие представления называются диаграммами Венна. На рис.1.1 операции объединения и пересечения множеств представлены с помощью диаграмм Венна. Результат операции изображен закрашенной областью.