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

Во многих случаях возникает необходимость сравнения двух множеств, каждое из кото-рых получено из одних и тех же исходных подмножеств в результате различных комбинаций нескольких теоретико-множественных операций. Для этого рассмотрим диаграммы Венна для двух и трёх множеств. Они показаны на рис.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. Все три компоненты являются разными объектами ■