Дискретка. Учебник издание шестое Рекомендовано Министерством образования и науки Российской Федерации в качестве учебника для студентов высших технических учебных заведений
 Скачать 1.99 Mb.
|
|
С. В. СУДОПЛАТОВ, Е. В. ОВЧИННИКОВА ДИСКРЕТНАЯ МАТЕМАТИКА УЧЕБНИК Издание шестое Рекомендовано Министерством образования и науки Российской Федерации в качестве учебника для студентов высших технических учебных заведений МОСКВА 2016 УДК 519.1(075.8) С892 Р е ц е н з е н т ы: Е. А. Палютин — д-р физ.-мат. наук, проф., А. Г. Пинус — д-р физ.-мат. наук, проф. Учебник подготовлен на кафедре алгебры и математической логики Новосибирского государственного технического университета С892 Судоплатов С.В., Овчинникова Е.В. Дискретная математика: Учебник. — 6-е изд. — М. : Юрайт, 2016. — 280 с. ISBN В книге излагаются основы теории множеств, алгебраических систем, компью- терной арифметики, теории графов, комбинаторики, алгебры логики, которые об- разуют курс дискретной математики. Для студентов технических вузов, изучающих дискретную математику. Может служить справочным пособием по дискретной математике. УДК 519.1(075.8) c ° Судоплатов С.В., Овчинникова Е.В., 2016 Оглавление Предисловие . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 Глава 1. Элементы теории множеств . . . . . . . . . . . . . . . . . . . 10 § 1.1. Множества и основные операции над ними . . . . . . . . . . . 10 § 1.2. Отношения. Функции. Взаимно однозначные соответствия . . 17 § 1.3. Натуральные числа. Принцип математической индукции . . . 23 § 1.4. Мощность множества. Конечные и бесконечные множества . . 26 § 1.5. Матрица бинарного отношения. Специальные бинарные отношения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 § 1.6. Отношения эквивалентности и разбиения. Фактор-множества 35 § 1.7. Отношения порядка . . . . . . . . . . . . . . . . . . . . . . . . . 37 § 1.8. Аксиомы теории множеств . . . . . . . . . . . . . . . . . . . . . 44 Задачи и упражнения . . . . . . . . . . . . . . . . . . . . . . . . 46 Глава 2. Алгебраические системы . . . . . . . . . . . . . . . . . . . . . 51 § 2.1. Определение и примеры . . . . . . . . . . . . . . . . . . . . . . 51 § 2.2. Морфизмы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 § 2.3. Подсистемы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 § 2.4. Конгруэнции. Фактор-алгебры. Теорема о гомоморфизме . . . 59 § 2.5. Декартовы произведения алгебр. Теорема Биркгофа . . . . . . 61 § 2.6. Решетки и булевы алгебры . . . . . . . . . . . . . . . . . . . . . 63 § 2.7. Идеалы и фильтры булевой алгебры . . . . . . . . . . . . . . . 68 § 2.8. Алгебры отношений и реляционные алгебры . . . . . . . . . . 70 Задачи и упражнения . . . . . . . . . . . . . . . . . . . . . . . . 74 Глава 3. Числовые системы . . . . . . . . . . . . . . . . . . . . . . . . . 76 § 3.1. Бесконечные числовые системы . . . . . . . . . . . . . . . . . . 76 § 3.2. Системы счисления . . . . . . . . . . . . . . . . . . . . . . . . . 82 § 3.3. Компьютерная алгебра и численный анализ . . . . . . . . . . . 88 § 3.4. Списочное представление чисел . . . . . . . . . . . . . . . . . . 90 § 3.5. Делимость в кольце целых чисел . . . . . . . . . . . . . . . . . 93 4 § 3.6. Разложение целых чисел на множители . . . . . . . . . . . . . 96 § 3.7. Целые числа по модулю m . . . . . . . . . . . . . . . . . . . . . 99 § 3.8. Линейные уравнения по модулю m. Китайская теорема об остатках . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 § 3.9. Точные вычисления, использующие модулярную арифметику 106 Задачи и упражнения . . . . . . . . . . . . . . . . . . . . . . . . 113 Глава 4. Элементы теории графов . . . . . . . . . . . . . . . . . . . . . 115 § 4.1. Виды и способы задания графов . . . . . . . . . . . . . . . . . 115 § 4.2. Подграфы и части графа. Операции над графами . . . . . . . 121 § 4.3. Маршруты. Достижимость. Связность . . . . . . . . . . . . . . 126 § 4.4. Расстояния в графах . . . . . . . . . . . . . . . . . . . . . . . . 131 § 4.5. Нахождение кратчайших маршрутов . . . . . . . . . . . . . . . 133 § 4.6. Степени вершин . . . . . . . . . . . . . . . . . . . . . . . . . . . 136 § 4.7. Обходы графов . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 § 4.8. Остовы графов . . . . . . . . . . . . . . . . . . . . . . . . . . . 140 § 4.9. Обходы графа по глубине и ширине. Решение задачи коммивояжера . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143 § 4.10. Упорядоченные и бинарные деревья . . . . . . . . . . . . . . . 149 § 4.11. Фундаментальные циклы . . . . . . . . . . . . . . . . . . . . . . 152 § 4.12. Разрезы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153 § 4.13. Векторные пространства, связанные с графами . . . . . . . . . 156 § 4.14. Раскраски графов . . . . . . . . . . . . . . . . . . . . . . . . . . 158 § 4.15. Планарные графы . . . . . . . . . . . . . . . . . . . . . . . . . . 160 Задачи и упражнения . . . . . . . . . . . . . . . . . . . . . . . . 162 Глава 5. Комбинаторика . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165 § 5.1. Перестановки и подстановки . . . . . . . . . . . . . . . . . . . . 165 § 5.2. Размещения и сочетания . . . . . . . . . . . . . . . . . . . . . . 168 § 5.3. Размещения и сочетания с повторением . . . . . . . . . . . . . 170 § 5.4. Разбиения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170 § 5.5. Метод включений и исключений . . . . . . . . . . . . . . . . . 172 § 5.6. Рекуррентные соотношения. Возвратные последовательности 174 Задачи и упражнения . . . . . . . . . . . . . . . . . . . . . . . . 177 5 Глава 6. Алгебра логики . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180 § 6.1. Формулы алгебры логики . . . . . . . . . . . . . . . . . . . . . 180 § 6.2. Функции алгебры логики . . . . . . . . . . . . . . . . . . . . . . 183 § 6.3. Эквивалентность формул . . . . . . . . . . . . . . . . . . . . . 186 § 6.4. Дизъюнктивные и конъюнктивные нормальные формы . . . . 188 § 6.5. Двухэлементная булева алгебра. Фактор-алгебра алгебры формул . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194 § 6.6. Минимизация булевых функций в классе ДНФ . . . . . . . . . 195 § 6.7. Карты Карно . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198 § 6.8. Принцип двойственности для булевых функций . . . . . . . . 201 § 6.9. Полные системы булевых функций . . . . . . . . . . . . . . . . 202 § 6.10. Функциональная декомпозиция . . . . . . . . . . . . . . . . . . 205 § 6.11. Логические сети . . . . . . . . . . . . . . . . . . . . . . . . . . . 212 § 6.12. Проверка теоретико-множественных соотношений с помощью алгебры логики . . . . . . . . . . . . . . . . . . . . . . . . . . . 219 § 6.13. Логические задачи . . . . . . . . . . . . . . . . . . . . . . . . . 220 Задачи и упражнения . . . . . . . . . . . . . . . . . . . . . . . . 222 Библиографический список . . . . . . . . . . . . . . . . . . . . . . . . . . 232 Приложение. Варианты типового расчета . . . . . . . . . . . . . . . . 235 Указатель терминов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262 Указатель обозначений . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 275 ПРЕДИСЛОВИЕ Дискретная (или прерывная) математика представляет собой область математики, в которой изучаются свойства структур конечного характе- ра, а также бесконечных структур, предполагающих скачкообразность про- исходящих в них процессов или отделимость составляющих их элементов. В отличие от дискретной математики классическая математика занимается преимущественно изучением свойств структур непрерывного характера. Деление математики на классическую и дискретную достаточно условно, поскольку, с одной стороны, происходит взаимопроникновение возникающих идей и методов, а с другой — средства дискретной математики используются для изучения непрерывных моделей и наоборот. Бурное развитие дискретной математики обусловлено прогрессом ком- пьютерной техники, необходимостью создания средств обработки и передачи информации, а также представления различных моделей на компьютерах, являющихся по своей природе конечными структурами. Книга предназначена для студентов бакалавриата всех направлений обучения в технических вузах, изучающих дискретную математику, и на- писана на основе учебного пособия С. В. Судоплатова, Е. В. Овчинниковой “Дискретная математика” (Новосибирск : Изд-во НГТУ, 1994). Материал составлен в соответствии с рабочими программами курсов дискретной ма- тематики, читаемых в НГТУ. Для более полного понимания излагаемого в настоящем учебнике материала желательно знакомство читателя с основами линейной алгебры, например, по книгам: Ивлева А. М., Пинус А. Г., Че- хонадских А. В. Основы алгебры и аналитической геометрии: Учебник. — Новосибирск : Изд-во НГТУ, 2006; Ивлева А. М., Прилуцкая П. И., Чер- ных И. Д. Линейная алгебра. Аналитическая геометрия: Учеб. пособие. — Новосибирск : Изд-во НГТУ, 2015. ПРЕДИСЛОВИЕ 7 Учебник включает шесть разделов: основы теории множеств, алгебраи- ческие системы, числовые системы, теория графов, комбинаторика, алгебра логики. Взаимосвязь разделов приведена на следующей схеме: 1 - 2 - 4 HH HH H j 6 ? ¡ ¡ µ 5 ¢ ¢ ¢ ¢¸ 3 Укажем основные цели, преследуемые в учебнике при рассмотрении ос- новных разделов дискретной математики. В первой главе рассматривается понятие множества, вводятся операции над множествами и перечисляются основные свойства этих операций. Опре- деляется понятие отношения на множестве, указываются свойства отноше- ний, различные виды отношений. Дается аксиоматика теории множеств, поз- воляющая, с одной стороны, избегать появления известных парадоксов, а с другой — получать содержательные результаты, покрывающие практи- ческие потребности. Во второй главе приводится центральное понятие курса — понятие алгеб- раической системы, а также различных видов алгебраических систем, связей между алгебраическими системами, основные операции над ними. Третья глава посвящена различным возможностям представления чисел и работы с числовыми системами, включая компьютерную арифметику. Даются способы точного вычисления арифметических выражений в рамках конечных систем, преимущества и недостатки компьютерных вычислений. В четвертой главе излагаются основы теории графов. Приводятся основ- ные виды и способы задания графов, операции над графами, их числовые характеристики, алгоритмы, используемые для решения практических за- дач, связанных с графами. В пятой главе рассматриваются основные комбинаторные конфигурации и формулы. Шестая глава посвящена изучению алгебры логики. Здесь приводятся по- нятия формулы и функции алгебры логики, алгоритмы минимизации функ- ций алгебры логики, критерий полноты системы булевых функций, прило- жения алгебры логики. 8 ПРЕДИСЛОВИЕ Для углубленного изучения материала в конце книги приводится список литературы. Для удобства поиска используемых терминов дан указатель терминов, а также указатель обозначений. Кроме того, в качестве прило- жения приведен типовой расчет по дискретной математике для самостоя- тельного выполнения студентами семестрового задания на основе матери- ала, излагаемого в книге. Перед решением задач типового расчета полез- но прорешать задачи и упражнения, помещенные в конце соответствующих разделов. Рассматриваемые в учебнике понятия и утверждения, как правило, ил- люстрируются примерами и пояснениями. Отмечаются прикладные аспекты изучаемого материала. В результате изучения материала студент будет владеть информацией о математике как особом способе познания мира, общности ее понятий и представлений, а также о дискретной математике как важнейшем разделе математики, используемом в современном математическом моделировании. Студент будет знать: основные понятия курса дискретной математики: мно- жества, отношения, функции и операции над ними; алгебраические системы и операции над ними; системы компьютерной арифметики; графы, деревья и операции над ними, их числовые характеристики, алгоритмы на графах; формулы и функции алгебры логики, алгоритмы нормализации и миними- зации нормальных форм, полные системы булевых; постановку и методы решения основных задач, связанных с перечисленными выше понятиями. Студент будет уметь: доказывать теоретико-множественные соотношения, алгебраические соотношения методом математической индукции кодировать бинарные отношения матрицами и проверять с помощью матриц и непосред- ственно основные свойства бинарных отношений; производить операции над алгебраическими системами, находить алгебры, порожденные данным мно- жеством; использовать компьютерную арифметику для точных вычислений арифметических выражений; производить основные операции с графами, находить основные числовые характеристики графов; работать с алгорит- мами на графах; составлять таблицы истинности формул алгебры логики, проверять эквивалентность формул; строить нормальные формы и решать по ним задачу минимизации булевых функций; строить полиномы Жегал- кина, проверять полноту систем булевых функций; переводить информацию с языка конкретной задачи на язык дискретной математики и строить ма- тематические модели простейших систем и процессов в естествознании и технике; выбирать методы решения задач на основе анализа построенной математической модели. ПРЕДИСЛОВИЕ 9 Знак ¤, используемый в тексте, означает конец рассуждения или его отсутствие. Знак читается “положим по определению”, “обозначим” или “имеет вид”, знак ⇔ — “тогда и только тогда”, знак ⇒ — “если ..., то ...”, знак ∀ — “для любого”, знак ∃ — “существует”. Создание книги стало возможным с появлением в Новосибирском госу- дарственном техническом университете кафедры алгебры и математической логики, основанной профессором А. Г. Пинусом в 1992 г. На разных эта- пах подготовки настоящей книги авторы получали от него большую помощь и поддержку. Много полезных предложений и замечаний сделал доцент ка- федры вычислительной техники НГТУ В. М. Зыбарев. Этим коллегам ав- торы выражают свою искреннюю благодарность. Авторы благодарны И. Д. Черных, который взял на себя труд по де- тальному прочтению рукописи, устранению неточностей и компьютерному набору учебника. В настоящем, шестом издании устранены выявленные неточности, несколько усовершенствован текст. Авторы благодарны коллегам за полезные замечания, способствовавшие улучшению содержания книги. Глава 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 идет речь. 1.1. МНОЖЕСТВА И ОСНОВНЫЕ ОПЕРАЦИИ НАД НИМИ 11 Мы будем использовать следующие обозначения для числовых множеств: 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, а это противоречит предположению. Таким образом, не всякое свойство приводит к осмыслен- ному заданию множества. В конце настоящей главы мы рассмотрим систему аксиом теории множеств, исключающую подобные парадоксы. Множество |