Судопланов. Судоплатов С.В., Овчинникова Е.В. Дискретная математика 2016. Редакционная коллегия серии учебники нгту
 Скачать 2.01 Mb.
|
|
A называется подмножеством множества B (обозначается A ⊆ B), если все элементы множества A принадлежат B: A ⊆ B ⇔ ∀x (x ∈ A ⇒ x ∈ B). Другими словами, это означает справедливость следующего утвержде- ния: для любого элемента x, если x ∈ A, то x ∈ B. Если A ⊆ B, то бу- дем также говорить, что множество A содержится в B, или имеется включение множества A в B. Множества A и B называются равными или совпадающими (обозначается A = B), если они состоят из одних и тех же элементов, т. е. если A ⊆ B и B ⊆ A. Таким образом, чтобы доказать равен- ство множеств, требуется установить два включения. 1.1. МНОЖЕСТВА И ОСНОВНЫЕ ОПЕРАЦИИ НАД НИМИ 15 Пример 1.1.3. Справедливы следующие включения: N ⊆ Z, Z ⊆ Q, Q ⊆ R, R ⊆ C. ¤ Пример 1.1.4. Покажем, что множества M 1 {x | sin x = 1} и M 2 {x | x = π 2 + 2kπ, k ∈ Z} совпадают. Действительно, если x ∈ M 1 , то x является решением уравнения sin x = 1. Но это значит, что x можно представить в виде x = π 2 +2kπ и поэтому x ∈ M 2 Таким образом, M 1 ⊆ M 2 . Если же x ∈ M 2 , т. е. x = π 2 + 2kπ, то sin x = 1, т. е. M 2 ⊆ M 1 . Следовательно, M 1 = M 2 . ¤ Запись A ⊂ B или A B означает, что A ⊆ B и A 6= B (A не равно B), и в этом случае будем говорить, что A строго включено в B, или является собственным подмножеством B. Так, включения из примера 1.1.3 являют- ся строгими. Заметим, что X ⊆ X; если X ⊆ Y и Y ⊆ Z, то X ⊆ Z; если X ⊆ Y и Y ⊆ X, то X = Y . Не следует смешивать отношение принадлежности ∈ и отношение вклю- чения ⊆. Хотя 0 ∈ {0} и {0} ∈ {{0}}, неверно, что 0 ∈ {{0}}, поскольку единственным элементом множества {{0}} является {0}. Совокупность всех подмножеств множества A называется его булеаном или множеством-степенью и обозначается через P(A) или 2 A . Таким об- разом, P(A) {B | B ⊆ A}. Мы будем предполагать, что существует множество, не содержащее ни од- ного элемента, которое называется пустым и обозначается через ∅. Ясно, что ∅ ⊆ A для любого множества A. Пример 1.1.5. Если A = {1, 2, 3}, то P(A) = {∅, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, A}. ¤ Множество, содержащее все элементы, находящиеся в рассмотрении, на- зывается универсальным или универсумом и обозначается через U. Рассмот- рим операции на булеане P(U). Если A, B ∈ P(U), то пересечение A ∩ B и объединение A ∪ B множеств A и B определяются равенствами A ∩ B {x | x ∈ A и x ∈ B}, A ∪ B {x | x ∈ A или x ∈ B}. 16 Глава 1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ Пересечение множеств A и B называется также их произведением и обозна- чается A · B, а объединение — суммой: A + B. Множество A \ B A − B {x | x ∈ A и x / ∈ B} называется разностью множеств A и B, множество A ⊕ B A ÷ B (A \ B) ∪ (B \ A) — кольцевой суммой, или симметрической разностью множеств A и B, а мно- жество A U \ A — дополнением множества A в U (см. рис. 1.1, на котором изображены так называемые диаграммы Эйлера—Венна, наглядно поясня- ющие соотношения между множествами). Пример 1.1.6. Докажем, что A \ B = A ∩ B. Сначала установим, что A \ B ⊆ A ∩ B. Пусть x — произвольный элемент A\B. Тогда по определению разности множеств имеем x ∈ A и x / ∈ B, отсюда x ∈ A и x ∈ B, значит, x ∈ A ∩ B. Теперь покажем, что A ∩ B ⊆ A \ B. Если x ∈ A ∩ B, то x ∈ A и x ∈ B, поэтому x ∈ A и x / ∈ B, значит, x ∈ A \ B. На основании включений A \ B ⊆ A ∩ B и A ∩ B ⊆ A \ B делаем вывод, что A \ B = A ∩ B. ¤ Аналогично примеру 1.1.6 устанавливаются следующие основные свой- ства операций объединения, пересечения и дополнения: ½¼ ¾» U A ½¼ ¾» U A ½¼ ¾» U A "! #Ã B "! #Ã B "! #Ã B A ∪ B A ∩ B A \ B A ⊕ B A ½¼ ¾» U A ½¼ ¾» U A "! #Ã B Рис. 1.1 1.1. МНОЖЕСТВА И ОСНОВНЫЕ ОПЕРАЦИИ НАД НИМИ 17 1. Ассоциативность операций ∪ и ∩: (A ∪ B) ∪ C = A ∪ (B ∪ C), (A ∩ B) ∩ C = A ∩ (B ∩ C). 2. Коммутативность операций ∪ и ∩: A ∪ B = B ∪ A, A ∩ B = B ∩ A. 3. Законы идемпотентности A ∪ A = A, A ∩ A = A. 4. Законы дистрибутивности A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C), A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C). 5. Законы поглощения A ∪ (A ∩ B) = A, A ∩ (A ∪ B) = A. 6. Законы де Моргана A ∪ B = A ∩ B, A ∩ B = A ∪ B. 7. Законы нуля и единицы: положим 0 ∅, 1 U, тогда A ∪ 0 = A, A ∩ 0 = 0, A ∪ 1 = 1, A ∩ 1 = A, A ∪ A = 1, A ∩ A = 0. 8. Закон двойного отрицания A = A. Отметим, что на основании примера 1.1.6 операция \ выражается через операции ∩ и . По закону де Моргана и закону двойного отрицания справед- ливо соотношение A∪B = A ∩ B, т. е. операция ∪ также выражается через операции ∩ и . По определению операция ⊕ тоже выражается через ∩ и . Таким образом, любая из определенных операций над множествами выражается через операции ∩ и . 18 Глава 1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ Пересечение и объединение могут быть определены для любого мно- жества множеств A i , где индексы i пробегают множество I. Пересечение ∩ {A i | i ∈ I} и объединение ∪ {A i | i ∈ I} задаются равенствами ∩ {A i | i ∈ I} {x | x ∈ A i для всех i ∈ I}, ∪ {A i | i ∈ I} {x | x ∈ A i для некоторого i ∈ I}. Вместо ∩ {A i | i ∈ I} и ∪ {A i | i ∈ I} часто пишут соответственно ∩ i∈I A i и ∪ i∈I A i , а иногда просто ∩A i , ∪A i , если из контекста ясно, какое множество I имеется в виду. Если I = {1, 2, . . . , n}, то используются записи A 1 ∩ A 2 ∩ . . . ∩ A n , A 1 ∪ A 2 ∪ . . . ∪ A n , а также n ∩ i=1 A i и n ∪ i=1 A i Множество {A i | i ∈ I} непустых подмножеств множества A называется покрытием множества A, если A = ∪ i∈I A i . Покрытие называется разбиени- ем, если A i ∩ A j = ∅ при i 6= j. Другими словами, множество {A i | i ∈ I} непустых подмножеств множества A является его разбиением, если каждый элемент x ∈ A принадлежит в точности одному из подмножеств A i , каждое из которых не является пустым. Предложение 1.1.1. Следующие условия эквивалентны: (1) A ⊆ B; (2) A ∩ B = A; (3) A ∪ B = B; (4) A \ B = ∅; (5) A ∪ B = U. Доказательство. (1) ⇒ (2). Так как A ∩ B ⊆ A, то достаточно пока- зать, что A ⊆ B влечет A ⊆ A ∩ B. Но если x ∈ A, то по условию x ∈ B, и, следовательно, x ∈ A ∩ B. (2) ⇒ (3). Так как A ∩ B = A, то A ∪ B = (A ∩ B) ∪ B. По закону поглощения и закону коммутативности имеем A ∪ B = B. (3) ⇒ (4). Предположим, что A∪B = B. Так как A\B = A∩B, то по зако- ну де Моргана, закону ассоциативности, закону коммутативности и законам нуля и единицы имеем A \ B = A ∩ (A ∪ B)A ∩ (A ∩ B) = (A ∩ A) ∩ B = 0 ∩ B = ∅. (4) ⇒ (5). Предположим, что A \ B = ∅, т. е. A ∩ B = ∅. Тогда A ∩ B = = 0 = 1. По закону де Моргана и закону двойного отрицания получаем U = 1 = A ∩ B = A ∪ B = A ∪ B. 1.1. МНОЖЕСТВА И ОСНОВНЫЕ ОПЕРАЦИИ НАД НИМИ 19 (5) ⇒ (1). Предположим, что A∪B = U и не выполняется условие A ⊆ B, т. е. найдется элемент x такой, что x ∈ A и x / ∈ B. Тогда x / ∈ A и, значит, x / ∈ A ∪ B, а это противоречит равенству A ∪ B = U. ¤ Упорядоченную последовательность из n элементов x 1 , x 2 , . . . , x n бу- дем обозначать через (x 1 , x 2 , . . . , x n ) или hx 1 , x 2 , . . . , x n i. Здесь круглые или угловые скобки используются для того, чтобы указать на порядок, в ко- тором записаны элементы. Будем называть такую последовательность упо- рядоченным набором длины n, кортежем длины n или просто n-кой. Длина кортежа x hx 1 , x 2 , . . . , x n i обозначается через l(x). Элемент x i называ- ется i-й координатой кортежа x. В теории множеств кортежи кодируются с помощью операции взятия множества по двум элементам в соответствии со следующими правилами: h i ∅, hx 1 i x 1 , hx 1 , x 2 i {{x 1 }, {x 1 , x 2 }}, hx 1 , x 2 . . . , x n+1 i hhx 1 , x 2 . . . , x n i, x n+1 i. Заметим, что две n-ки x = (x 1 , x 2 , . . . , x n ) и y = (y 1 , y 2 , . . . , y n ) равны (x = y) тогда и только тогда, когда x 1 = y 1 , x 2 = y 2 , . . ., x n = y n Пример 1.1.7. Пары (1, 2) и (2, 1) не совпадают, хотя множества {1, 2} и {2, 1} равны. ¤ Декартовым (прямым) произведением множеств A 1 , A 2 , . . ., A n называ- ется множество {(x 1 , x 2 , . . . , x n ) | x 1 ∈ A 1 , x 2 ∈ A 2 , . . . , x n ∈ A n }, обознача- емое через A 1 × A 2 × · · · × A n или n Q i=1 A i . Если A 1 = A 2 = . . . = A n = A, то множество A 1 × A 2 × . . . × A n называется n-й декартовой степенью мно- жества A и обозначается через A n . Положим по определению A 0 {∅}. Пример 1.1.8. Для множеств A = {1, 2} и B = {3, 4} имеем A × B = = {(1, 3), (1, 4), (2, 3), (2, 4)}, B×A = {(3, 1), (3, 2), (4, 1), (4, 2)}, A 2 = A×A = = {(1, 1), (1, 2), (2, 1), (2, 2)}. ¤ Пример 1.1.9 (шахматная доска). Рассмот- 6 - y x 0 1 1 Рис. 1.2 рим два множества A = {a, b, c, d, e, f, g, h} и B = {1, 2, 3, 4, 5, 6, 7, 8}. Тогда множеству пар (x, y) ∈ A × B соответствует множество кле- ток шахматной доски. ¤ Пример 1.1.10. Множество [0, 1] 2 равно мно- жеству {(a, b)| 0 6 a 6 1, 0 6 b 6 1}, которому со- ответствует множество точек на плоскости, имею- щих неотрицательные координаты, не превосходящие единицы (рис. 1.2). ¤ 20 Глава 1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ § 1.2. Отношения. Функции. Взаимно однозначные соответствия Часто при решении задач необходимо выбирать элементы, связанные некоторым соотношением. Примерами таких связей между элементами мо- гут служить функциональные зависимости или отношение “меньше либо равно”. Любое подмножество P прямого произведения A 1 × A 2 × . . . × A n на- зывается n-местным отношением или n-местным предикатом на множе- ствах A 1 , A 2 , . . . , A n . Другими словами, элементы x 1 , x 2 , . . . , x n (где x 1 ∈ A 1 , . . . , x n ∈ A n ) связаны соотношением P (обозначается P (x 1 , x 2 , . . . , x n )) тогда и только тогда, когда (x 1 , x 2 , . . . , x n ) ∈ P . При n = 1 отношение P является подмножеством множества A 1 и назы- вается унарным отношением или свойством. Наиболее часто встречаются двухместные отношения (n = 2). В этом слу- чае они называются бинарными отношениями или соответствиями. Таким образом, соответствием P между множествами A и B является подмноже- ство множества A × B. Если P ⊆ A × B и (x, y) ∈ P , то пишут также x P y. Отношение P ⊆ A n называется n-местным отношением (предикатом) на множестве A. Пример 1.2.1. Если A = {2, 3, 4, 5, 6, 7, 8}, то бинарное отношение P = {(x, y) | x, y ∈ A, x делит y и x 6 3} можно записать в виде P = {(2, 2), (2, 4), (2, 6), (2, 8), (3, 3), (3, 6)}. ¤ Пример 1.2.2. Рассмотрим отношение P = {(x, y) | x, y ∈ R, x 6 y} на множестве R. Тогда запись x P y означает, что x 6 y, и в качестве имени (обозначения) этого отношения можно взять сам символ 6. ¤ Пример 1.2.3 (ход ладьи). Рассмотрим множество шахматных клеток S = A × B из примера 1.1.9. Определим бинарное отношение C на мно- жестве S по следующему правилу: (c 1 , c 2 ) ∈ C тогда и только тогда, когда c 1 , c 2 ∈ S и ладья может пройти с клетки c 1 на клетку c 2 одним ходом на пустой доске (напомним, что ладья за один ход может изменить либо горизонтальную координату, либо вертикальную, но не обе координаты од- новременно). Нетрудно заметить, что C = {(c 1 , c 2 ) | c 1 = (s 1 , t 1 ), c 2 = (s 2 , t 2 ), s 1 , s 2 ∈ A, t 1 , t 2 ∈ B, и (s 1 = s 2 и t 1 6= t 2 ) или (s 1 6= s 2 и t 1 = t 2 )}. ¤ 1.2. ОТНОШЕНИЯ. ФУНКЦИИ. ВЗАИМНО ОДНОЗНАЧНЫЕ СООТВЕТСТВИЯ 21 Бинарные отношения P ⊆ A × B иногда удобно изображать графически. Рассмотрим два таких представления. Начертим пару взаимно перпендику- лярных осей (Ox — горизонтальная ось, Oy — вертикальная ось), на каж- дой оси отметим точки, представляющие элементы множеств A и B соот- ветственно. Отметив на плоскости точки с координатами (x, y) такие, что (x, y) ∈ P , получаем множество, соответствующее отношению P . На рис. 1.3 показано множество точек, соответствующих отношению из примера 1.2.1. Другой способ состоит в том, что элементы - 6 2 3 4 5 6 7 8 2 3 4 5 6 7 8 • • • • • |