Пример 2.5. Доказать, используя метод взаимного включения, закон дистрибутивности пересечения относительно объединения:
A Ç (B È C) = (A Ç B) È (A Ç C).
Для доказательства этого тождества необходимо доказать, чтоA Ç (B È C) Í (A Ç B) È (A Ç C), a затем что(A Ç B) È (A Ç C) Í A Ç (B È C).Докажем первое включение, показывая истинность последовательности импликаций.
1. Необходимость.
(" x Î Е)(x Î (A Ç (B È C)) ® x Î A & (x Î B Ú x Î C) ®
(импликация истинна на основе определения операций объединения и пересечения)
x Î A & x Î B Ú x Î A & x Î C ® x Î (A Ç B) Ú x Î (A Ç C) ®
(использован дистрибутивный закон)
x Î ((A Ç B) È (A Ç C)) ® A Ç (B È C) Í (A Ç B) È (A Ç C).
(использовано определение включения в высказывательной форме)
Таким образом, доказано прямое включение множеств (необходимость).
2. Достаточность. Теперь докажем обратное включение:
(" x Î Е)(x Î ((A Ç B) È (A Ç C))) ® x Î (A È B) Ú x Î (A È C) ®
x Î A & x Î B Ú x Î A & x Î C ®
x Î A & (x Î B Ú x Î C) ®
x Î A & x Î B È C ® x Î (A Ç (B È C)) ®
(A Ç B) È (A Ç C) Í A Ç (B È C).
Обратное включение также доказано.
Ответ: Таким образом, дистрибутивность пересечения относительно объединения доказана.
Пример 2.6. Доказать, используя геометрический метод, закон дистрибутивности объединения относительно пересечения:
A È (B Ç C) = (A È B) Ç (A È C).
Для доказательства заданного тождества отметим на диаграмме рис. 2.8,а множество точек, соответствующих множеству A È (B Ç C),а на диаграмме рис. 2.8,б - множество точек, соответствующих множеству (A È B) Ç (A È C).
На рис. 2.8,а светлой штриховкой отмечено множество В Ç С, а серой штриховкой - множество А, множество A È (B Ç C) на диаграмме представлено фигурой, представляющей собой объединение фигур, заштрихованных вышеуказанным образом.
Рис. 2.8. Пример диаграммы Эйлера-Венна
На рис. 2.8,б множество A заштриховано серым, множество B - черным, а множествоC - белым цветом, тогда объединение множеств A È Bпредставляет собой фигуру, объединяющую серый и черный круги, объединение множеств A È C – фигуру, объединяющую серый и белый круги, а пересечение множеств A È Bи A È C представлено множеством A и множеством точек внутри фигуры, имеющей одинаковую с множеством A штриховку.
Ответ: Сравнивая эти два рисунка, можно сделать вывод, что эти множества равны, следовательно, тождество доказано.
Пример 2.7. Доказать, используя метод от противного, истинность тождества:
A Ç (B \ A) = Æ.
Решение: Предположим, что A Ç (B \ A) ¹ Æ, т.е. существует элемент х, принадлежащий множеству, стоящему в левой части тождества. Покажем с помощью последовательных импликаций, что наше предположение ложно:
($ x)(x Î (A Ç (B \ A)) ® x Î A & x Î (B \ A) ®
x Î A & (x Î B & x Ï A) ® x Î A & x Î B & x Ï A ®Æ & x Î B ® Æ
(использовано свойство коммутативности)
Ответ: Таким образом, исходное тождество доказано.
КОНТРОЛЬНЫЕ ВОПРОСЫ
1. Что такое взаимное включение множеств и в каком случае существует взаимное включение?
2. Что называется объединением, пересечением, разностью и дополнением множеств?
3. В каком случае объединение, пересечение и разность двух множеств равны пустому множеству?
4. Как определяется симметрическая разность множеств?
5. Привести примеры множеств:
а) объединение которых равно их пересечению;
б) пересечение множеств равно Æ, а их разность не является пустым множеством.
6. Приведите основные тождества алгебры множеств.
7. Поясните операцию дополнения множеств.
8. Какие методы доказательства тождеств с множествами вам известны?
9. Что представляет из себя метод доказательства тождеств с множествами от противного?
10. На чем основан метод взаимного включения?
11. На чем основан геометрический метод доказательства тождеств с множествами?
ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ
1. Пусть множества А, В и С являются подмножествами множества S = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, A = {1, 2, 3, 4, 5, 10}, B = {2, 4, 7, 8, 9}, C = {5, 8, 10}.
Найти: A È B, A \ C, 
Ç (A È C).
2. Пусть A = { x | x - женское имя}; B = {Мария, Иван, Петр, Иванов}; C = { x | x - фамилия}.
Найти: A Ç B, A Ç C, B Ç C.
3. Показать, что для записи последовательности операций объединения и разности необходимы круглые скобки.
4. Показать на диаграммах Эйлера-Венна справедливость утверждения задания 3.
5. Доказать, что B Í A & C Í A Þ B È C Í A.
6. Выполнить разбиения множества В на 5 классов: B = { a, b, c, 1, 2, 3}.
7. Для произвольных множеств А, В, С Î Â(E) доказать или опровергнуть следующие тождества методом включения множеств.
а) A È (B Ç C) = (A È B) Ç (A È C);
б) 
;
в) 
;
г) A \ B = A \ (A Ç B);
д) A \ B = A Ç 
;
е) A \ (A \ B) = A Ç B;
ж) A Ç (B \ C) = (A Ç B) \ (A Ç C);
з) (A È B) Ç (B È C) Ç (A È C) = (A Ç B) È (B Ç C) È (A Ç C);
и) А \ (В È С) = (А \ В) Ç (А \ С);
к) А \ (В Ç С) = (А \ В) È (А \ С);
л) A \ (B \ C) = (A \ B) È (AÇBÇC);
м) A Ç (B \ C) = (A Ç B) \ (A Ç C);
н) A È (B \ C) = (A È B) \ (A È C).
8. Для произвольных А, В, С Î Â(E) доказать или опровергнуть следующие тождества методом от противного.
а) (A \ (A \ B)) \ (A Ç B) = Æ;
б) А Ç (В \ А) = Æ;
в) (A Ç C) \ (С \ (С \ A) = Æ;
г) (A \ С) \ (A Ç 
) = Æ;
д) 
;
е) 
;
ж) ((А Ç В) È (А Ç )) \ А = Æ.
9. Докажите, что B È C = Æ, еслиB = Æ и C = Æ.
10. Покажите на примере, что выражение A È B Ç C требует использования круглых скобок.
11. Докажите что если B Í A & C Í A, то B È C Í A;и еслиAÍ B & A Í C, тоA Í B Ç C.
12. Докажите, что если C Í A, тоB Ç C Í A и C Í A È B.
13. Докажите, Â(A) Ç Â(B) = Â(A Ç B).
14. Справедливо ли тождество Â(A) È Â(B) = Â(A È B).Если нет приведите пример.
15. Справедливо ли тождество: { x | x Î Z & x = 2 m } Ç { x | x Î Z & x = 3 m } = { x | x Î Z & x = 6 m }, где m Î N.
16. Опровергните следующее утверждение: если А Ç В = А Ç С, то В = С.
17. Пусть
I - множество целых чисел, I = {...-1, 0, 1,...};
N - множество положительных целых чисел N = {0, 1, 2,...};
Np - множество отрицательных целых чисел Np = {..., -2, -1, 0};
E - множество четных чисел;
P - множество простых чисел.
Найдите: N Ç Np, I \ N, I \ Np, N È Np, I \ E, E Ç P.
18. Доказать, что А = В, следуя каждому из следующих условий:
а) A \ B = B \ A;
б) A È B = B Ç A;
в) A È C = B È C & A Ç C = B Ç C.
19. Доказать, что 
, если только A = Æи 
.
20. Используя диаграммы Венна, рассмотрите совместимость следующих утверждений.
а) (A Ç B) È C = A \ B и C Ç A = B Ç A;
б) (A \ (B \ C)) Í C È B и A Ç B Ç C = Æ и C \ B Í A;
с) (B \ A) Ç C ¹ Æ и C \ A Í C \ B.
21. Докажите следующие тождества:
а) (A È B) Ç (C È D) = (A Ç C) È (A Ç D) È (B Ç C) È (B Ç D);
б) А \ В = 
È (А Ç В);
в) А \ (А \ (А \ В)) = А \ В;
г) А \ (А \ (А \ (А \ В))) = А Ç В;
д) A1 È A2 È... È An = (A1 \ A2) È (A2 \ A3) È... È (An-1 \ An) È (An \ A1) È (A1 Ç A2 Ç... Ç An) = A1 È (A2 \ A1) È (A3 \ (A1 È A2)) È (A4 \ (A1 È A2 È A3)) È... È (An \ (A1 È A2 È... È An-1)).
е) A1 Ç A2 Ç... Ç An = A1 \ [(A1 \ A2) È (A1 \ A3) È... È (A1 \ An)]
22. Упростите следующие выражения:
а) 
;
б) 
.
