Судоплатов С.В., Овчинникова Е.В. Дискретная математика. Учебник для дистанционного образования новосибирск 2011 Рецензенты А. Г. Пинус др физмат наук, проф
 Скачать 1.36 Mb.
|
|
Министерство образования и науки Российской Федерации НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ С. В. СУДОПЛАТОВ, Е. В. ОВЧИННИКОВА ДИСКРЕТНАЯ МАТЕМАТИКА УЧЕБНИК для дистанционного образования НОВОСИБИРСК 2011 Рецензенты А. Г. Пинус — др физмат. наук, проф.; В. М. Зыбарев — канд. техн.наук, доц. Сергей Владимирович Судоплатов Елена Викторовна Овчинникова Дискретная математика В книге излагаются основы теории множеств, алгебраических систем, теории графов и алгебры логики, которые образуют курс дискретной математики. Книга предназначена для студентов технических вузов, изучающих дискретную математику в рамках дистанционного образования Судоплатов СВ, Овчинникова Е.В., 2006, 2011 Оглавление Предисловие 5 Г лава. Элементы теории множеств 1.1. Множества и основные операции над ними . . . . . . . . . . . . . . . . . . . 6 § 1.2. Отношения. Функции. Взаимно однозначные соответствия . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 § 1.3. Натуральные числа. Принцип математической индукции . . . . . . . . . . . . . . . . . . . . . . . 17 § 1.4. Мощность множества. Конечные и бесконечные множества . . . . . . . . . . . . . . . . . . . . . . . 19 § 1.5. Матрица бинарного отношения. Специальные бинарные отношения . . . . . . . . . . . . . . . . . . . . . . . . 24 § 1.6. Отношения эквивалентности и разбиения. Фактор-множества . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 § 1.7. Отношения порядка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 § 1.8. Задачи и упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Глава. Алгебраические системы 2.1. Определения и примеры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 § 2.2. Морфизмы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 § 2.3. Подсистемы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 § 2.4. Конгруэнции. Фактор-алгебры. Теорема о гомоморфизме . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 § 2.5. Решетки и булевы алгебры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 § 2.6. Алгебры отношений и реляционные алгебры . . . . . . . . . . . . . . . . . . 47 § 2.7. Задачи и упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Глава. Элементы теории графов 3.1. Виды и способы задания графов . . . . . . . . . . . . . . . . . . . . . . . . . 52 § 3.2. Подграфы и части графа. Операции над графами . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 § 3.3. Маршруты. Достижимость. Связность . . . . . . . . . . . . . . . . . . . . . . 61 § 3.4. Расстояния в графах . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 § 3.5. Нахождение кратчайших маршрутов . . . . . . . . . . . . . . . . . . . . . . . 67 § 3.6. Степени вершин . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 § 3.7. Обходы графов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 § 3.8. Остовы графов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 § 3.9. Фундаментальные циклы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 § 3.10. Разрезы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 § 3.11. Раскраски графов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 § 3.12. Планарные графы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 § 3.13. Задачи и упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Глава. Алгебра логики 4.1. Формулы алгебры логики . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 § 4.2. Функции алгебры логики . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 § 4.3. Эквивалентность формул . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 § 4.4. Дизъюнктивные и конъюнктивные нормальные формы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 § 4.5. Двухэлементная булева алгебра. Фактор-алгебра алгебры формул . . . . . . . . . . . . . . . . . . . . . . . . . 99 § 4.6. Минимизация булевых функций в классе ДНФ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 § 4.7. Карты Карно . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 3 § 4.8. Принцип двойственности для булевых функций . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 § 4.9. Полные системы булевых функций . . . . . . . . . . . . . . . . . . . . . . . . 106 § 4.10. Логические сети . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 § 4.11. Проверка теоретико-множественных соотношений с помощью алгебры логики . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 § 4.12. Задачи и упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Варианты контрольной работы 4 ПРЕДИСЛОВИЕ Книга предназначена для студентов младших курсов технических вузов, изучающих дискретную математику дистанционно, и написана на основе учебника Судоплатов СВ, Овчинникова Е. В. Дискретная математика Учебник — М.:ИНФРА-М, Новосибирск Изд-во НГТУ, 2005, доступного через библиотеку НГТУ, киоск НГТУ или Интернет-магазины России. Материал учебника составлен в соответствии с рабочими программами курсов дискретной математики, читаемых в НГТУ. Учебник включает четыре раздела элементы теории множеств, алгебраические системы, теория графов, алгебра логики. В конце книги приведены варианты контрольной работы. Вариант N контрольной работы студента вычисляется по формуле = k + 25 · m, где k — число, состоящее из последних двух цифр личного шифра студента, а целое число m выбирается так, чтобы значение находилось в пределах от 1 до Перед решением задач контрольной работы полезно прорешать задачи и упражнения, помещенные в конце соответствующих разделов. В конце каждой главы помещены ссылки на примеры, которые являются аналогами соответствующих задач контрольной работы. Знак , используемый в тексте, означает конец рассуждения или его отсутствие. Знак читается положим по определению, обозначим или имеет вид, знак ⇔ — тогда и только тогда, знак ⇒ если ..., то ...”, знак ∀ — для любо о, знак ∃ — существует Глава ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ Множества и основные операции над ними Понятия множества и элемента множества относятся к понятиям, не определимым явно, таким, как, например, точка и прямая. Это связано стем, что некоторые понятия в математике должны быть исходными, служить теми кирпичиками, из которых складывается общая теория. Мы определяем только, как соотносятся эти исходные понятия, не говоря о природе рассматриваемых объектов. Под множеством M понимается совокупность некоторых объектов, которые будут называться элементами множества M. Тот факт, что x является элементом множества M , будем обозначать через x ∈ читается “x принадлежит M”), а если x не является элементом множества, то будем писать x / ∈ M (читается “x не принадлежит Заметим, что элементы множества сами могут являться множествами. Например, множество групп студентов состоит из элементов (групп), которые, в свою очередь, состоят из студентов. Множество можно задать перечислением принадлежащих ему элементов или указанием свойств, которым элементы множества должны удовлетворять. Если x 1 , x 2 , . . . , x n — все элементы множества M, то будем писать M = {x 1 , x 2 , . . ., x n }. Пусть имеется свойство P , которым могут обладать или не обладать элементы некоторого множества Тогда множество M, состоящее из всех элементов множества A, обладающих свойством P , будет обозначаться через {x ∈ A | x обладает свойством P }, а также {x | x обладает свойством P }, {x | P (или {x} P (x) , когда из контекста ясно, о каком множестве A идет речь. Мы будем использовать следующие обозначения для числовых множеств или ω — множество натуральных чисел, Z — множество целых чисел, Q — множество рациональных чисел, R — множество вещественных чисел, C — множество комплексных чисел 1.1. МНОЖЕСТВА И ОСНОВНЫЕ ОПЕРАЦИИ НАД НИМИ 7 П р им ер. Множество M арабских цифр можно задать двояко перечислением M = {0, 1, 2, . . . , 9} или посредством свойства = {x | x — арабская цифра}. П р им ер. Множество нечетных чисел {±1, ±3, ±5, . . можно определить как {x | x = 2k + 1 для некоторого k ∈ Множество A называется подмножеством множества B обозначается, если все элементы множества A принадлежат B: A ⊆ B ⇔ ∀x(x ∈ A ⇒ x ∈ Другими словами, это означает справедливость следующего утверждения для любого элемента x, если x ∈ A, то x ∈ B. Если A ⊆ то будем также говорить, что множество A содержится вили имеется включение множества A в B. Множества A и B называются равными или совпадающими (обозначается A = B), если они состоят из одних и тех же элементов, те. если A ⊆ B и B ⊆ A. Таким образом, чтобы доказать равенство множеств, требуется установить два включения. П р им ер. Справедливы следующие включения N ⊆ Z, Z ⊆ Q, Q ⊆ R, R ⊆ Пример. Покажем, что множества M 1 {x | sin x = 1} и | x = π 2 + 2kπ, k ∈ Z} совпадают. Если x ∈ M 1 , то x является решением уравнения sin x = 1. Но это значит, что x можно представить в виде x = π 2 +2kπ и поэтому x ∈ Таким образом, M 1 ⊆ M 2 . Если же x ∈ M 2 , те, тот. е. M 2 ⊆ M 1 . Следовательно, M 1 = Запись A ⊂ B или A B означает, что A ⊆ B и A = B (A неравно, ив этом случае будем говорить, что A строго включено вили является собственным подмножеством B. Так, включения из примера 1.1.3 являются строгими. Заметим, что X ⊆ X; если X ⊆ Y и Y ⊆ Z, то X ⊆ Z; если X ⊆ и Y ⊆ X, то X = Y Не следует смешивать отношение принадлежности ∈ и отношение включения ⊆. Хотя 0 ∈ {0} и {0} ∈ {{0}}, неверно, что 0 ∈ поскольку единственным элементом множества {{0}} является Совокупность всех подмножеств множества A называется его буле- аном или множеством-степенью и обозначается через P(A) или Таким образом, P(A) {B|B ⊆ Мы будем предполагать, что существует множество, не содержащее ни одного элемента, которое называется пустыми обозначается через ∅. Ясно, что ∅ ⊆ A для любого множества A. Глава 1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ П р им ер. Если A = {1, 2, 3}, то P(A) = {∅, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, Множество, содержащее все элементы, находящиеся в рассмотрении, называется универсальным или универсумом и обозначается через. Рассмотрим операции на булеане 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}. Пересечение множеств A и B называется также их произведением и обозначается A · B, а объединение — суммой A + Множество A \ B A − B {x|x ∈ A и x / ∈ B} называется разностью множеств A и B, множество A⊕B A ˙ −B (A\B)∪(B \A) кольцевой суммой или симметрической разностью множеств A и а множество A U \ A — дополнением множества A в U (см. рис. на котором изображены так называемые диаграммы Эйлера—Венна, наглядно поясняющие соотношения между множествами). П р им ер. Докажем, что A \ B = A Сначала установим, что A \ B ⊆ A ∩ B. Пусть x — произвольный элемент A \ B. Тогда по определению разности множеств имеем x ∈ и x / ∈ B, отсюда x ∈ A и x ∈ B, значит, x ∈ A ∩ B. Теперь покажем, что A ∩ B ⊆ A \ B. Если x ∈ A ∩ B, то x ∈ A и x ∈ B, поэтому x ∈ и x / ∈ B, значит, x ∈ A \ B. На основании включений A \ B ⊆ A ∩ B и ∩ B ⊆ A \ B делаем вывод, что A \ B = A ∩ B. U A U A U A "! # B "! # B "! # B A ∪ B A ∩ B A \ B A ⊕ B A U A U A "! # Рис. 1.1 1.1. МНОЖЕСТВА И ОСНОВНЫЕ ОПЕРАЦИИ НАД НИМИ 9 Аналогично примеру 1.1.6 устанавливаются следующие основные свойства операций пересечения, объединения и дополнения. Ассоциативность операций и ∩: 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. Законы дистрибутивности ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C), A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C). 5. Законы поглощения ∪ (A ∩ B) = A, A ∩ (A ∪ B) = A. 6. Законы де Моргана ∪ B = A ∩ B, A ∩ B = A ∪ B. 7. Законы нуля и единицы положим 0 ∅, 1 U, тогда ∪ 0 = A, A ∩ 0 = 0, A ∪ 1 = 1, A ∩ 1 = A, A ∪ A = 1, A ∩ A = 0. 8. Закон двойного отрицания = Отметим, что на основании примера 1.1.6 операция \ выражается через операции и . По закону де Моргана и закону двойного отрицания справедливо соотношение A∪B = A ∩ B, те. операция также выражается через операции и . По определению операция ⊕ тоже выражается через и. Таким образом, любая из определенных операций надмножествами выражается через операции и . Глава 1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ Пересечение и объединение могут быть определены для любого множества множеств A i , где индексы i пробегают множество I. Пересечение и объединение ∪ {A i | i ∈ I} задаются равенствами i ∈ I} {x | x ∈ A i для всех i ∈ I}, ∪ {A i | i ∈ I} {x | x ∈ A i для некоторого i ∈ Вместо ∩ {A i | i ∈ I} и ∪ {A i | i ∈ 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 = j. Другими словами, множество {A i | i ∈ I} непустых подмножеств множества A является его разбиением, если каждый элемент x ∈ A принадлежит в точности одному из подмножеств A i , каждое из которых не является пустым. Предложение 1.1.1. Следующие условия эквивалентны) A ⊆ B; 2) A ∩ B = A; 3) A ∪ B = B; 4) A \ B = ∅; 5) A ∪ B = Доказательство. Так как 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 = ∅, те. Тогда ∩ B = 0 = 1. По закону де Моргана и закону двойного отрицания получаем U = 1 = A ∩ B = A ∪ B = A ∪ B. 5 ⇒ 1. Предположим, что A ∪ B = U и не выполняется условие ⊆ B, те. найдется элемент x такой, что x ∈ A и x / ∈ B. Тогда x / ∈ и, значит, x / ∈ A ∪ B, а это противоречит равенству A ∪ B = Упорядоченную последовательность из n элементов x 1 , x 2 , . . . , x будем обозначать через (x 1 , x 2 , . . . , x n ) или x 1 , x 2 , . . . , x n . Здесь круглые или угловые скобки используются для того, чтобы указать на порядок, в котором записаны элементы. Будем называть такую последовательность упорядоченным набором длины n, кортежем длины n 1.2. ОТНОШЕНИЯ. ФУНКЦИИ. ВЗАИМНО ОДНОЗНАЧНЫЕ СООТВЕТСТВИЯ 11 или просто кой. Элемент x называется й координатой кортежа x 1 , x 2 , . . . , x n . В теории множеств кортежи кодируются с помощью операции взятия множества по двум элементам в соответствии со следующими правилами, x 1 x 1 , x 1 , x 2 {{x 1 }, {x 1 , x 2 }}, x 1 , x 2 . . . , x n+1 x 1 , x 2 . . . , x n , x Заметим, что две кии равны (x = y) тогда и только тогда, когда x 1 = y 1 , x 2 = y 2 , . . ., x n = y Пример. Пары (1, 2) и (2, 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 i=1 A i . Если A 2 = . . . = A n = A, то множество A 1 ×A 2 × × . . .×A n называется й декартовой степенью множества A и обозначается через Положим по определению Пример. Для множеств A = {1, 2} и B = {3, 4} имеем × B = {(1, 3), (1, 4), (2, 3), (2, 4)}, B × A = {(3, 1), (3, 2), (4, 1), (4, 2)}, A × A = {(1, 1), (1, 2), (2, 1), (2, Пример. (шахматная доска. Рассмотрим два множества = {a, b, c, d, e, f, g, h} и B = {1, 2, 3, 4, 5, 6, T E y x 0 Рис. 1.2 7, 8}. Тогда множеству пар (x, y) ∈ A × B соответствует множество клеток шахматной доски. П р им ер Множество [0, равно множеству {(a, b)| 0 a 1, 0 b 1}, которому соответствует множество точек на плоскости, имеющих неотрицательные координаты, не превосходящие единицы (рис. 1.2). § Отношения. Функции. Взаимно однозначные соответствия Часто при решении задач необходимо выбирать элементы, связанные некоторым соотношением. Примерами таких связей между элементами могут служить функциональные зависимости или отношение “меньше либо равно”. n-Местным отношением или местным предикатом P на множествах A 1 , A 2 , . . . , A n называется любое подмножество прямого произведения A 1 × A 2 × . . . × A n . Другими словами, элемен- Глава 1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ ты x 1 , x 2 , . . . , x где x 1 ∈ A 1 , . . . , x n ∈ A n ) связаны соотношением (обозначается P (x 1 , x 2 , . . . , x n )) тогда и только тогда, когда, x 2 , . . . , x n ) ∈ P При n = 1 отношение P является подмножеством множества и называется унарным отношением или свойством. Наиболее часто встречаются двухместные отношения (n = В этом случае они называются бинарными отношениями или соответствиями. Таким образом, соответствием P между множествами и B является подмножество множества A × B. Если P ⊆ A × B и, y) ∈ P , то пишут также x P Отношение P ⊆ A n называется местным отношением (предикатом) на множестве Пример. Если A = {2, 3, 4, 5, 6, 7, 8}, то бинарное отношение делит y и x 3} можно записать в виде = {(2, 2), (2, 4), (2, 6), (2, 8), (3, 3), (3, Пример. Рассмотрим отношение P = {(x, y) | x, y ∈ R, x y} на множестве R. Тогда запись x P y означает, что x y, ив качестве имени (обозначения) этого отношения можно взять сам символ Пример (ход ладьи. Рассмотрим множество шахматных клеток S = A × B из примера 1.1.9. Определим бинарное отношение на множестве S последующему правилу (c 1 , c 2 ) ∈ C тогда и только тогда, когда c 1 , c 2 ∈ S и ладья может пройти с клетки на клетку одним ходом на пустой доске (напомним, что ладья за один ход может изменить либо горизонтальную координату, либо вертикальную, ноне обе координаты одновременно. Нетрудно заметить, что 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 ∈ и (s 1 = и t 1 = t 2 ) или (s 1 = и t 1 = Бинарные отношения P ⊆ A × B иногда удобно изображать графически. Рассмотрим два таких представления. Начертим пару взаимно перпендикулярных осей (Ox — горизонтальная ось, Oy — вертикальная ось, на каждой оси отметим точки, представляющие элементы множеств A и B соответственно. Отметив на плоскости точки с координатами) такие, что (x, y) ∈ P , получаем множество, соответствующее отношению P . На рис. 1.3 показано множество точек, соответствующих отношению из примера Другой способ состоит в том, что элементы x ∈ A и y ∈ B, связанные отношением P , соединяются стрелками. П р им ер. На рис. 1.4 графически показано отношение P 1 = {(a, 2), (b, 1), (c, 2)} между множествами A = {a, b, c} и B = {1, 2, 3}, 1.2. ОТНОШЕНИЯ. ФУНКЦИИ. ВЗАИМНО ОДНОЗНАЧНЫЕ СООТВЕТСТВИЯ 13 а также отношение P 2 = {(a, b), (b, b), (c, a)} на множестве Для любого множества A определим тож- E T 2 3 4 5 6 7 8 2 3 4 5 6 7 8 • • • • • • O x Рис. 1.3 дественное отношение id A {(x, x) | x ∈ и универсальное отношение U A A 2 . Отношение называется также диагональю, а полным отношением. Пусть P — некоторое бинарное отношение. Областью определения отношения P называется множество | (x, y) ∈ P для некоторого областью значений отношения P — множество | (x, y) ∈ P для некоторого Обратным к P отношением называется множество, x) | (x, y) ∈ P Образом множества X относительно предиката P называется множество для некоторого x ∈ прообразом множества X относительно P — множество P −1 (X) или, другими словами, образ множества X относительно предиката Пример. Для отношения P из примера 1.2.1 и множества = {3} имеем δ P = {2, 3}, ρ P = {2, 3, 4, 6, 8}, P −1 = {(2, 2), (4, 2), (6, 2), (8, 2), (3, 3), (6, 3)}, P (X) = {3, 6}, P −1 (X) = {3}. ' & $ % ' & $ % P 1 d d d d d d d d d E Рис. 1.4 Глава 1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ Рис. Произведением бинарных отношений P 1 ⊆ A × B и P 2 ⊆ B × C или композицией и называется множество P 1 ◦ P 2 = {(x, y) | x ∈ ∈ A, y ∈ C, и найдется элемент z ∈ B такой, что (x, z) ∈ ирис. В дальнейшем произведение будем также обозначать через Предложение 1.2.1. Для любых бинарных отношений P , Q, выполняются следующие свойства) (P −1 ) −1 = P ; 2) (P ◦ Q) −1 = Q −1 ◦ P −1 ; 3) (P ◦ Q) ◦ R = P ◦ (Q ◦ R) (ассоциативность композиции). Ассоциативность композиции позволяет обозначать композицию ◦ Q) ◦ R = P ◦ (Q ◦ R) через P QR. По этой же причине однозначно определена композиция P 1 P 2 . . . P n двухместных предикатов, P 2 , . . . , P n . Отметим, что существуют предикаты P и Q, для которых не выполняется закон коммутативности P ◦ Q = Q ◦ P (приведите примеры таких предикатов). Отношение f ⊆ A×B называется функцией или отображением из множества A в множество B, если δ f = A, ρ f ⊆ B и из (x, y 1 ) ∈ f , (x, y 2 ) ∈ f следует y 1 = Если вместо δ f = A выполняется A, то f называется частичной функцией. Функция f изв обозначается через f : A → B или A f → B. Если (x, y) ∈ f , то пишем y = f (x) (y — значение функции f при значении аргумента x) или f : x → y (функция f ставит в соответствие элементу x элемент Пример. Отношение {(1, 2), (2, 3), (3, 2)} ⊆ {1, 2, функция, отношение {(1, 2), (1, 3), (2, 3)} не является функцией, а отношение функция, которая обычно обозначается через y = x 2 − 2x + Тождественное отношение id A = {(x, x) | x ∈ A} является функцией, для которой id A (x) = x при всех x ∈ A. Други- 1.2. ОТНОШЕНИЯ. ФУНКЦИИ. ВЗАИМНО ОДНОЗНАЧНЫЕ СООТВЕТСТВИЯ 15 ми примерами функций являются проекции π A,B 1 : A× ×B → и π A,B 2 : A × B → B, которые задаются последующим правилам, b)) a, π A,B 2 ((a, Функция f называется разнозначной, инъективной (инъекцией) или 1-1-функцией, если отношение является частичной функцией, т. е. для любых элементов x 1 , x 2 ∈ δ f из x 1 = следует f (x 1 ) = f (Если f — инъекция, то будем писать f : A 1−1 −−→ Функция f : A → B называется функцией A на B или сюръектив- ной функцией (сюръекцией), если ρ f = B. Если f — сюръекция, то будем писать f : на Функция f называется взаимно однозначным соответствием между множествами A и B или биективной функцией (биекцией), если f — разнозначное отображение A на B. Таким образом, функция является биекцией, если она инъективна и сюръективна. Если f — би- екция между A и B, то будем писать f : A ↔ B. Биекция f : A ↔ называется подстановкой множества A. Простейшим примером подстановки является функция Пример. На рис. 1.6 графически показаны функции f i : [0, 1] → [0, 1], i ∈ {1, 2, 3, 4}. Функция f 1 сюръективна, ноне инъектив- на, функция f 2 инъективна, ноне сюръективна, функция f 3 биективна и является подстановкой, а функция не инъективна и не сюръек- тивна. П р им ер. Рассмотрим три функции f i : R → R, i = 1, 2, 3: 1) функция f 1 (x) = e x инъективна, ноне сюръективна; 2) функция f 2 (x) = x · sin x сюръективна, ноне инъективна; 3) функция f 3 (x) = 2x − 1 биективна. E x T y O 1 Рис. 1.6 Глава 1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ П р им ер. Биекцией между множеством натуральных чисел = {0, 1, 2, . . .} и множеством целых чисел Z = {0, ±1, ±2, . . является функция f : N → Z, для которой f (n) если n = 2m − 1, −m, если n = Предложение 1.2.2. 1. Если f : A → B и g : B → C, то f ◦ g : A → C. 2. Если f : A → B, то id A ◦ f = f , f ◦ id B = f . 3. Если f : на B, g : на C, тона. Если f и g — разнозначные отображения, то f ◦ g — разнозначное отображение. Если : A ↔ B, g : B ↔ C, то f ◦ g : A ↔ C. 6. Если f : A ↔ то f −1 : B ↔ A, f ◦ f −1 = id A , f −1 ◦ f = Если f — отображение и X ⊆ δ f , то множество {f (x)|x ∈ ∈ X} называется образом множества X при отображении f и обозначается через f (X), а отображение f ∩ (X × ρ f ) называется ограничением f на X и обозначается через f или Функция f : N → называется последовательностью. Ее можно представить в виде f (0), f (1), f (2), . . . , f (n), . . . или b 0 , b 1 , . . . , b n , . . ., где b n = f (n), n ∈ Множество всех функций изв обозначается через B A : B A {f |f : A → Функция f : A n → B называется местной функцией изв Если y — значение местной функции f при значении аргумента, x 2 , . . . , x n ), то пишем y = f (x 1 , x 2 , . . . , x n ). Функция f : A n → называется местной алгебраической операцией на множестве A. При n = 1 операция f называется унарной, при n = 2 — бинарной, а в общем случае — n-арной. При n = 0 операция f : A 0 → A есть множество {(∅, a)} для некоторого a ∈ A. Часто местную операцию на A будем называть константой на A и отождествлять с элементом Пример. Операция сложения вещественных чисел является двухместной, те. бинарной операцией + : R 2 → → R, которая паре чисел (a, b) ставит в соответствие число a + b по обычному правилу. Любой выделенный элемент множества R, например, является местной операцией, те. константой на R. 1.3. НАТУРАЛЬНЫЕ ЧИСЛА. ПРИНЦИП МАТЕМАТИЧЕСКОЙ ИНДУКЦИИ Натуральные числа. Принцип математической индукции Рассмотрим два подхода к заданию множества натуральных чисел. Первый подход — конструктивный — позволяет представлять натуральные числа в виде объектов, построенных из пустого множества. Второй подход — аксиоматический. Согласно этому подходу натуральные числа образуют множество, удовлетворяющее некоторому набору свойств (аксиом, и при этом природа элементов множества не важна. Таким образом, с одной стороны, указывается множество натуральных чисел, ас другой стороны — все существенные (определяющие) свойства этого множества. Положим по определению 0 ∅, 1 {0} тете 1}, . . . Множества, обозначаемые 0, 1, 2, . . . , n, . . ., называются натуральными числами. Объединив эти множества, получаем множество всех натуральных чисел {0, 1, 2, . . . , n, . . .}, обозначаемое через В силу обозначений предыдущего параграфа, если A = n = = {0, 1, . . . , n − 1}, B = 2 = {0, 1}, то B A = {f |f : n → {0, Обозначение согласуется стем, что в множестве имеется ровно функций. Действительно, поскольку функция f на каждом аргументе может принимать одно из двух значений 0 или 1 и таких элементов i ровно n, то всего имеется 2 · 2 · . . . · 2 = 2 n различных функций. Аналогично имеем 2 ω = {f | f : ω → {0, 1}} — множество, состоящее из всех последовательностей нулей и единиц. Как уже отмечалось, второй подход к определению множества натуральных чисел является аксиоматическим. Мы рассмотрим аксиоматику Дедекинда—Пеано. Пусть имеется некоторое множество N, в котором выбран элемент, обозначаемый через 0, и функция, которая произвольному элементу n ∈ N ставит в соответствие элемент n ∈ N , называемый непосредственно следующим (элемент n играет роль числа n + 1). Таким образом, с помощью функции n → n можно однозначно найти элементы , 0 , 0 и т. д. (элемент играет роль числа n). Множество N называется множеством натуральных чисел, если система N N; удовлетворяет следующим аксиомам) для любого m = 0 найдется n ∈ N такой, что n = m; 2) для любых m, n ∈ N, если m = n , то m = n; Глава 1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ) n = 0 для любого n ∈ N ; 4) (аксиома математической индукции) для любого свойства унарного отношения на множестве N), если P выполняется на элементе те обладает свойством P ), и для любого n ∈ N из выполнимости на элементе n следует выполнимость P на элементе n , то свойство P выполняется на любом элементе n ∈ N Последняя аксиома является наиболее содержательной, она символически записывается следующим образом (P (0), ∀n(P (n) ⇒ P (n )) ⇒ ∀nP (n) а также (0), ∀n(P (n) ⇒ P (n + 1)) ∀n P (или ∈ P, ∀n(n ∈ P ⇒ (n + 1) ∈ P ) P = Итак, утверждение для любого n ∈ N выполняется P (n)” считается доказанным, если установлены базис индукции (доказано P (и индукционный шаг (доказано, что для любого n ∈ N справедливо (n + 1) в предположении, что выполняется P (n)). В этом состоит принцип математической индукции. Принцип математической индукции позволяет также давать индукционные определения, те. определения понятий P (n) для всех натуральных чисел n, построенные последующей схеме) задается значение P (0); 2) задается правило получения значения P (n + 1) по числу n и значению P (Определим по индукции операции сложения a + b и умножения a · b на натуральных числах. Положим a + 0 a (базис индукции). Если известно значение a + n, то a + n (a + n) (индукционный шаг. Аналогично a · 0 0. Если задано a · n, то a · n (a · n) + Используя операцию сложения, можно ввести отношение на множестве натуральных чисел a b ⇔ ∃ c(a + c = Определим по индукции функцию n! (факториал 0! 1, (n+ + 1)! n! · (n + Пример. Докажем по индукции неравенство Бернулли + a) n 1 + an для всех n ∈ N и a > −1, a ∈ При n = 0 неравенство имеет вид (1 + a) 0 1 + a · 0 и оно справедливо, те. базис индукции выполняется. Установим справедливость индукционного шага. Предположим, что + a) n 1 + an, (1.1) 1.4. МОЩНОСТЬ МНОЖЕСТВА 19 и покажем, что + a) n+1 1 + a(n + Умножим обе части неравенства (1.1) на положительное число 1 + Тогда (1 + a) n (1 + a) (1 + an)(1 + a), те+ Поскольку a 2 0, имеем + a + an + a 2 n 1 + a + an = 1 + a(n + Из неравенств (1.3) и (1.4) получаем неравенство (1.2). На основании принципа математической индукции заключаем, что (1 + a) n 1 + an для всех n ∈ Иногда удается установить только выполнение P (k) для некоторого k > 0 и свойство P (n) ⇒ P (n + 1) для всех n k. Тогда по принципу математической индукции свойство P выполняется для всех n k: P (k), ∀n k (P (n) ⇒ P (n + 1)) ∀n k P (Другой эквивалентной формой принципа математической индукции является принцип полной индукции: если для всякого n ∈ N из предположения, что P (k) верно при любом натуральном k < n, следует, что P (k) верно также при k = то P (n) верно при любом натуральном n: ∀n ((∀k < n P (k)) ⇒ P (n)) ∀n P (Эта форма используется в том случае, когда для доказательства выполнимости) необходимо использовать выполнимость свойства не только на элементе n, но и на некоторых предыдущих элементах Мощность множества. Конечные и бесконечные множества Понятие мощности возникает при сравнении множеств по числу элементов. Множества A и B называются эквивалентными (обозначается ∼ B), если существует биекция f : A ↔ Отметим, что для любых множеств A, B, C выполняются следующие свойства Глава 1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ) A ∼ A (поскольку id A : A ↔ A); 2) если A ∼ B, то B ∼ A (так как из f : A ↔ B следует f −1 : B ↔ A); 3) если A ∼ B и B ∼ C, то A ∼ C (так как из f : A ↔ B, g : B ↔ следует f ◦ g : A ↔ Мощностью множества A называется класс всех множеств, эквивалентных множеству A (обозначается |A|). Эквивалентные множества и B называются равномощными: |A| = |B|. Если A ∼ n для некоторого, те имеет ровно n элементов, то множество A называется конечным. В этом случае пишут |A| = n. Таким образом, мощностью конечного множества является число его элементов. Множество, не являющееся конечным, называется бесконечным. Если, то множество A называется счетным |A| = ω. Если ∼ 2 ω , то множество A называется континуальным или континуумом На мощность множества A можно смотреть и как на новый объект, называемый кардинальным числом или кардиналом. В качестве примеров кардиналов можно взять любое натуральное число n, а также, 2 ω , 2 и т. д. Эти числа можно рассматривать как имена, обозначающие соответствующие мощности. Кардинальным числом конечного множества служит число его элементов. Существование биекции между двумя эквивалентными множествами позволяет переносить изучение свойств с одного множества на другое, когда природа элементов неважна. Например, если |A| = n, то с элементами множества A можно работать как с числами 0, 1, 2, . . . . . . , n − 1, которые являются элементами множества Говорят, что мощность множества A не превосходит мощности множества, если A эквивалентно некоторому подмножеству множества B. Мощность множества A меньше мощности множества |A| < |B|, если |A| |B| и |A| = Теорема 1.4.1 (теорема Кантора—Бернштейна). Если |A| |B| и, то |A| = Следствие 1.4.2 (теорема о сравнении множеств. Для любых множеств и B существует одна и только одна из следующих возможностей Определим на кардинальных числах операции сложения, умножения и возведения в степень. Если |A| = α, |B| = β, то + β |A ∪ B|, где A ∩ B = ∅; α · β |A × B|; α β |A B |. 1.4. МОЩНОСТЬ МНОЖЕСТВА 21 В случаях, когда α, β ∈ ω, введенные таким образом операции совпадают с обычными операциями на натуральных числах. Для конечных кардиналов справедливы следующие три правила, используемые в комбинаторике. Правило суммы. Если |A| = m, |B| = n, то |A∪B| = ив томи только том случае, когда A ∩ B = Правило произведения. Если |A| = m, |B| = n, то |A × B| = m · Правило степени. Если |A| = m, |B| = n, то |A B | = m Следующее утверждение показывает, что операции на бесконечных кардиналах могут иметь необычные свойства. Предложение 1.4.3. Доказательство. По определению множество ω 2 = ω × равно {(m, n) | m, n ∈ ω}. На координатной плоскости изобразим точки с натуральными координатами (m, n) T E • • • • • • • • • • d d d d d d d d d d d d d d d d d d d d d d d d d d d d (0, 0) (0, 1) (0, 2) (0, 3) (1, 0) (2, 0) (3, 0) (1, 1) (1, 2) (2, 1) 0 1 3 6 2 5 9 4 7 Рис. рис. Очевидно, что все эти точки расположены впервой четверти. Для доказательства утверждения требуется установить биекцию между множеством натуральных чисел и полученными точками, т. е. перенумеровать точки. Нумеруем точки по диагонали 0 → (0, 0), 1 → (0, 1), 2 → (1, 0), 3 → (0, 2), 4 → (1, 1), 5 → (2, 0), 6 → (0, 3), 7 → (1, 2) и т. д. Так как указанная нумерация разнозначна и каждая пара натуральных чисел имеет натуральный номер, то это отображение осуществляет взаимно однозначное соответствие ↔ Предложение 1.4.4. ω Доказательство. Так как для любого n ∈ ω существует биекция f n : ω ↔ ω n , то достаточно установить, что найдется биекция ϕ : ω ↔ ( ∪ 1 n∈ω {(n, k) | k ∈ ω}) ∪ {∅}, те. Биекция ϕ легко строится с помощью биекции ψ : ω ↔ из предложения 1.4.3: ϕ(0) = ∅, ϕ(m + 1) = (n + 1, k), где) = (n, k), m ∈ Предложение 1.4.5. |Q| = Доказательство. Поскольку множество рациональных чисел состоит из дробей вида m n , где m ∈ Z, n ∈ ω \ {0}, его можно представить в виде множества пар (m, n). Так как множество таких Глава 1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ пар содержится в Z 2 , а |Z 2 | = ω, то |Q| ω. С другой стороны, очевидно, множество Q бесконечно, те. По теореме Кантора— Бернштейна заключаем, что |Q| = Теорема 1.4.6. Выполняется |P(U)| = 2 |U для любого множества Доказательство. Очевидно, что любому подмножеству A ⊆ ⊆ U взаимно однозначно ставится в соответствие индикаторная функция, для которой f (x) если x / ∈ если x ∈ те. Осталось заметить, что 2 |U | = Теорема 1.4.7 (теорема Кантора. Выполняется |U| < 2 |U для любого множества Предложение 1.4.8. Если |A| > ω и |B| ω, то |A \ B| = Доказательство. Так как |B| ω, то |A ∩ B| ω. Рассмотрим множество C со следующими условиями A ∩ B ⊂ C ⊂ A, |C \ (A ∩ B)| = ω. Такое множество C существует, поскольку по условию имеем |A \ B| > ω. Так как C = (C \ (A∩ ∩B)) ∪ (A то |C| = ω и существует биекция f : C \ (A ∩ B) ↔ C. Искомая биек- ция ϕ : A \ B ↔ A строится последующим правилам ϕ(x) = x, если x ∈ A \ C, ϕ(x) = f (x), если x ∈ C \ Предложение 1.4.9. Доказательство. Поскольку неравенства очевидны, достаточно доказать неравенство ω ω 2 ω , те. существование функции ϕ : ω ω 1−1 −−→ 2 ω , которая кодирует всевозможные последовательности натуральных чисел с помощью последовательностей, состоящих из нулей и единиц. Для последовательности f ∈ определим последовательность ϕ(f ) ∈ последующим правилам, 1, . . . , 1 f (0) раз, 0, 1, 1, . . . , 1 f (1) раз, 0, . . . , 1, 1, . . . , 1 f (n) раз, 0, . . Очевидно, что если f 1 = f 2 (f 1 , f 2 ∈ ω ω ), то ϕ(f 1 ) = Предложение 1.4.10. R ∼ [0, Доказательство. Равенство мощностей отрезка I 1 = [0, 1] и интервала I 2 = (0, 1) обеспечивается биекцией ϕ : I 1 ↔ I 2 , задаваемой 1.4. МОЩНОСТЬ МНОЖЕСТВА 23 по следующему правилу) если x = 0, x = 1 n , n ∈ ω \ {0}, 1 если x = 0, 1 если x = если x = 1 n , n > В свою очередь, биекция ψ(x) = tg (π(x − 1 2 )) (рис. 1.8) определяет эквивалентность интервала и множества R. Следовательно, R ∼ [0, Предложение 1.4.11. Множество вещественных чисел R кон- тинуально. Д ока за тел ь ст во. В силу предложений 1.4.9 и 1.4.10 достаточно установить, что 10 ω ∼ [0, 1]. Рассмотрим множество X = {f ∈ 10 ω |f (m) = 9 для некоторого m ∈ ω и существует k ∈ ω такое, что f (n) = 9 для всех n > k}. Так как множество 10 ω \ X взаимно однозначно соответствует множеству бесконечных десятичных дробей, задающих числа из [0, 1], то по теореме Кантора и предложению остается показать, что множество X счетно. Нетрудно заметить, что множество X эквивалентно множеству ∪ n∈ω ω n , поскольку каждая функция f ∈ X однозначно определяется кортежем цифр (0), . . . , f (k)), где f (k) = 9 и f (n) = 9 для всех n > k. Теперь из предложения 1.4.4 получаем X ∼ ∪ n∈ω ω n ∼ ω, те Рис. 1.8 Глава 1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ Матрица бинарного отношения. Специальные бинарные отношения Рассмотрим два конечных множества A = {a 1 , a 2 , . . ., a m }, B = = {b 1 , b 2 , . . . , b n } и бинарное отношение P ⊆ A×B. Определим матрицу) размера m × n бинарного отношения P последующему правилу если (a i , b j ) ∈ если (a i , b j ) / ∈ Полученная матрица содержит полную информацию о связях между элементами и позволяет представлять эту информацию на компьютере. Заметим, что любая матрица, состоящая из нулей и единиц, является матрицей некоторого бинарного отношения. П р им ер. Матрица бинарного отношения P ⊆ A 2 , A = {1, 2, 3}, заданного на рис. 1.9, имеет вид ] = 1 1 1 0 0 1 1 0 Отметим основные свойства матриц бинарных отношений. Если P, Q ⊆ A × B, [P ] = (p ij ), [Q] = (q ij ), то [P ∪ Q] = = (p ij + q ij ) и [P ∩ Q] = (p ij · q ij ), где сложе- • • • E © d d d d d d sd d d d d d ' 1 Рис. 1.9 ние осуществляется по правилам 0 + 0 0, 1 + 1 1+ +0 0 + 1 1, а умножение обычным образом. Итака матрица [P ∩ Q] получается перемножением соответствующих элементов из [P ] и [Q]: [P ∩ Q] = [P ] ∗ Пример. Пусть [P ] = ( 1 0 1 0 1 1 ), [Q] = ( 0 1 1 0 0 1 ) — матрицы отношений P и Тогда ∪ Q] = [P ] + [Q] = 1 0 1 0 1 1 + 0 1 1 0 0 1 = 1 1 1 0 1 1 , [P ∩ Q] = [P ] ∗ [Q] = 1 0 1 0 1 1 ∗ 0 1 1 0 0 1 = 0 0 1 0 0 1 2. Если P ⊆ A × B, Q ⊆ B × C, то [P ◦ Q] = [P ] · [Q], где умножение матриц [P ] и [Q] производится по обычному правилу умножения 1.5. МАТРИЦА БИНАРНОГО ОТНОШЕНИЯ 25 матриц, но произведение и сумма элементов из [P ] и [Q] — по определенным в п. 1 правилам. П р им ер. Если [P ] = ( 0 1 0 1 1 0 ), [Q] = 0 1 1 0 1 1 , то ◦ Q] = 0 1 0 1 1 0 · 0 1 1 0 1 1 = 1 0 1 1 3. Матрица обратного отношения равна транспонированной матрице отношения P : [P −1 ] = [P ] T 4. Если P ⊆ Q, [P ] = (p ij ), [Q] = (q ij ), то p ij q ij 5. Матрица тождественного отношения единична = 1 0 · · · 0 0 1 · · · 0 0 0 · · · Пусть P — бинарное отношение на множестве A: P ⊆ A 2 . Отношение называется рефлексивным, если (x, x) ∈ P для всех x ∈ A, те Отношение P называется симметричным, если для любых x, y ∈ из (x, y) ∈ P следует (y, x) ∈ P , те, или [P ] T = [P Отношение P называется антисимметричным, если из (x, y) ∈ и (y, x) ∈ P следует, что x = y, те. На языке матриц это означает, что в матрице [P ∩P −1 ] = [P ]∗[P все элементы вне главной диагонали являются нулевыми. Отношение P называется транзитивным, если из (x, y) ∈ P и (y, z) ∈ P следует (x, z) ∈ P , те Пример. Проверим, какими свойствами обладает отношение, изображенное на рис. 1.10. Составим матрицу отношения P : [P ] = 0 1 1 0 1 1 0 0 0 . Так как в матрице [P ] на главной диагонали имеются нулевые элементы, отношение P не рефлек- сивно. Несимметричность матрицы [P ] означает, что отношение P несимметрично. Для проверки антисимметричности вычислим матрицу Глава 1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ ∩ P −1 ] = [P ] ∗ [P ] T . Имеем ] ∗ [P ] T = 0 1 1 0 1 1 0 0 0 ∗ 0 0 0 1 1 0 1 1 0 = 0 0 0 0 1 0 0 0 Поскольку в полученной матрице все элементы, стоящие вне главной диагонали, нулевые, отношение P антисимметрично. Так как ◦ P ] = [P ] (проверьте, тот. е. P является транзитивным отношением. П р им ер. Отношение < {(x, y) | x, y ∈ • • • T E j 2 Рис. 1.10 ∈ Q и x < y} на множестве рациональных чисел не рефлексивно, несимметрично, антисимметрично и транзитивно. П р им ер. Рассмотрим отношение = {(x, y) | x, y ∈ Z и x − y < на множестве целых чисел Так как x−x = 0 < 1 для любого x ∈ Z, отношение P рефлексивно. Поскольку (2, 4) ∈ P , а (4, 2) / ∈ P , отношение P не симметрично. Заметим, что если x − y < 1 и y − x < 1, то x = y, так как из x = y следует |x − y| 1. Таким образом, отношение P антисимметрично. Предположим теперь, что (x, y), (y, z) ∈ P , те и y − z < Имеем x < y и y < z, тогда x < z, значит, x − z < 1, те Следовательно, отношение P транзитивно. § Отношения эквивалентности и разбиения. Фактор-множества Отношение P называется отношением эквивалентности (эквивалентностью, если P рефлексивно, симметрично и транзитивно. Эквивалентности часто обозначают символами E и тильда x E y, x Пример. Отношение равенства x = y является эквивалентностью на любом множестве A, так как оно рефлексивно (x = симметрично (x = y ⇒ y = x) и транзитивно (x = y, y = z ⇒ x = z). 2. Отношение подобия на множестве треугольников есть отношение эквивалентности. На любом множестве P(U) отношение равномощности |A| = является отношением эквивалентности (см. § 1.4). 4. Отношение принадлежности к одной студенческой группе на множестве студентов НГТУ — отношение эквивалентности 1.6. ОТНОШЕНИЯ ЭКВИВАЛЕНТНОСТИ И РАЗБИЕНИЯ 5. Рассмотрим множество M программ, вычисляющих некоторые функции. Отношение E = {(x, y) | программы x и y вычисляют одну и туже функцию является эквивалентностью. Пусть E — эквивалентность на множестве A. Классом эквивалентности элемента x ∈ A называется множество E(x) {y | x E Классы эквивалентности E будут также называться E-классами. Множество A/E {E(x)|x ∈ A} называется фактор-множеством множества A по отношению Пример. Для отношения равенства = на множестве каждый класс состоит только из одного элемента = (x) = для любого x ∈ A. Таким образом, фактор-множество A/= имеет вид | x ∈ A} и, следовательно, биективно множеству A. 2. Для отношения принадлежности к одной студенческой группе классом эквивалентности является множество студентов одной группы. Фактор-множество множества студентов НГТУ поэтому отношению эквивалентности представляет собой множество студенческих групп НГТУ. Предложение 1.6.1. Множество A/E является разбиением множества. Обратно, если R = {A i } — некоторое разбиение множества, то можно задать соответствующее ему отношение эквивалентности последующему правилу E y ⇔ x, y ∈ A i для некоторого Таким образом, существует биекция между множеством всех отношений эквивалентности на множестве A и множеством всех разбиений множества В любом классе E(x) эквивалентности E каждый элемент y ∈ связан отношением E с любым элементом z ∈ E(x). Поэтому если E эквивалентность наконечном множестве A, A/E = {E(x 1 ), . . . , E(x n )}, E(x i ) = {b i 1 , . . . , b i m i }, i = 1, . . . , n, и множество A перенумеровано в следующем порядке b 1 1 , . . . , b 1 m 1 , b 2 1 , . . . , b 2 m 2 , . . . , b n 1 , . . . , b n m n , то матрица имеет блочно-диагональный вид = m 1 m 2 m n m 1 { m 2 { m n { 1 0 1 где блоки 1 состоят из единица остальные элементы равны 0. Глава 1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ Если же множество A перенумеровано произвольным образом A = = {a 1 , . . . , a n }, E — отношение эквивалентности на A, то матрица = (e ij ) приводится к блочно-диагональному виду некоторыми одновременными перестановками строки столбцов. Элементы a и a эквивалентны по отношению E тогда и только тогда, когда я и я строки (а также столбцы) матрицы [E] совпадают. Класс эквивалентности) состоит из элементов a j , для которых e ij = Пример. Рассмотрим множество A = {1, 2, 3, 4, 5} с разбиением, задающим отношение эквивалентности с двумя классами {1, 3, 5} и {2, 4}. Матрица [E] имеет вид 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 . По этой матрице легко определить, что класс E(3) равен, 3, 5}, так как в й строке только e 31 , и равны 1. § Отношения порядка Отношение эквивалентности является обобщением отношения равенства эквивалентные элементы считаются равными. Обобщением обычного отношения служат отношения порядка. Отношение P ⊆ называется предпорядком или квазипорядком, если P рефлексивно и транзитивно. П р им ер. Отношение P = {(1, 1), (2, 2), (3, 3), (1, 2), (2, 1), (2, 3), (1, 3)} на множестве {1, 2, 3} является d d d E B % m % m ! m u 2 Рис. 1.11 предпорядком (рис. Отношение P ⊆ называется частичным порядком, если P рефлексивно, транзитивно и антисимметрично. Таким образом, частичный порядок это антисимметричный предпорядок. Частичный порядок обычно обозначается символом, а обратное ему отношение символом. Отношение также является частичным порядком и называется двойственным порядку. Используя отношение , определим отношение <, называемое строгим порядком, последующему правилу x < y ⇔ x y и x = y. Заметим, что отношение строгого порядка не является частичным порядком, так как не выполняется условие рефлексивности (неверно, что x < Пример. Частичным порядком является обычное отношение на множестве N. Действительно, это отношение рефлексивно (x x), транзитивно (x y, y z ⇒ x z) и антисимметрично y, y x ⇒ x = y). 1.7. ОТНОШЕНИЯ ПОРЯДКА 29 П р им ер. Отношение, изображенное на рис. 1.12, является частичным порядком, а отношение из примера 1.7.1 — нет. П р им ер. Отношение включения ⊆ на j j % % % a Рис. 1.12 булеане P(U) образует частичный порядок. Заметим, что в примерах 1.7.3 и 1.7.4 имеются элементы x и y, про которые нельзя сказать, что x y или y x (например, при a = x, y = c из примера 1.7.3). Такие элементы называются несравнимыми. Частичный порядок называется линейным порядком, если любые два элемента x и y из множества A сравнимы, те или y x (линейным является частичный порядок из примера Непустое множество A, на котором зафиксирован некоторый частичный (линейный) порядок, называется частично (линейно) упорядоченным множеством (сокращенно ч.у.м. или л.у.м.). П р им ер. Пары ω; , [0, с обычными отношениями образуют линейно упорядоченные множества. Элемент a ∈ A частично упорядоченного множества A = называется максимальным (минимальным, если для всех x ∈ A из a x (x a) следует x = a. Элемент a ∈ A называется наибольшим (наименьшим), если x a (a x) для всех x ∈ A. Наибольший (наименьший) элемент ч.у.м. A (если он существует) обозначается через max A (min A). Наибольший элемент часто называют единицей, а наименьший нулем множества A. Заметим, что всякий наибольший элемент является максимальным, а всякий наименьший элемент — минимальным. Обратное утверждение, вообще говоря, неверно (см. пример. Всякое конечное ч.у.м. содержит как максимальные, такими- нимальные элементы. П р им ер. Частично упорядоченное множество {1, 2, изображенное на рис. 1.13, имеет наибольший элемент 2, минимальные элементы 1, 3, ноне имеет наименьшего элемента. П р им ер. Линейно упорядоченное множе- • • • I q g g g ! ! u 1 Рис. 1.13 ство [0, имеет наименьший элемент 0, ноне имеет наибольшего элемента. Пусть A = A; — ч.у.м., B — подмножество Элемент a ∈ A называется верхней (нижней) гранью множества B, если b a (a b) для всех b ∈ Пример. Рассмотрим ч.у.м. и интервал B = (0, Тогда любое число x 1 является верхней гранью B, а любое число x 0 — нижней гранью B. Глава 1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ Элемент a ∈ A называется точной верхней гранью (супремумом) множества B (обозначается sup B), если a — наименьшая из верхних граней множества B. Элемент a ∈ A называется точной нижней гранью (инфимумом) множества B (обозначается inf B), если a — наибольшая из нижних граней множества В примере 1.7.8 имеем sup B = 1, inf B = Линейный порядок на множестве A называется полным, если каждое непустое подмножество множества A имеет наименьший элемент. Пара A; , в которой отношение является полным порядком на множестве A, называется вполне упорядоченным множеством (сокращенно в.у.м.). П р им ер. Пара является в.у.м., а пара [0, нет, поскольку, например, полуоткрытый интервал (1/2, 1], являющийся подмножеством [0, 1], не содержит наименьшего элемента. Определим отношение, на котором основано упорядочение слов в словарях. Рассмотрим непустое множество символов X = {x, y, z, . . .}, называемое алфавитом. Конечные наборы написанных друг за другом символов из X называются словами (например, x, y, xy, yx, zxx, xyyz и т. д. Элемент x слова x 1 x 2 . . . x называется его й координатой. Число n называется длиной слова x 1 x 2 . . . x n . Множество слов алфавита обозначим через W (X). При этом будем считать, что W (содержит слово Λ, не имеющее символов и называемое пустым словом. Длина пустого слова Λ по определению равна нулю. Заметим, что каждое слово x 1 x 2 . . . x из W (X) взаимно однозначно соответствует упорядоченному набору x 1 , x 2 , . . . , x из X n . Следовательно, множество W (X) биективно множеству ∪ n∈ω X n , и, значит, бесконечно. Пусть — отношение порядка на множестве X. Определим на множестве) отношение лексикографического порядка L последующему правилу x 1 x 2 . . . x m L y 1 y 2 . . . y n ⇔ (m n и x i = y для всех m) или (существует i m такое, что x i < y i , и для всех j < i выполняется x j = y Утверждение 1.7.1. Если X; — л.у.м., то W (X); L — л.у.м. Обозначим через W n (X) множество слов алфавита X, длина которых не превосходит n, через L n — ограничение отношения L на множество Утверждение 1.7.2. Если X; — в.у.м., то W n (X); L n — в.у.м. для любого n ∈ ω. 1.7. ОТНОШЕНИЯ ПОРЯДКА 31 Рассмотрим частично упорядоченное множество A; . Говорят, что элемент y покрывает элемент x, если x y и не существует такого элемента z, что x < z < y. Если множество A конечно, частично упорядоченное множество можно представить в виде схемы, в которой каждый элемент изображается точкой на плоскости, и если y покрывает x, то точки x и y соединяют отрезком, причем точку, соответствующую x, • • • • • • d d d d d а б Рис. располагают ниже y. Такие схемы называются диаграммами Хассе. На рис. 1.14 показаны две диаграммы Хассе. Вторая диаграмма соответствует линейно упорядоченному множеству. П р им ер. Рассмотрим частично упорядоченное множество P(A); ⊆ , где A = {1, 2, Множество P(A) содержит восемь элементов {0, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}. На рис. 1.15a изображена диаграмма Хассе, соответствующая P(A); ⊆ . 2. Пусть A = {1, 2, 3, 5, 6, 10, 15, 30}. Рассмотрим отношение частичного порядка на множестве A, задаваемое по правилу y ⇔ y делится на Диаграмма Хассе для ч.у.м. изображена на рис. б. На рис. в изображена диаграмма Хассе линейно упорядоченного множества {0, 1, 2, 3, 4, 5, 6, 7}; c обычным отношением порядка на множестве натуральных чисел, не превосходящих семи. Заметим, что диаграммы Хассе первых двух отношений совпадают. Это означает, что эти частично упорядоченные множества имеют одинаковую структуру, причем отличную от структуры третьего ч.у.м., • • • • • • • • d d d d d d d d d d d d d d d d ∅ {1} {2} {3} {1,2} {2,3} {1,3} {1,2,3} • • • • • • • • d d d d d d d d d d d d d d d d 1 2 3 5 6 10 15 30 • • • • • • • • 0 1 2 3 4 5 6 а б в Рис. 1.15 Глава 1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ хотя оно тоже содержит восемь элементов. Формально такая общность структуры определяется понятием изоморфизма. Пусть A = A; A , B = B, B — частично упорядоченные множества. Отображение f : A → B называется изоморфизмом частично упорядоченных множеств A и B, если выполняются следующие условия биекция между множествами A и B; — для любых a 1 , a 2 ∈ A, тогда и только тогда, когда f (a 1 ) B f (Если существует изоморфизм между A и B, то частично упорядоченные множества A и B называются изоморфными и этот факт обозначается через Теорема 1.7.3. Всякое частично упорядоченное множество = изоморфно некоторой системе подмножеств множества, частично упорядоченной отношением включения Задачи и упражнения. Доказать, что {∅} = ∅. 2. Доказать, что {{0, 1}, {0, 2}} = {0, 1, 2}. 3. Доказать, что (A ∪ B) = A ∩ B. 4. Построить пример множеств A и B таких, что A × B = B × A. 5. Пусть [0, 1], [0, 2] — отрезки на числовой прямой. Дать геометрическую интерпретацию множеств [0, 1] × [0, 2], [0, 1] 2 , [0, 2] 3 6. Изобразить отношения P = {(a, 1), (a, 2), (b, 2), (b, 3), (c, 1), (c, 4)} и Q = {(1, α), (2, β), (3, α)}. Найти δ Q , и P ◦ Q. 7. Для отношений P = {(x, y) ∈ R 2 |x = y 2 } и Q = {(x, y) ∈ R 2 |x · y > > найти P ◦ Q, Q ◦ P , P ◦ P и P −1 8. Пусть A и B — конечные множества мощности m и n соответственно. Найти: а) число бинарных отношений между элементами множеств A и B; б) число функций изв в) число инъекций изв г) число биекций изв. Доказать следующие эквивалентности: а) A × B ∼ B × A; б) (A × B) C ∼ A C × B C 10. Доказать, что: а) если A — конечное множество, B — подмножество множества A, томно- жество B конечно 1.8. ЗАДАЧИ И УПРАЖНЕНИЯ 33 б) если A 1 , . . . , A n — конечные множества, то множества A 1 ∪ ∪ . . . ∪ A n и . . . × A n конечны. Доказать, что если A — счетное множество, B — конечное множество, то множество A \ B счетно. Доказать, что если множества A i , i ∈ ω, счетны, то множество ∪ i∈ω A i счетно. Доказать, что если A — счетное множество, то множество ∪ n∈ω A n всех конечных последовательностей, составленных из элементов множества A, счетно. Доказать, что множество всех многочленов от одной переменной с рациональными коэффициентами счетно. Доказать, что множества точек отрезка и квадрата эквивалентны. Построить бинарное отношение: а) рефлексивное, симметричное, не транзитивное; б) не рефлексивное, антисимметричное, не транзитивное; в) рефлексивное, несимметричное, транзитивное. Пусть L — множество всех прямых на плоскости. Являются ли эквивалент- ностями следующие отношения: а) отношение параллельности двух прямых; б) отношение перпендикулярности двух прямых. Доказать, что отношение {((x 1 , y 1 ), (x 2 , y 2 )) | x 2 1 + y 2 1 = x 2 2 + y 2 2 } является отношением эквивалентности на множестве R 2 . Определить классы этой эквивалентности. Доказать, что отношение {(a, b) | (a − b) — рациональное число является отношением эквивалентности на множестве вещественных чисел. Пусть на множестве ω определено отношение , задаваемое следующим правилом делит n. Считая, что 0 делит 0, показать, что частичный порядок. Для произвольных натуральных чисел m и n найти inf{m, и sup{m, n} относительно указанного порядка. Для обычных отношений и < на множестве ω показать, что < ◦ < = <, ◦ < = < и ω 2 22. Построить пример ч.у.м. с единственным минимальным элементом, но без наименьшего. Рассмотрим на множестве отношение Парето Π: (x 1 , y 1 ) Π (x 2 , y 2 ) ⇔ и Для точек A(a 1 , a 2 ) и B(b 1 , b 2 |