Элементы теории множеств

A  B = {x| x  A и x  B или x  A и x  B}
На рисунке 2.6 серым цветом изображена симметрическая разность множеств.
Данная операция обладает следующими свойствами:

1. 
   А  В = В  А - коммутативность;
   
2. 
   (А  В)  С = А (В  С) – ассоциативность;
   
3. 
   А   =   А – существование нейтрального элемента;
   
4. 
   А  (В  С) = (А  В)  (А  С) – дистрибутивность относительно пересечения.
   

Симметрическая разность с помощью определенных ранее операций может быть представлена в виде: AB=(А\В)(В\А) или AB=(АВ)\(А В).
Следует также отметить, что иногда эту операцию называют дизъюнктивной суммой и обозначают знаком  или .
Замечание 2.1. Над множествами, полученными в результате указанных пяти операций, можно в свою очередь производить те же самые операции. Так, например, можно образовывать дополнения пересечения , объединения или разности ; можно образовывать пересечение объединений (АВ)  (С D) или объединение пересечений (АВ)  (С D) и т.д.
Замечание 2.2. Для указания порядка операций применяются скобки. Отношение между скобками, знаками  и  такое же, как между скобками, знаками * и + в алгебре. Дополнение берётся от всего выражения, над которым стоит черта.
Замечание 2.3. Нужно помнить, что все указанные операции можно производить только над множествами, принадлежащими одному и тому же универсальному множеству.
Задача 2.1. Заданы множества: U = {2; 3; 4; 8; 9; 10; 11}; A = {2; 3; 4}; B = {3; 4; 8; 9} и С = {2; 10; 11}. Найти следующие множества:

1. 
   А  В; А  В  С;
   
2. 
   Ā;
   
3. 
   А  В; В  Ā;
   
4. 
   А \ В; В \ А; А \ С \ В;
   
5. 
   А  В; А  С; (А  В)  С.
   

Решение.

1. 
   По определению объединение А  В будет состоять из всех элементов обоих множеств, то есть А  В ={2; 3; 4; 8; 9}. Как мы помним, кратность элементов не учитывается. Аналогично для нахождения А  В  С к элементам множества А  В присоединим элементы множества С. Получим: А  В  С = {2; 3; 4; 8; 9; 10; 11}. Очевидно, что А  В  С = U.
   
2. 
   Для нахождения дополнения множества А (множества Ā) выберем те элементы, которые принадлежат универсуму и не принадлежат А. Таковыми будут элементы 8, 9, 10 и 11. То есть Ā = {8; 9; 10; 11}. Аналогично найдем = {2; 10; 11}; = {3; 4; 8; 9}.
   
3. 
   Пересечение множеств – это множество, состоящее из их общих элементов. Для множеств А и В таковыми будут только два элемента – 3 и 4. Следовательно, можем записать: А  В = {3; 4}. Аналогично найдём В  Ā = {3; 4; 8; 9}  {8; 9; 10; 11} = {8; 9}.
   
4. 
   Для нахождения разности А \ В отберём только те элементы, которые принадлежат исключительно множеству А и не принадлежат В. Таковым будет только один элемент – 2. Значит, А \ В = {2}. Аналогично найдём В \ А = {8; 9}. A \ C \ B = (A \ C) \ В = {3; 4} \ {3; 4; 8; 9} = .
   
5. 
   Для нахождения симметрической разности А  В сначала объединим эти множества, а затем из полученного множества удалим общие элементы двух множеств. Таких элементов будет два: 3 и 4. Следовательно, А  В = {2; 8; 9}. Аналогично, А  С = {3; 4; 10; 11}.
   

(А  В)  С = {2; 8; 9}  {2; 10; 11} = {8; 9; 10; 11}.
Задача 2.2. Заданы множества: U = {a; b; c; d; e; f; k, m, n}; P = {a; b; c, d}; Q = {b; c; e; f; k} и R = {k; m; n}. Выполнить следующие действия:

1. 
   
   
2. 
   
   
3. 
   
   
4. 
   
   
5. 
   
   

Решение.

1. 
   Сначала выполним действие в скобках и найдём объединение множеств P c Q: P  Q = {a, b, c, d, e, f, k}. Далее найдём дополнение множества R: = {a, b, c, d, e, f}. Объединяем оба полученных множества: = {a, b, c, d, e, f, k}. И, наконец, находим дополнение к последнему множеству. Окончательно = {m, n}.
   
2. 
   Сначала находим разность P \ R = {a; b; c, d}. Очевидно, что P \ R = P. Далее найдём разность этого множества с Q: P \ R \ Q = P \ Q = {a, d}. Дополнение к этому множеству ={b, c, e, f, k, m, n}. Находим теперь пересечение этого множества с R. Окончательно: = {k, m, n}.
   
3. 
   Находим дополнения = {a, b, c, d, e, f}, = {a, d, m, n}. Их симметрическая разность = {b, c, e, f, m, n}. Дополнение Р: = {e, f, k, m, n}. Теперь можем найти симметрическую разность = {e, f}. Окончательно получаем: = {b, c, m, n}.
   
4. 
   Найдём PQ={b,c}. Дополнение к нему = {a, d, f, k, m, n}. Пересечение QR={k}. Его дополнение = {a, b, c, d, e, f, m, n}. Разность между найденными дополнениями ={k}. Дополнение этого множества было найдено на предыдущем шаге. Поэтому
   

= {a, b, c, d, e, f, m, n}.

5. 
   Очевидно, что пересечение U с R будет не что иное, как R, то есть . Отсюда получаем, что = {a, b, c, d, e, f}. Далее найдём = {e, f, k, m, n} и симметрическую разность = {b, c, m, n}. Окончательно получаем: = {b, c}.
   

Задача 2.3. Для двух произвольных множеств А и В построить диаграммы и найти следующие множества:

1. 
   
   
2. 
   ;
   
3. 
   
   

Решение.__1)_____Задача_2.4.'>Решение.

1)



Задача 2.4. Даны три произвольные множества А, В и С. Построить диаграммы и описать следующие восемь множеств, на которые разделится универсальное множество.

Решение

1. 
   область 1 – это пересечение трёх множеств А, В и С. Значит, эта область может быть описана выражением А  В  С;
   
2. 
   область 2 получится, если из пересечения А с В убрать элементы множества С, то есть ;
   
3. 
   область 3 аналогична области 2:
   

;

4. 
   область 4: ;
   
5. 
   область 5 проще всего получить пересечением множества А с множествами , то есть ;
   
6. 
   область 6: ;
   
7. 
   область 7: ;
   
8. 
   область 8 – это дополнение к объединению трёх множеств: .
   

Задача 2.5. Для трёх произвольных множеств А, В и С построить диаграммы и найти следующие множества:

1. 
   (A\B)C;
   
2. 
   A\(BC);
   
3. 
   .
   

Решение.



Задачи для самостоятельного решения.
1. Записать универсальное множество и выполнить над множествами А = {о, т, с, ф, х}, В = { т, с, у, х}, C = {x, y}, D = {о, к, е, ф} следующие операции:

1. 
   (AB)\(CD);
   
2. 
   (A\B)\(C\D);
   
3. 
   ;
   
4. 
   .
   

2. Построить диаграммы для трёх произвольных множеств А, В, С:

1. 
   (AB)(AC);
   
2. 
   (AB)(AB);
   
3. 
   ;
   
4. 
   ;
   
5. 
   .
   

3. ОСНОВНЫЕ ЗАКОНЫ АЛГЕБРЫ МНОЖЕСТВ

Рассмотренные операции над множествами подчинены некоторым законам, которые напоминают известные элементарные законы алгебры чисел. Этим определяется название алгебра множеств, которую часто называют булевой алгеброй множеств, что связано с именем английского математика Джона Буля, который положил в основу своих логических исследований идею аналогии между алгеброй и логикой.
Для произвольных множеств А, В, и С справедливы следующие тождества (табл. 3.1):

Таблица 3.1

1. Закон тождества
2. Коммутативность объединения	2’. Коммутативность пересечения
3. Ассоциативность объединения	3’. Ассоциативность пересечения
4. Дистрибутивность объединения относительно пересечения	4’. Дистрибутивность пересечения относительно объединения
5. Законы действия с пустым и универсальным U множествами (закон исключённого третьего)	5’. Законы действия с пустым и универсальным U множествами (закон противоречия)
6. Закон идемпотентности объединения	6’. Закон идемпотентности пересечения
7. Закон де Моргана	7’. Закон де Моргана
8. Закон элиминации (поглощения)	8’. Закон элиминации (поглощения)
9. Закон склеивания	9’. Закон склеивания
10. Закон Порецкого	10’. Закон Порецкого
11. Закон инволюции (двойного дополнения)

Законы алгебры множеств по отношению к операциям пересечения () и объединения () подчинены принципу двойственности: если в каком-либо законе все знаки пересечения заменить знаками объединения, а все знаки объединения – знаками пересечения, знак универсума (U) заменить знаком пустого множества (Ø), а знак пустого – знаком универсума, то получим снова верное тождество. Например (в силу этого принципа), из следует и т. п.

3.1. Проверка истинности тождеств при помощи диаграмм Эйлера-Венна

Все законы алгебры множеств можно наглядно представить и доказать, используя диаграммы Эйлера-Венна. Для этого необходимо:

1. 
   Начертить соответствующую диаграмму и заштриховать все множества, стоящие в левой части равенства.
   
2. 
   Начертить другую диаграмму и сделать то же для правой части равенства.
   
3. 
   Данное тождество истинно тогда и только тогда, когда на обеих диаграммах заштрихована одна и та же область.