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

Объединением множествА иВназывается множество, состоящее из тех и только тех элементов, которые принадлежат хотя бы одному из множествА илиВ(рис. 1.2,а).

Пример. Если, то.

U U

A B A B

а) б)

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

а) объединение множеств;

б) пересечение множеств

Пересечением множествАиВназывается множество, состоящее из тех и только тех элементов, которые принадлежат одновременно и множествуА, и множествуВ(рис. 1.2,б).

Пример. Если, то.

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

Пример.;

.

ДополнениеммножестваАдо универсальногоUназывается множествоU(рис. 1.3,б).

Пример. Если, U, тоU.

U U

A B

A

а) б)

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

а) разность множеств A иB;

б) дополнение множества A

1.1.6. Системы множеств

Элементы множества сами могут быть множествами: ; в таком случае удобно говорить о системе множеств. Рассмотрим такие системы множеств, как булеан, разбиение и покрытие множеств.

Булеаном B(Х)множестваХназывается множество всех подмножеств множестваХ. Например, для множества булеаном является множествоB,.

Разбиением R(Х)множестваХназывается система его непустых непересекающихся подмножеств, в объединении дающая множествоХ(рис. 1.4).

U

X X₁ X₂

X₃ X₄

Рис. 1.4. Разбиение множества R

Например, для множества можно построить разбиениеR₁, состоящее из двух элементов (они называются блоками разбиения), или разбиениеR₂– из четырех блоков; возможны и другие разбиения этого множестваХ.

Покрытием P(X)множестваXназывается система его непустых подмножеств, в объединении дающая множествоX(рис. 1.5).

В этом определении отсутствует слово “непересекающаяся” – т.е. блоки могут иметь общие элементы.

Пример. Для множествапокрытиями являются системы множестви.

1.1.7. Законы алгебры множеств

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

Таблица 1.1

Законы алгебры множеств

№	Формулы	Название
1	A = ; A = A; A=	Свойства пустого множества
2	AU = U; AU = A; AĀ = U	Свойства универсального множества
3	AB = BA; AB = BA	Закон коммутативности
4	(АВ)С=А(ВС); (АВ)С=А(ВС)	Закон ассоциативности
5	А(ВС)= (АВ)(АС); А(ВС)= (АВ)(АС)	Закон дистрибутивности
6	=А	Закон двойного дополнения
7	АА=А; АА=А	Законы идемпотентности
8		Законы де Моргана
9	А(АВ)=А; А(АВ)=А	Законы поглощения

Докажем закон дистрибутивности

А(ВС)= (АВ)(АС).(1.1)

Обозначим Xлевую часть равенства (1.1),Y– правую. Согласно определению равенства множеств покажем, что выполняются одновременнои.

Пусть x– произвольная точка из множестваX=А(ВС). Тогда по определению объединения множеств (или). Далее по определению пересечения множеств (илии ). Следовательно,

или и (или и

Таким образом для любого выполняется, т.е..

Докажем теперь, что . Пустьy– произвольная точка из множества. Тогда

иилииили

илииили

.

В силу произвольности заключаем.

Таким образом, и, следовательно,, и закон дистрибутивности доказан.