Множества. Операции над множествами. Булева алгебра множеств

Булева алгебра множеств
Основными понятиями этой главы являются понятия множества и элемента множества (эти понятия считаем неопределяемыми). Синонимами слова множество являются слова совокупность, набор, коллектив и т.д. Множества мы будем обозначать большими буквами латинского алфавита (X, У, Z,...), элементы множества малыми буквами (х, у, z,...). Принадлежность элемента х множеству X (неопределяемое понятие) будем обозначать х X. Аналогично х X обозначает, что элемент х не принадлежит множеству X.
Определение 1.1. Множество X является подмножеством множества Y (обозначим
X Y), если для любого х X следует, что х Y.
Определение 1.2. Множества Х и Y равны (X = Y) тогда и только тогда, когда X Y и Y Х.

Будем считать, что мы выбрали некоторое достаточно большое множество, называемое универсальным, за пределы которого мы не будем выходить. Понятие универсального множества, обозначим его U также неопределяемое, но любое рассматриваемое нами множество X удовлетворяет условию: X U. Это утверждение мы принимаем без доказательства. Заметим, что утверждения, которые считаются верными без доказательства, называются аксиомами.

Определим следующие операции над множествами:
объединением двух множеств Х и Y называется множество Х Y = {х U | х X или х Y}; пересечением двух множеств Х и Y называется множество Х ∩ Y = {х U| х X И х Y}; дополнением множества X называется множество = {х U | х X}.
Определение 1.3. Назовем пустым множеством (множеством, в котором нет ни одного элемента) множество Ø = , то есть дополнение к универсальному множеству.
Рисунки, интерпретирующие операции над множествами, называются диаграммами (кругами) Виенна.


Объединение Пересечение Дополнение

Теорема 1.4. Множества относительно операций дополнения, объединения и пересечения удовлетворяют следующим равенствам
1. = X - закон двойного отрицания;
2. X Y = Y X - коммутативность;
3. X ∩ Y = Y ∩ X - коммутативность;
4. X (Y Z) = (X Y) Z - ассоциативность;
5. X ∩ (Y ∩ Z) = (X ∩ Y) ∩ Z - ассоциативность;
6. X (Y ∩ Z) = (X Y) ∩ (X Z) - дистрибутивность;
7. X∩ (Y Z) = (X ∩ Y) (X ∩ Z)- дистрибутивность;
8. = ∩ - закон де Моргана;
9. = - закон де Моргана;
10. X X = X- закон идемпотентности;
11. Х∩Х = Х- закон идемпотентности;
законы нуля и единицы:
12. X U= U;
13. X∩U = X;
14. X Ø = X;
15. X ∩Ø = Ø;
16. X (X∩Y) = X - закон поглощения;
17. X ∩ (X Y) = X - законы поглощения;
18. X = U - законы дополнения;
19. Х ∩ = Ø - законы дополнения.
Все эти равенства следуют непосредственно из определения и демонстрируются с помощью кругов Виенна.
Множество с операциями, удовлетворяющими 19 приведенным выше равносильностям, называется булевой алгеброй; сами операции в этом случае называются булевыми. Из теоремы 1.4 следует, что множество всех множеств образует булеву алгебру относительно операций дополнения, объединения и пересечения. Заметим, что в дальнейшем мы будем рассматривать и другие множества, образующие булеву алгебру. Кроме булевых, над множествами определяются следующие операции.
Определение 1.5. Разностью множеств X и Y называется множество X\Y = {х X и х Y}
Определение 1.6. Симметрической разностью множеств X и Y называется множество X ΔY = (X\Y) (Y\X).

Очевидно, что имеют место следующие равенства:
1)Х\Ø = Х; 2) X\U = Ø; 3) Ø\Х = Ø; 4)Х\Х= Ø;5)U\X = ; 6) X ΔY = Y Δ Х;
7) X Δ U = ; 8) X \ Ø = X
Рассмотрим более подробно свойства подмножеств данного множества.
Теорема 1.7. Пусть X и Y - множества. Тогда X Y тогда и только тогда, когда X\Y = Ø
Теорема 1.8. Пусть X, Y, Z - множества. Тогда:
1) X X - рефлексивность;
2) из (X Y) и (Y Z) следует X Z - транзитивность;
3) из (X Y) и (Y X) следует X = Y - антисимметричность.
Доказательства приведенных выше теорем следуют непосредственно из определений. Замечание: понятия коммутативности, ассоциативности, дистрибутивности, рефлексивности, транзитивности и антисимметричности будут подробно рассмотрены в последующих главах этой книги.

Powered by Drupal - Design by artinet