Судопланов. Судоплатов С.В., Овчинникова Е.В. Дискретная математика 2016. Редакционная коллегия серии учебники нгту
 Скачать 2.01 Mb.
|
|
Ó÷åáíèêè ÍÃÒÓ Ñåðèÿ îñíîâàíà â 2001 ãîäó РЕДАКЦИОННАЯ КОЛЛЕГИЯ СЕРИИ «УЧЕБНИКИ НГТУ» д-р техн. наук, проф. (председатель) Н.В. Пустовой д-р техн. наук, проф. (зам. председателя) Г.И. Расторгуев д-р техн. наук, проф. А.А. Батаев д-р техн. наук, проф. А.Г. Вострецов д-р техн. наук, проф. В.И. Гужов д-р техн. наук, проф. В.А. Гридчин д-р техн. наук, проф. В.И. Денисов д-р физ.-мат. наук, проф. В.Г. Дубровский д-р экон. наук, проф. К.Т. Джурабаев д-р филос. наук, проф. В.И. Игнатьев д-р филос. наук, проф. В.В. Крюков д-р техн. наук, проф. В.Н. Максименко д-р физ.-мат. наук, проф. Х.М. Рахимянов д-р техн. наук, проф. Ю.Г. Соловейчик д-р техн. наук, проф. А.А. Спектор д-р экон. наук, проф. В.А. Титова д-р юр. наук, доц. В.Л. Толстых д-р техн. наук, проф. А.Г. Фишов д-р техн. наук, проф. А.Ф. Шевченко д-р техн. наук, проф. Н.И. Щуров НОВОСИБИРСК 2 0 1 6 С. В. СУДОПЛАТОВ Е. В. ОВЧИННИКОВА ДИСКРЕТНАЯ МАТЕМАТИКА 5-е издание Рекомендовано Министерством образования и науки Российской Федерации в качестве учебника для студентов высших технических учебных заведений УДК 519.1(075.8) С892 Рецензенты: д-р физ.-мат. наук, проф. Е. А. Палютин, канд. техн. наук, доц. В. М. Зыбарев Авторы книги Судоплатов Сергей Владимирович и Овчинникова Елена Викторовна награждены дипломами лауреатов премии Правительства Российской Федерации в области образования за цикл трудов «Концепция формирования логико- математического образования в высшей школе», в который вошли учебники «Дискретная математика» и «Математическая логика и теория алгоритмов» Судоплатов С. В. С892 Дискретная математика : учебник / С. В. Судоплатов, Е. В. Овчин- никова. – 5-e изд. – Новосибирск : Изд-во НГТУ, 2016. – 280 с. (Серия «Учебники НГТУ») ISBN 978-5-7782-2820-7 В книге излагаются основы теории множеств, алгебраических систем, ком- пьютерной арифметики, теории графов, комбинаторики, алгебры логики, ко- торые образуют курс дискретной математики. Для студентов технических вузов, изучающих дискретную математику. Может служить справочным пособием по дискретной математике. УДК 519.1(075.8) ISBN 978-5-7782-2820-7 © Судоплатов С. В., Овчинникова Е. В., 2002, 2005, 2010, 2012, 2016 © Новосибирский государственный технический университет, 2002, 2005, 2010, 2012, 2016 Оглавление Предисловие к пятому изданию . . . . . . . . . . . . . . . . . . . . . . . 8 Предисловие к первому изданию . . . . . . . . . . . . . . . . . . . . . . 9 Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 Глава 1. Элементы теории множеств . . . . . . . . . . . . . . . . . . . 13 § 1.1. Множества и основные операции над ними . . . . . . . . . . . 13 § 1.2. Отношения. Функции. Взаимно однозначные соответствия . . 20 § 1.3. Натуральные числа. Принцип математической индукции . . . 26 § 1.4. Мощность множества. Конечные и бесконечные множества . . 29 § 1.5. Матрица бинарного отношения. Специальные бинарные отношения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 § 1.6. Отношения эквивалентности и разбиения. Фактор-множества 38 § 1.7. Отношения порядка . . . . . . . . . . . . . . . . . . . . . . . . . 40 § 1.8. Аксиомы теории множеств . . . . . . . . . . . . . . . . . . . . . 46 Задачи и упражнения . . . . . . . . . . . . . . . . . . . . . . . . 49 Глава 2. Алгебраические системы . . . . . . . . . . . . . . . . . . . . . 54 § 2.1. Определение и примеры . . . . . . . . . . . . . . . . . . . . . . 54 § 2.2. Морфизмы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 § 2.3. Подсистемы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 § 2.4. Конгруэнции. Фактор-алгебры. Теорема о гомоморфизме . . . 62 § 2.5. Декартовы произведения алгебр. Теорема Биркгофа . . . . . . 64 § 2.6. Решетки и булевы алгебры . . . . . . . . . . . . . . . . . . . . . 66 § 2.7. Идеалы и фильтры булевой алгебры . . . . . . . . . . . . . . . 71 § 2.8. Алгебры отношений и реляционные алгебры . . . . . . . . . . 73 Задачи и упражнения . . . . . . . . . . . . . . . . . . . . . . . . 77 Глава 3. Числовые системы . . . . . . . . . . . . . . . . . . . . . . . . . 79 § 3.1. Бесконечные числовые системы . . . . . . . . . . . . . . . . . . 79 § 3.2. Системы счисления . . . . . . . . . . . . . . . . . . . . . . . . . 85 § 3.3. Компьютерная алгебра и численный анализ . . . . . . . . . . . 91 6 § 3.4. Списочное представление чисел . . . . . . . . . . . . . . . . . . 93 § 3.5. Делимость в кольце целых чисел . . . . . . . . . . . . . . . . . 96 § 3.6. Разложение целых чисел на множители . . . . . . . . . . . . . 99 § 3.7. Целые числа по модулю m . . . . . . . . . . . . . . . . . . . . . 102 § 3.8. Линейные уравнения по модулю m. Китайская теорема об остатках . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 § 3.9. Точные вычисления, использующие модулярную арифметику 109 Задачи и упражнения . . . . . . . . . . . . . . . . . . . . . . . . 116 Глава 4. Элементы теории графов . . . . . . . . . . . . . . . . . . . . . 118 § 4.1. Виды и способы задания графов . . . . . . . . . . . . . . . . . 118 § 4.2. Подграфы и части графа. Операции над графами . . . . . . . 124 § 4.3. Маршруты. Достижимость. Связность . . . . . . . . . . . . . . 129 § 4.4. Расстояния в графах . . . . . . . . . . . . . . . . . . . . . . . . 134 § 4.5. Нахождение кратчайших маршрутов . . . . . . . . . . . . . . . 136 § 4.6. Степени вершин . . . . . . . . . . . . . . . . . . . . . . . . . . . 139 § 4.7. Обходы графов . . . . . . . . . . . . . . . . . . . . . . . . . . . 140 § 4.8. Остовы графов . . . . . . . . . . . . . . . . . . . . . . . . . . . 143 § 4.9. Обходы графа по глубине и ширине. Решение задачи коммивояжера . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146 § 4.10. Упорядоченные и бинарные деревья . . . . . . . . . . . . . . . 152 § 4.11. Фундаментальные циклы . . . . . . . . . . . . . . . . . . . . . . 155 § 4.12. Разрезы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156 § 4.13. Векторные пространства, связанные с графами . . . . . . . . . 159 § 4.14. Раскраски графов . . . . . . . . . . . . . . . . . . . . . . . . . . 161 § 4.15. Планарные графы . . . . . . . . . . . . . . . . . . . . . . . . . . 163 Задачи и упражнения . . . . . . . . . . . . . . . . . . . . . . . . 165 Глава 5. Комбинаторика . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168 § 5.1. Перестановки и подстановки . . . . . . . . . . . . . . . . . . . . 168 § 5.2. Размещения и сочетания . . . . . . . . . . . . . . . . . . . . . . 171 § 5.3. Размещения и сочетания с повторением . . . . . . . . . . . . . 173 § 5.4. Разбиения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173 § 5.5. Метод включений и исключений . . . . . . . . . . . . . . . . . 175 § 5.6. Рекуррентные соотношения. Возвратные последовательности 177 Задачи и упражнения . . . . . . . . . . . . . . . . . . . . . . . . 180 7 Глава 6. Алгебра логики . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183 § 6.1. Формулы алгебры логики . . . . . . . . . . . . . . . . . . . . . 183 § 6.2. Функции алгебры логики . . . . . . . . . . . . . . . . . . . . . . 186 § 6.3. Эквивалентность формул . . . . . . . . . . . . . . . . . . . . . 189 § 6.4. Дизъюнктивные и конъюнктивные нормальные формы . . . . 191 § 6.5. Двухэлементная булева алгебра. Фактор-алгебра алгебры формул . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197 § 6.6. Минимизация булевых функций в классе ДНФ . . . . . . . . . 198 § 6.7. Карты Карно . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201 § 6.8. Принцип двойственности для булевых функций . . . . . . . . 204 § 6.9. Полные системы булевых функций . . . . . . . . . . . . . . . . 205 § 6.10. Функциональная декомпозиция . . . . . . . . . . . . . . . . . . 208 § 6.11. Логические сети . . . . . . . . . . . . . . . . . . . . . . . . . . . 215 § 6.12. Проверка теоретико-множественных соотношений с помощью алгебры логики . . . . . . . . . . . . . . . . . . . . . . . . . . . 222 § 6.13. Логические задачи . . . . . . . . . . . . . . . . . . . . . . . . . 223 Задачи и упражнения . . . . . . . . . . . . . . . . . . . . . . . . 225 Библиографический список . . . . . . . . . . . . . . . . . . . . . . . . . . 235 Приложение. Варианты типового расчета . . . . . . . . . . . . . . . . 238 Указатель терминов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265 Указатель обозначений . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 276 ПРЕДИСЛОВИЕ К ПЯТОМУ ИЗДАНИЮ В настоящем издании устранены выявленные неточности, несколько усовершенствован текст. Авторы благодарны коллегам за полезные замечания, способствовавшие улучшению содержания книги. ПРЕДИСЛОВИЕ К ПЕРВОМУ ИЗДАНИЮ Книга предназначена для студентов младших курсов технических вузов, изучающих дискретную математику, и написана на основе учебного пособия С. В. Судоплатова, Е. В. Овчинниковой “Дискретная математика” (Новосибирск : Изд-во НГТУ, 1994). Материал составлен в соответствии с рабочими программами курсов дискретной математики, читаемых в НГТУ. Для более полного понимания излагаемого в настоящем учебнике материала желательно знакомство читателя с основами линейной алгебры, например, по книгам: Ивлева А. М., Пинус А. Г., Чехонадских А. В. Основы алгебры и аналитической геометрии: Учебник. — Новосибирск : Изд-во НГТУ, 2003; Ивлева А. М., Прилуцкая П. И., Черных И. Д. Линейная алгебра. Анали- тическая геометрия: Учеб. пособие. — Новосибирск : Изд-во НГТУ, 2000. Учебник включает шесть разделов: основы теории множеств, алгебраи- ческие системы, числовые системы, теория графов, комбинаторика, алгебра логики. Взаимосвязь разделов приведена на следующей схеме: 1 - 2 - 4 HH HH H j 6 ? ¡ ¡ µ 5 ¢ ¢ ¢ ¢¸ 3 Для углубленного изучения материала в конце книги приводится список литературы. Для удобства поиска используемых терминов дан указатель терминов, а также указатель обозначений. Кроме того, в качестве прило- жения приведен типовой расчет по дискретной математике для самостоя- 10 ПРЕДИСЛОВИЕ тельного выполнения студентами семестрового задания на основе матери- ала, излагаемого в книге. Перед решением задач типового расчета полез- но прорешать задачи и упражнения, помещенные в конце соответствующих разделов. Рассматриваемые в учебнике понятия и утверждения, как правило, ил- люстрируются примерами и пояснениями. Отмечаются прикладные аспекты изучаемого материала. Знак ¤, используемый в тексте, означает конец рассуждения или его отсутствие. Знак читается “положим по определению”, “обозначим” или “имеет вид”, знак ⇔ — “тогда и только тогда”, знак ⇒ — “если ..., то ...”, знак ∀ — “для любого”, знак ∃ — “существует”. Создание книги стало возможным с появлением в Новосибирском госу- дарственном техническом университете кафедры алгебры и математической логики, основанной профессором А. Г. Пинусом в 1992 г. На разных эта- пах подготовки настоящей книги авторы получали от него большую помощь и поддержку. Много полезных предложений и замечаний сделал доцент ка- федры вычислительной техники НГТУ В. М. Зыбарев. Этим коллегам ав- торы выражают свою искреннюю благодарность. Авторы благодарны И. Д. Черных, который взял на себя труд по де- тальному прочтению рукописи, устранению неточностей и компьютерному набору учебника. ВВЕДЕНИЕ Дискретная (или прерывная) математика представляет собой область математики, в которой изучаются свойства структур конечного характе- ра, а также бесконечных структур, предполагающих скачкообразность про- исходящих в них процессов или отделимость составляющих их элементов. В отличие от дискретной математики классическая математика занимается преимущественно изучением свойств структур непрерывного характера. Деление математики на классическую и дискретную достаточно условно, поскольку, с одной стороны, происходит взаимопроникновение возникающих идей и методов, а с другой — средства дискретной математики используются для изучения непрерывных моделей и наоборот. Бурное развитие дискретной математики обусловлено прогрессом ком- пьютерной техники, необходимостью создания средств обработки и передачи информации, а также представления различных моделей на компьютерах, являющихся по своей природе конечными структурами. Укажем основные цели, преследуемые в учебнике при рассмотрении ос- новных разделов дискретной математики. В первой главе рассматривается понятие множества, вводятся операции над множествами и перечисляются основные свойства этих операций. Опре- деляется понятие отношения на множестве, указываются свойства отноше- ний, различные виды отношений. Дается аксиоматика теории множеств, поз- воляющая, с одной стороны, избегать появления известных парадоксов, а с другой — получать содержательные результаты, покрывающие практи- ческие потребности. Во второй главе приводится центральное понятие курса — понятие алгеб- раической системы, а также различных видов алгебраических систем, связей между алгебраическими системами, основные операции над ними. 12 ВВЕДЕНИЕ Третья глава посвящена различным возможностям представления чисел и работы с числовыми системами, включая компьютерную арифметику. Даются способы точного вычисления арифметических выражений в рамках конечных систем, преимущества и недостатки компьютерных вычислений. В четвертой главе излагаются основы теории графов. Приводятся основ- ные виды и способы задания графов, операции над графами, их числовые характеристики, алгоритмы, используемые для решения практических за- дач, связанных с графами. В пятой главе рассматриваются основные комбинаторные конфигурации и формулы. Шестая глава посвящена изучению алгебры логики. Здесь приводятся по- нятия формулы и функции алгебры логики, алгоритмы минимизации функ- ций алгебры логики, критерий полноты системы булевых функций, прило- жения алгебры логики. Глава 1 ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ § 1.1. Множества и основные операции над ними Понятия множества и элемента множества относятся к понятиям, не опре- делимым явно, таким, как, например, точка и прямая. Это связано с тем, что некоторые понятия в математике должны быть исходными, служить теми “кирпичиками”, из которых складывается общая теория. Мы опреде- ляем только, как соотносятся эти исходные понятия, не говоря о природе рассматриваемых объектов. Под множеством M понимается совокупность некоторых объектов, называемых элементами множества M. Тот факт, что x является элемен- том множества M, будем обозначать через x ∈ M (читается “x принадле- жит M”), а если x не является элементом множества M, то будем писать x / ∈ M (читается “x не принадлежит M”). Заметим, что элементы множества сами могут являться множествами. Например, множество групп студентов состоит из элементов (групп), кото- рые, в свою очередь, состоят из студентов. Множество можно задать перечислением принадлежащих ему элемен- тов или указанием свойств, которым элементы множества должны удовле- творять. Если x 1 , x 2 , . . . , x n — все элементы множества M, то будем писать M = {x 1 , x 2 , . . ., x n }. Пусть имеется свойство P , которым могут обладать или не обладать элементы некоторого множества A. Тогда множество M, состоящее из всех элементов множества A, обладающих свойством P , будет обозначаться через {x ∈ A | x обладает свойством P }, а также {x | x обладает свойством P }, {x | P (x)} или {x} P (x) , когда из контекста ясно, о каком множестве A идет речь. 14 Глава 1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ Мы будем использовать следующие обозначения для числовых множеств: N или ω — множество натуральных чисел, Z — множество целых чисел, Q — множество рациональных чисел, R — множество вещественных чисел, C — множество комплексных чисел. Пример 1.1.1. Множество M арабских цифр можно задать двояко: пе- речислением — M = {0, 1, 2, . . . , 9} или посредством свойства — M = {x | x — арабская цифра}. ¤ Пример 1.1.2. Множество нечетных чисел {±1, ±3, ±5, . . .} можно определить как {x | x = 2k + 1 для некоторого k ∈ Z}. ¤ Способ задания множества с помощью свойств таит некоторые опасно- сти, поскольку “неправильно” заданные свойства могут привести к проти- воречию. Приведем один из наиболее типичных теоретико-множественных парадоксов — парадокс Рассела. Рассмотрим множество всех множеств, ко- торые не являются своими собственными элементами: K {M | M / ∈ M}. Спросим теперь, является ли множество K своим элементом? Если K ∈ K, то должно выполняться свойство, задающее множество K, т. е. K / ∈ K, что приводит к противоречию. Если же K / ∈ K, то, поскольку выполняется свойство, задающее K, приходим к тому, что K ∈ K, а это противоречит предположению. Таким образом, не всякое свойство приводит к осмыслен- ному заданию множества. В конце настоящей главы мы рассмотрим систему аксиом теории множеств, исключающую подобные парадоксы. Множество |