Проверка равенства двух множеств

Во многих случаях возникает необходимость сравнения двух множеств, каждое из кото-рых получено из одних и тех же исходных подмножеств в результате различных комбинаций нескольких теоретико-множественных операций. Для этого рассмотрим диаграммы Венна для двух и трёх множеств. Они показаны на рис.7 и 8. Цифры на этих рисунках – это просто имена соответствующих подмножеств.

Принципиальными являются следующие почти очевидные факты, которые приводятся без доказательств.

Утверждение 1. α) Результат выполнения любых теоретико-множественных операций над множествами A и B является объединением некоторых множеств из числа множеств, обо-значенных на рис.7 цифрами 1, 2, 3, 4. β) Результат выполнения любых теоретико-множествен-ных операций над множествами A, B и C является объединением некоторых множеств из числа множеств, обозначенных на рис.8 цифрами 1, 2, 3, 4, 5, 6, 7, 8.

Таким образом, для определения результатов теоретико-множественных операций мож-но осуществить операции с множествами, состоящими из символов 1, 2, 3, 4 (для двух мно-жеств) или из символов 1, 2, 3, 4, 5, 6, 7, 8 (для трёх множеств). Такие операции подробно рассмотрены в примерах 10 и 11. Рассмотрим ещё некоторые примеры.

Пример 12. Рассмотрим множество(А В) ', где А и В показаны на рис.7. В данном слу-чае U = {1, 2, 3, 4}; А ={2, 4}; B = {3, 4}. В соответствии с описанными ранее алгоритмами вы-полнения теоретико-множественных операций имеем А В = {4}, (А В) ' = {4} ' = {1, 2, 3}. Та-ким образом, просто подсчитано, что

(А В) ' = {1, 2, 3}. (3а)

Рис.7

Рис.8

Рассмотрим теперь множество А' В'. Имеем (см. рис.7): А' = {1, 3}, В' = {1, 2}, А' В' = {1, 3} {1, 2}= {1, 2, 3}, т.е. подсчитано, что

А' В' = {1, 2, 3} ■ (3b)

Формулы (3а) и (3b) означают, что (А В) ' = А' В' (дополнение к пересечению равно объ-единению дополнений). Это соотношение называется 1 -м законом де Моргана. Аналогично вы-водится и 2 -й закон де Моргана: (А В) ' = А' В' (дополнение к объединению равно пересече-нию дополнений). Законы де Моргана уже упоминались в главе 1 (формулы (1-7) и (1-8)). Но там они относились к истинностным значениям составных высказываний, а здесь – к двум про-извольным подмножествам произвольного универсального множества U. Однако это – не слу-чайное совпадение, а проявление общей закономерности.

Пример 13. Рассмотрим множество А (В С), где А, В и С показаны на рис.8. В данном случае U = {1, 2, 3, 4, 5, 6, 7, 8}; А ={2, 5, 6, 8}; B = {3, 5, 7, 8}; С = {4, 6, 7, 8}. В соответствии с описанными ранее алгоритмами выполнения теоретико-множественных операций имеем В С = {3, 5, 7, 8} {4, 6, 7, 8} = {7, 8}; А (В С) = {2, 5, 6, 8} {7, 8} = {2, 5, 6, 7, 8}. Таким образом,

А (В С) = {2, 5, 6, 7, 8}. (4а)

Рассмотрим теперь множество (А В)Ç(А С) с теми же самыми А, В и С. В соответствии с описанными ранее алгоритмами выполнения теоретико-множественных операций имеем А В = {2, 5, 6, 8} {3, 5, 7, 8} = {2, 3, 5, 6, 7, 8}; А С = {2, 5, 6, 8} {4, 6, 7, 8} = {2, 4, 5, 6, 7, 8}; (А В) (А С) = {2, 3, 5, 6, 7, 8}Ç {2, 4, 5, 6, 7, 8} = {2, 5, 6, 7, 8} Таким образом,

(А В) (А С)= {2, 5, 6, 7, 8} ■ (4b)

Формулы (4а) и (4b) означают, что А (В С) = (А В) (А С). Эти соотношения выража-ют дистрибутивность объединения относительно пересечения. Заметим, что в 15-м вариан-те задания 1-6 требуется проверить эквивалентность двух составных высказываний:

P Ú(Q Ù R) º (P Ú Q)Ù(P Ú R),

которая внешне напоминает установленное в примере 13 равенство множеств. Эта аналогия между составными высказываниями и теоретико-множественными операциями обсуждается в главе 5.

Задание 10. Путём выполнения заданных теоретико-множественных операций проверить равенство двух множеств (см. примеры 12 и 13):

1. А (В С) = (А В) С

2. А (В С) = (А В) С

3. А (В С) = (А В) (А С)

4. А (В С) = (А В) (А С)

5. (А В) А = (А В) A = А

6. (А В) ' = А' В'

7. (А В) ' = А' В'

8. A (В С) = (A В) (A C)

9. A (В С) = (A В) (A C)

10. A (A B) = А В

11. А В = А (А В)

12. А (B C) = (А В) (A С) = (А В) C

13. (A B) C = (A C)\(B C)

14. А В = A (B A)

15. (A') ' = A

16. A A' = U, где U - универсальное множество

17. A A' = Æ

18. (А В) (А В') = (А В) (А В') = A

19. (А' В) A = А В

20. A (B A) = Æ

21. (А В) C = (A C) (B C)

22. A (B C) = (A B) (A C)

23. A (B C) = (A B) C

24. A Δ B = B Δ A

25. A Δ(B Δ C) = (A Δ B Δ C

26. A (B Δ C) = (A B)Δ(A C)

27. A Δ(A Δ B) = B

28. A B = A Δ B Δ(A B)

29. A B = A Δ(A B)

30. A ΔÆ = A

31. A Δ A = Æ

32. A Δ U = A', где U - универсальное множество

33. A B = (A Δ B) (A B) ■

Дата добавления: 2015-10-16