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

Во многих случаях возникает необходимость сравнения двух множеств, каждое из кото-рых получено из одних и тех же исходных подмножеств в результате различных комбинаций нескольких теоретико-множественных операций. Для этого рассмотрим диаграммы Венна для двух и трёх множеств. Они показаны на рис.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): А' = {1, 3}, В' = {1, 2}, А' В' = {1, 3} {1, 2}= {1, 2, 3}, т.е. подсчитано, что

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

Рис.7

Рис.8

Формулы (3а) и (3b) означают, что (А В)' = А' В' (дополнение к пересечению равно объ-единению дополнений). Это соотношение называется 1-м законом де Моргана. Аналогично вы-водится и 2-й закон де Моргана: (А В)' = А' В' (дополнение к объединению равно пересече-нию дополнений). Законы де Моргана будут упоминаться в разделе 5-2. Но там они относятся к булевым функциям, а здесь – к двум произвольным подмножествам произвольного универсаль-ного множества 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) означают, что А (В С) = (А В) (А С). Эти соотношения выража-ют дистрибутивность объединения относительно пересечения.

Задания

Задание 1. Определить истинность или ложность следующих высказываний:

01. 6 Î{–2, 5, 8, 9}

02. 9 Ï{6, 3, 4, 8}

03. {k, c, r, a} = {k, c, a, r}

04. Множество натуральных чисел, меньших трёх ¹ {1, 2}

05. 8 Í{3, –2, 5, 7, 8}

06. {5, 8, 9}Î{5, 8, 9, 0}

07. 6 ¹ {–2, 5, 8, 9}

08. Æ = {Æ}

Пусть A = {2, 4, 6, 8, 10, 12}, B = {2, 4, 8, 10, 12}, C = {4, 10, 12}.

09. 4ÎA

10. 8ÎB

11. 4ÏC

12. Каждый элемент C принадлежит A

13. Каждый элемент C принадлежит B

Пусть U = {a, b, c, d, e, f, g}, A = {a, e}, B = {a, b, e, f, g}, C = {b, f, g}, D = {d, e}.

14. CÌU

15. DÍB

16. AÌB

17. BÍC

18. ÆÌA

19. ÆÍÆ

20. DÌB

21. DËB

22. AËB■

Задание 2.Вставить знакÎ, Ï, = или ¹ вместо пробела, чтобы получить истинное выска-зывание:

01. 5____{2, 4, {5}, 7}

02. {4}____{4, 7, 8, 12}

03. 0____{1, –2, 0, {5}, 9}

04. {3}____{2, 3, 4, 6}

05. 8____{3, –2, 5, 7, 8}

06. –12____{3, 8, 12, 18}

07. 3____{2, 5, 6, 8}

08. b____{h, c, d,a, b}

09. 9____{6, 3, 4, 8}

10. {k, c, r, a}____{k, c, a, r}

11. {5, 8, 9}____{5, 8, 9, 0}

12. 6____{–2, 5, 8, 9}

13. m____{l, m, n, o, p}

14. {e, h, a, n}____{a, {h}, e, n}

15. {3, 7, 12, 14}____{3, 7, 12, 14, 0}■

Задание 3.Вставить знак Í или Ë вместо пробела, чтобы получить истинное высказыва-ние:

01. {4}____{4, 7, 8, 12}

02. {3}____{2, 3, 4, 6}

03. {k, c, r, a}____{k, c, a, r}

04. {5, 8, 9}____{5, 8, 9, 0}

05. {e, h, a, n}____{a, {h}, e, n}

06. {3, 7, 12, 14}____{3, 7, 12, 14, 0}

07. {–2, 0, 2}_____{–2, –1, l, 2}

08. {Понедельник, Среда, Пятница}___{Воскресенье, Понедельник, Вторник, Среда, Четверг}

09. {a, n, d}_____{r, a, n, d, y}

10. Æ_____{a, b, c, d, e}

11. Æ_____Æ

12. {–7, 4, 9}_____множествовсехнечётныхцелыхчисел

13. {B, C, D}_____{B, C, D, F}

14. {красный, зелёный, синий, жёлтый}_____{ зелёный, жёлтый, синий, красный}

15. Æ_____{0}

16. {–1, 0, 1, 2, 3) _____{0, 1, 2, 3, 4} ■

Задание 4.Написать булеан(множество всех подмножеств) для следующих множеств:

01. {B, C, D}

02. {B, C}

03. {B, {C}}

04. {{B},{C}}

05. {B, {B}}

06. {B, {B}, C}

07. {{Æ}, B, {C}}

08. {a, 1, 0}

09. {a, 1, {0}}

10. {a, {a}, 1, {0}}

11. {–3, 3, {–3}}

12. {Понедельник, Среда, Пятница}

13. {Понедельник, Среда, August}

14. {e, é, è} ■

Задание 5.Найти пересечение множеств (см. пример 7):

01. {3, 4, 5, 6, 7} {4, 6, 8, 10}

02. {9, 14, 25, 30} {10, 17, 19, 38, 52}

03. {5, 9, 11} Æ

04. {a, m, n, s, w} {c, d, m, o, s}

05. {P, Q, R} {F, H, Q, X, R} ■

Задание 6.Найти объединение множеств (см. пример 6):

01. {1, 5, 7} {3, 7, 10}

02. {a, m, n, s, w} {c, d, m, o, s}

03. {P, Q, R} {F, H, Q, X, R} ■

Задание 7.Найти разность множеств (см. пример 8):

01. {1, 5, 7} {3, 7, 10}

02. {a, m, n, s, w} {c, d, m, o, s}

03. {P, Q, R} {F, H, Q, X, R}

04. {3, 5, 7} {1, 2, 3, 4, 5, 7}

05. {f, g, h, i,j, k} {g, i, k} ■

Задание 8.Пусть U = {a, b, c, d, e, f, g}, X = {a, c, e, g}, Y = {a, b, c}, Z = {b, c, d, e, f}. Вы-полнить указанные операции:

01. X (Y Z)	02. Y (X Z)	03. (Y Z’) X
04. (X’ Y’) Z	05. (Z X’)’ Y	06. (Y X’)’ Z’
07. X Y	08. Y X	09. X’ Y
10. Y’ X	11. X (X Y)	12. Y (Y X) ■

Задание 9.Пусть U = {a, b, c, d, e, f, g},A = {a, c, e}, B = {a, b, d, e, f}, C = {a, c, d, g}.

Выполнить указанные операции:

01. (A‘ B) C 02. (A B‘) C 03. (A B) C‘ 04. (A B)‘ C	05. A‘ (B C) 06. A (B‘ C) 07. A (B C‘) 08. A (B C)‘	09. (A‘ B) C 10. (A B‘) C 11. (A B) C‘ 12. (A B)‘ C	13. A‘ (B C) 14. A (B‘ C) 15. A (B C‘) 16. A (B C)‘
17. (A‘ B) C 18. (A B‘) C 19. (A B) C‘ 20. (A B)‘ C	21. A‘ (B C) 22. A (B‘ C) 23. A (B C‘) 24. A (B C)‘	25. (A‘ B) C 26. (A B‘) C 27. (A B) C‘ 28. (A B)‘ C	29. A‘ (B C) 30. A (B‘ C) 31. A (B C’) 32. A (B C)’ ■

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

01. А (В С) = (А В) С

02. А (В С) = (А В) С

03. А (В С) = (А В) (А С)

04. А (В С) = (А В) (А С)

05. (А В) А = (А В) A= А

06. (А В)' = А' В'

07. (А В)' = А' В'

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

09. 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)

Предметный указатель

Венна диаграммы

Дистрибутивность объединения относительно пересечения

Множеств, объединение

пересечение

разность

разность симметрическая

Множества, равные

Множества, булеан

дополнение

Множество, пустое

универсальное

Моргана, де 1-ый закон

2-ой закон

Операциитеоретико-множественные

Подмножество

Принадлежность

Свойство, характеристическое

Глава 3. Кортежи

1. Понятие кортежа

2. Прямое произведение множеств

3. Операция проектирования

4. Графики

5. Соответствия и функции

6. Задания

7. Предметный указатель

Понятие кортежа

Как понятия высказывания и множества, понятие кортежа будет исходным, неопределяе-мым. Можно говорить о кортеже книг, стоящих на полке, о кортеже спортсменов, построенных в один ряд по росту, векторе, состоящем из n координат, и т.д. Синонимами слова «кортеж» служат слова «вектор», «набор», «последовательность» и пр.

Наряду с термином «кортеж» вводится (также в качестве исходного) термин «компонен-та», или «координата» кортежа. В самом общем виде компонента кортежа (точнее, его i-ая компонента) – это то, что находится в данном кортеже на i-ом месте. Это может быть i-ая (счи-тая слева) книга на полке, i-ый по алфавиту школьник в классе, i-ый по росту школьник в том же классе, i-ая координата вектора, и т.д. Число компонент кортежа называется его длиной. Кортеж длины s, первая компонента которого есть a₁, вторая - a₂, ..., s-я, последняя, - a_s, обоз-начается знакосочетанием áa₁, a₂, ..., a_sñ (компоненты перечислены по порядку, разделены запя-тыми и взяты в угловые скобки). Обратим внимание на принципиальное различие между корте-жем áa₁, a₂, ..., a_sñ и множеством {a₁, a₂, ..., a_s} всех его компонент. Элементы множества, хотя и выписаны в некотором порядке, на самом деле совершенно «равноправны», и множества {a₁, a₂, ..., a_s} и {a_s, a_s−1 , ..., a₁} совпадают. В то же время кортежи áa₁, a₂, ..., a_sñ и áa_s, a_s−1 , ..., a₁ñ являются, вообще говоря, разными. При задании множеств не только перечислением (как это делалось до сих пор), а и другими способами (см. далее главу 4) различие между множествами и кортежами станет более явным. Заметим также, что все элементы множества предполагаются различными, а разные компоненты кортежа могут совпадать.

Кортежи длины 2 называются парами, длины 3 -тройками и т.д. Для удобства вводят в рассмотрение кортеж длины 0, не содержащий вообще компонент, т.е. имеющий вид áñ. Его обозначают буквой L (лямбда).

Кортежи будем обозначать строчными буквами из начала греческого алфавита. Будем считать, что кортеж a равен кортежу b, если, во-первых, они одинаковой длины, и, во-вторых, каждая компонента a равна компоненте b с тем же номером. Равенство кортежей a и b выража-ется как a = b, а неравенство - как a ≠ b. Кортеж a называется кортежем над множеством X, если каждая компонента a есть элемент из X. Компонентами кортежа могут быть объекты лю-бой природы, в частности, множества и другие кортежи.

Пример 1.Рассмотрим следующий кортеж длины 3: a = áa, {a}, áaññ. Его 1-ая компонента – это некоторый элемент a, 2-ая компонента – одноэлементное множество {a}, 3-ья компонента – кортеж áañ длины 1. Все три компоненты являются разными объектами ■