Во многих случаях возникает необходимость сравнения двух множеств, каждое из кото-рых получено из одних и тех же исходных подмножеств в результате различных комбинаций нескольких теоретико-множественных операций. Для этого рассмотрим диаграммы Венна для двух и трёх множеств. Они показаны на рис.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 1, вторая - a 2,..., s -я, последняя, - as, обоз-начается знакосочетанием á a 1, a 2,..., as ñ (компоненты перечислены по порядку, разделены запя-тыми и взяты в угловые скобки). Обратим внимание на принципиальное различие между корте-жем á a 1, a 2,..., as ñ и множеством { a 1, a 2,..., as } всех его компонент. Элементы множества, хотя и выписаны в некотором порядке, на самом деле совершенно «равноправны», и множества { a 1, a 2,..., as } и { as, as −1 ,..., a 1} совпадают. В то же время кортежи á a 1, a 2,..., as ñ и á as, as −1 ,..., a 1ñ являются, вообще говоря, разными. При задании множеств не только перечислением (как это делалось до сих пор), а и другими способами (см. далее главу 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. Все три компоненты являются разными объектами ■
