Универсальное множество и пустое множество 9 Здесь М является множеством, состоящим из положительных целых чисел, которые больше 1 и нечетные. (в) А = {x: x — гласная буква английского алфавита}. <...> Универсальное множество и пустое множество При задании множества в любом приложении теории множеств обычно приходится сталкиваться с вопросом, к какому основному или универсальному множеству принадлежит рассматриваемое множество. <...> Фундаментальное произведение множеств Операции над множествами позволяют образовывать из исходных множеств новые множества. <...> Этот класс называют степенным множеством S и обозначают 2S число элементов степенного множества n(2S бой степень 2 и равно n(2S) = 2 n(S) то степенное множество 2S . <...> Теория множеств Фундаментальные произведения также представляют собой разбиение универсального множества. <...> Алгебра множеств и двойственность Абстрактная алгебра занимается изучением операций, производимых над некоторыми элементами. <...> 3 A ∩ A = A A ∪ A = A Идемпотентность — формулы алгебры множеств не имеют ни степеней, ни коэффициентов 4 A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) 5 A ∩ (A ∪ B) = A A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) A ∪ (A ∩ B) = A Дистрибутивность — раскрытие скобок и вынесение общего элемента Законы поглощения — большее по числу переменных пересечение (или объединение) поглощается меньшим 6 (A ∩ B)С = AC ∪ BC (A ∪ B)C ∩ ВC = АC Законы де Моргана — дополнение пересечения (объединения) нескольких множеств заменяется на объединение (пересечение) дополнений каждого из этих множеств 7 (AC )C = A Инволюция — дополнение дополнения множества дает исходное множество 8 9 A ∩ AC ШC = Ш = U A ∩ U = A A ∩ Ш = Ш A ∪ AC UC = U = Ш A ∪ Ш = A A ∪ U = U Законы тождества Принцип двойственности алгебры множеств Нетрудно заметить, что тождества в таблице располагаются парами, например первое тождество A ∩ B = B ∩ A имеет парное Законы дополнения 24 Глава 1. <...> Определение Любое множество или совокупность множеств разбиения <...>
Дискретная_математика._Краткий_курс._Учебное_пособие.pdf
УДК 512.563.3 (075)
ББК 22.1я73
К14
Электронные версии книг
на сайте www.prospekt.org
К14
Казанский А. А.
Дискретная математика. Краткий курс : учебное пособие. —
Москва : Проспект, 2016. — 320 с.
ISBN 978-5-392-19545-9
В пособии изложены основные разделы современной дискретной
математики. Рассматриваются вопросы, связанные с теорией
множеств, теорией отношений, теорией графов и логикой. Материал
построен на основе курса лекций, читаемого автором в технических
вузах.В каждой главе рассмотрено большое число задач с подробными
решениями и примерами, что позволяет эффективно и быстро осваивать
изучаемую тему.
Для студентов, обучающихся по специальности «Прикладная
математика», а также для студентов технических и экономических
факультетов, изучающих курс «Дискретная математика» и компьютерные
технологии. Представляет интерес для тех, кто связан с использованием
методов дискретной математики.
Учебное издание
УДК 512.563.3 (075)
ББК 22.1я73
Казанский Александр Анатольевич
ДИСКРЕТНАЯ МАТЕМАТИКА.
КРАТКИЙ КУРС
Учебное пособие
Печать офсетная. Печ. л. 10,0. Тираж 1000 (1-й завод 100) экз. Заказ №.
ООО «Проспект»
Оригинал-макет подготовлен компанией ООО «Оригинал-макет»
www.o-maket.ru; тел.: (495) 726-18-84
Санитарно-эпидемиологическое заключение
№ 77.99.60.953.Д.004173.04.09 от 25.04.2009 г.
Подписано в печать 31.08.2015. Формат 70Х
100 1/32
111020, г. Москва, ул. Боровая, д. 7, стр. 4.
ISBN 978-5-392-19545-9
©© Казанский А. А., 2015
Колотилова Е. А., дизайн обложки, 2014
© ООО «Проспект», 2015
Стр.2
ОГЛАВЛЕНИЕ
Глава 1. Теория множеств .........................................................6
Введение ....................................................................................... 6
1.1. Множество и его элементы ................................................7
1.2. Универсальное множество и пустое множество ................9
1.3. Подмножества ................................................................... 10
1.4. Диаграммы Венна ............................................................. 11
1.5. Операции над множествами ............................................. 14
1.6. Фундаментальное произведение множеств ..................... 18
1.7. Классы множеств, степенные множества и разбиения ... 20
1.8. Алгебра множеств и двойственность ............................... 22
1.9. Доказательство тождеств с множествами ........................ 24
1.10. Математическая индукция ............................................. 32
1.11. Представление множеств формулами ............................ 33
1.12. Многочлены алгебры множеств ..................................... 38
1.13. Полные нормальные формы .......................................... 41
1.14. Определение минимальных форм .................................. 45
1.15. Представление формул алгебры множеств графами ..... 49
1.16. Минимизация формул алгебры множеств на графе ...... 52
1.17. Решенные задачи ............................................................ 58
Глава 2. Отношения ................................................................. 90
2.1. Введение ............................................................................ 90
2.2. Декартово произведение множеств ................................. 91
2.3. Отношения ........................................................................ 92
2.4. Представление отношений .............................................. 94
2.5. Композиция отношений .................................................. 96
2.6. Свойства отношений ........................................................ 99
2.7. Замыкание свойств ......................................................... 104
2.8. Отношение эквивалентности ......................................... 105
Стр.3
4
Оглавление
2.9. Отношение частичного порядка .................................... 107
2.10. Решенные задачи .......................................................... 108
Глава 3. Теория графов .......................................................... 124
3.1. Введение .......................................................................... 124
3.2. Определения ................................................................... 125
3.3. Подграфы. Изоморфизм и гомеоморфизм графов........ 129
3.4. Дополнение графа .......................................................... 132
3.5. Маршруты, цепи, циклы ................................................ 135
3.6. Расстояние в графе ......................................................... 137
3.7. Двудольные и k-дольные графы ..................................... 140
3.8. Операции над графами ................................................... 143
3.9. Многомерный куб как произведение графа K2
.............. 145
3.10. Связность графов .......................................................... 150
3.11. Деревья .......................................................................... 157
3.12. Векторные пространства циклов и разрезов графа ..... 161
3.13. Сети ............................................................................... 173
3.14. Представления графов. Матрицы и списки
смежности графов ................................................................. 183
3.15. Покрытия, независимость и паросочетания ............... 194
3.16. Раскрашивание графов ................................................. 201
3.17. Эйлеровы и гамильтоновы графы ................................ 205
3.18. Планарность .................................................................. 209
3.19. Ориентированные графы .............................................. 213
3.20. Решенные задачи .......................................................... 222
Глава 4. Логика и исчисление высказываний ....................... 273
4.1. Введение .......................................................................... 273
4.2. Высказывания и составные высказывания ................... 276
4.3. Логические операции ..................................................... 278
4.4. Таблицы истинности для высказываний ....................... 280
4.5. Тавтологии и контрадикции .......................................... 283
4.6. Логическая тождественность ......................................... 284
4.7. Условные высказывания ................................................ 285
4.8. Алгебра высказываний ................................................... 289
4.9. Построение выводов в исчислении высказываний ....... 291
Стр.4
Оглавление
5
4.10. Исчисление предикатов ................................................ 293
4.11. Решенные задачи .......................................................... 296
Предметный указатель ............................................................ 313
Литература ............................................................................. 317
Стр.5
Глава 1
ТЕОРИЯ МНОЖЕСТВ
Введение
Понятие множества используется во всех математических
дисциплинах. Сама идея о существовании соотношения между
величинами различной природы возникла, по-видимому, во
времена античности, однако потребовалось много столетий,
чтобы это первоначальное представление привело к современному
теоретико-множественному понятию отображения,
которое каждому элементу одного множества ставит в соответствие
элемент другого множества. Античные математики
использовали различные таблицы, например астрономические
таблицы Птолемея, но эти таблицы понимались как соотношения
между конечными дискретными множествами постоянных
величин и предназначались только для вычисления числовых
значений. В многочисленных трудах греческих математиков,
включая и Архимеда, не используется идея функциональной
зависимости. Эта идея сформировалась лишь в начале XVII в.,
когда научились представлять функциональные зависимости
с помощью формул. В работах Декарта, Ньютона, Лейбница,
н Эйлера для записи различных зависимостей стали использовать
е громоздкие таблицы, а компактные алгебраические вырамжения.
Эти работы привели к значительным успехам в матене
число, а функция.атике и благодаря им в XVIII в. главным объектом становится
Понятия, связанные с множествами, введены немецким
математиком Дедекиндом в 1871 г. в работе по теории алгебраических
чисел и теории полей. Общие принципы множеств, или
совокупностей, сформулированы Георгом Кантором в эти же
годы, однако его основные работы посвящены свойствам бес
Стр.6