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

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

Булеаном 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

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

№	Формулы	Название
	A Ç Æ =Æ; A È Æ = A; A Ç =Æ	Свойства пустого множества
	A È U = U; A Ç U = A; A È Ā = U	Свойства универсального множества
	A Ç B = B Ç A; A È B = B È A	Закон коммутативности
	(А Ç В) Ç С=А Ç (В Ç С); (А È В) È С=А È (В È С)	Закон ассоциативности
	А Ç (В È С)= (А Ç В) È (А Ç С); А È (В Ç С)= (А È В) Ç (А È С)	Закон дистрибутивности
	= А	Закон двойного дополнения
	А Ç А=А; А È А=А	Законы идемпотентности
		Законы де Моргана
	А È (А Ç В)=А; А Ç (А È В)=А	Законы поглощения

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

А È (В Ç С)= (А È В) Ç (А È С). (1.1)

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

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

или и ( или и

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

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

и или и или

или и или

.

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

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