Дискретная математика. Вып. 19


Комплекс учебников удостоен
Премии Правительства Российской Федерации в области науки и техники за 2003 год




МАТЕМАТИКА В ТЕХНИЧЕСКОМ УНИВЕРСИТЕТЕ



Выпуск 19

Комплекс учебников
«Математика в техническом университете» из 21 выпуска




1. Введение в анализ
2. Дифференциальное исчисление функций одного переменного
3. Аналитическая геометрия
4. Линейная алгебра
5. Дифференциальное исчисление функций многих переменных
6. Интегральное исчисление функций одного переменного
7. Кратные и криволинейные интегралы. Элементы теории поля
8. Дифференциальные уравнения
9. Ряды
10. Теория функций комплексного переменного
11. Интегральные преобразования и операционное исчисление
12. Дифференциальные уравнения математической физики
13. Приближенные методы математической физики
14. Методы оптимизации
15. Вариационное исчисление и оптимальное управление
16. Теория вероятностей
17. Математическая статистика
18. Случайные процессы
19. Дискретная математика
20. Исследование операций
21. Математическое моделирование в технике

А.И. БЕЛОУСОВ, С.Б. ТКАЧЕВ





ДИСКРЕТНАЯ
МАТЕМАТИКА




Под редакцией
д-ра техн. наук, профессора B.C. Зарубина и д-ра физ.-мат. наук, профессора А.П. Крищенко

Рекомендовано Министерством образования Российской Федерации в качестве учебника для студентов высших технических учебных заведений



6-е издание







Москва ИЗДАТЕЛЬСТВО МГТУ им. Н.Э. Баумана 2020

УДК 512.5+519.1(075.8)
ББК 22.174
      Б43







Рецензенты: член-корреспондент РАН Ю.Н. Павловский, профессор А.К. Платонов


      Белоусов, А. И.
Б43 Дискретная математика : учебник для вузов / А. И. Белоусов, С. Б. Ткачев ; под ред. B. C. Зарубина, А. П. Крищен-ко. — 6-е изд. — Москва : Издательство МГТУ им. Н. Э. Баумана, 2020. — 703, [1] с. : ил. — (Математика в техническом университете ; вып. 19).
         ISBN 978-5-7038-3845-7
         ISBN 978-5-7038-4905-7 (вып. 19)
         В девятнадцатом выпуске серии «Математика в техническом университете» изложены теория множеств и отношений, элементы современной абстрактной алгебры, теория графов, классические понятия теории булевых функций, а также основы теории формальных языков, куда включены теории конечных автоматов, регулярных языков, контекстно-свободных языков и магазинных автоматов. В анализе графов и автоматов особое внимание уделено алгебраическим методам.
         Содержание учебника соответствует курсу лекций, который авторы читают в МГТУ им. Н.Э. Баумана.
         Для студентов технических университетов. Может быть полезен преподавателям, аспирантам и инженерам.

УДК 512.5+519.1(075.8)
                                         ББК 22.174


ISBN 978-5-7038-4905-7 (вып. 19)
ISBN 978-5-7038-3845-7

© Белоусов А.И., Ткачев С.Б., 2001
© Белоусов А.И., Ткачев С.Б., 2006, с изменениями
© Оформление. Издательство МГТУ им. Н. Э. Баумана, 2020

                ПРЕДИСЛОВИЕ





Предлагаемая читателю книга является девятнадцатым выпуском комплекса учебников «Математика в техническом университете». Она содержит систематическое изложение курса дискретной математики.
   Развитие классической («непрерывной») математики было обусловлено прежде всего решением задач естествознания, главным образом физики. «Дискретная» же математика развивалась в связи с изучением законов и правил человеческого мышления, что и обусловило ее применение в тех областях техники, которые так или иначе связаны с моделированием мышления, и в первую очередь в вычислительной технике и программировании.
   Мышление реализует себя прежде всего в языке. Поэтому разумно считать, что ядро дискретной математики образует именно математическая теория языков, точнее, область этой теории, называемая теорией формальных языков. Слово «формальный» подчеркивает, что в этой теории изучаются в основном искусственные языки, специально созданные для каких-то целей: языки программирования, языки математики и т. п. Теория формальных языков является базой теории кодирования, «криптологии», изучающей методы защиты информации, теории алгоритмов и в определенном смысле математической логики. В прикладном аспекте эта теория служит основой разработки математического обеспечения вычислительных машин.
   Доминирующим в современной теории формальных языков является алгебраический подход, в котором существенно используется аппарат, базирующийся на понятии алгебраиче

Предисловие

ской структуры полукольца. Этот аппарат во многом похож на аппарат линейной алгебры. Систематическое изложение теории формальных языков на базе теории полуколец и является одной из основных задач этой книги. Отметим, что в отечественной учебной литературе такой подход почти не получил отражения.
   Теория формальных языков существенно опирается и на теорию графов. Многие задачи теории языков (например, задача определения языка конечного или магазинного автомата) сводится к задаче о путях во взвешенных (размеченных) ориентированных графах, где множество меток имеет алгебраическую структуру полукольца.
   Изложение материала построено следующим образом. Глава 1 посвящена множествам и отношениям. Здесь напоминаются основы теории множеств, изложенные в первом выпуске комплекта учебников, причем некоторые вопросы излагаются более детально. Основное содержание главы составляет теория отношений. Центральным результатом является теорема о неподвижной точке для индуктивных упорядоченных множеств, на базе которой строятся методы решения задач о путях в графах и алгебраические методы в теории формальных языков.
   Ввиду важности алгебраических методов в дискретной математике большое внимание уделяется алгебраической теории: ей посвящены три главы. В главе 2 излагаются элементы классической общей алгебры и рассматриваются группы, кольца и поля. Глава 3 посвящена полукольцам и булевым алгебрам. Приведенный здесь материал имеет важное значение с точки зрения приложения алгебраических методов как в теории формальных языков, так и в теории булевых функций. Особенностью изложения является определение булевой алгебры как частного случая полукольца. В главе 4 приведены некоторые результаты общей теории алгебраических систем.
   Глава 5 посвящена теории графов. Центральное место в главе занимает изложение алгебраического метода решения задач о путях в ориентированных графах, размеченных над

Предисловие

7

полукольцами. Этот материал служит, с одной стороны, иллюстрацией применения алгебраической техники в решении графовых задач, а с другой — основой решения задач в теории формальных языков. Глава содержит также описание некоторых алгоритмов на графах: алгоритма «поиска в глубину» и «поиска в ширину», алгоритма Краскала для отыскания остовного дерева наименьшего веса, алгоритма топологической сортировки. Коротко рассматриваются изоморфизм графов, группы автоморфизмов графов и элементы цикломатики (анализа структуры циклов неориентированного графа).
   Глава 6 посвящена классическому разделу дискретной математики — булевым функциям — и включает вопросы минимизации булевых функций и теорему Поста о функциональной полноте.
   В главах 7 и 8 изложена теория формальных языков. Глава 7 содержит «линейную часть» этой теории — теорию конечных автоматов и регулярных языков, а глава 8 — теорию контекстно-свободных языков. Это важнейший класс языков, его теоретический анализ является основой многих информационных технологий, таких, в частности, как проектирование компиляторов или разработка лингвистического обеспечения баз данных. Фундаментальным является понятие магазинного автомата — распознавателя в классе контекстно-свободных языков. Именно эта модель языка служит математической основой конкретных технологий разработки синтаксических анализаторов для языков программирования.
   В дополнениях к главе 8 приведены элементарные сведения о синтаксическом анализе контекстно-свободных языков и введение в математическую теорию семантики формальных языков (в частности, языков программирования). Здесь мы пытаемся перекинуть «мостик» от чистой теории к практической технологии анализа контекстно-свободных языков, используемой прежде всего в компиляторах. Этот материал призван проиллюстрировать связь между изложеной математической теорией и ее приложениями к разработке математического обеспечения компьютеров.

Предисловие

   В конце каждой главы помещены задачи для самостоятельного решения. Наиболее трудные задачи снабжены указаниями. В некоторых задачах содержатся и теоретические результаты, дополняющие основной текст. Часть задач придумана авторами, часть заимствована из других задачников и учебников.
   Дискретная математика — бурно развивающаяся область. К сожалению, в этом учебнике мы не нашли возможности даже обзорно изложить некоторые результаты, развивающие классическую теорию графов (гиперграфы, сети Петри, потоковые диаграммы) и теорию языков (сверхъязыки, автоматы над структурами, отличными от слов, теорию алгоритмов как динамических систем, топологические методы в семантике). Мы рекомендуем интересующемуся читателю обстоятельно написанную «Handbook of Theoretical Computer Science», а также последние выпуски периодического издания «Lecture notes in Computer Science». Наиболее интересные, с нашей точки зрения, работы из этого издания указаны в списке литературы.
   Для успешного освоения материала книги достаточно знания традиционных курсов математического анализа и линейной алгебры, читаемых в техническом университете. Мы в основном опирались на материал, изложенный в выпусках I-IV настоящего комплекса учебников.
   В тексте книги имеются ссылки на другие выпуски комплекса учебников. Такой ссылкой служит номер выпуска. Например, [I] означает, что имеется в виду первый выпуск. Ссылки без римских цифр относятся только к этому, девятнадцатому, выпуску. Так, (см. 1.2) отсылает читателя ко второму параграфу первой главы, а (см. Д.7.1) — к первому дополнению седьмой главы этой книги. Ссылки на номера формул и рисунков набраны обычным шрифтом (например, (2.1) — первая формула в главе 2, (рис. 1.5) — пятый рисунок в главе 1).
   Большинство используемых в этой книге обозначений помещено в перечне основных обозначений, где наряду с их краткой расшифровкой указаны глава и параграф, в кото

Предисловие

9

рых можно найти более подробное объяснение по каждому из обозначений. Для части обозначений, введенных в первом выпуске, указаны глава и параграф первого выпуска, а также при необходимости глава и параграф этой книги. Например, I-1.3, 1.1 показывает, что обозначение введено в третьем параграфе первой главы первого выпуска и пояснения к нему содержатся в первом параграфе первой главы девятнадцатого выпуска. После этого перечня приведены написание и русское произношение входящих в формулы букв латинского и греческого алфавитов.
   В конце книги помещены список рекомендуемой литературы и предметный указатель, в котором расположены в алфавитном порядке (по существительному в именительном падеже) все выделенные в тексте полужирным курсивом термины с указанием страницы, где они строго определены или описаны.
   Выделение термина светлым курсивом означает, что этот термин в данном параграфе относится к ключевым словам и читателю должно быть известно его значение. Значение этого термина можно уточнить, найдя с помощью предметного указателя необходимую страницу этого выпуска, на которой термин определен или описан. Если термин введен в другом выпуске, то дана ссылка на этот выпуск (например, III означает ссылку на третий выпуск), а также указана курсивом страница предлагаемой книги, на которой имеются некоторые пояснения к этому термину.
   Авторы выражают глубокую благодарность А.А. Кириль-ченко и М.С. Виноградовой за многочисленные пожелания и замечания, которые были учтены при подготовке книги.
   Перед чтением книги в целях самоконтроля предлагается выполнить приведенные ниже задания. В тексте заданий прямым полужирным шрифтом выделены термины, значение которых должно быть известно читателю, а в конце каждого задания указана ссылка на номер выпуска, в котором можно найти соответствующие разъяснения. В основном тексте книги эти термины не выделены и не входят в предметный указатель.

Предисловие

Задания для самопроверки

   1.    Что такое конечное множество, подмножество, элемент множества? Какими способами можно задать множество? Приведите примеры конечных и счетных множеств. [I]
   2.    Является ли множество всех рациональных чисел счетным? [I]
   3.    Что такое множество всех действительных чисел? Что понимают под расширенной (пополненной) числовой прямой? [I]
   4.    Является ли множество натуральных чисел собственным подмножеством множества целых чисел? [I]
   5.    Какие операции над множествами вы знаете? Перечислите свойства этих операций. [I]
   6.    В чем заключается принцип двойственности для законов де Моргана? [I]
   7.    Из каких этапов состоит доказательство по методу математической индукции? [I]
   8.    Сформулируйте определение взаимно однозначного отображения двух множеств. Что такое тождественное отображение? Чему равна композиция прямого и обратного отображений двух множеств? [I]
   9.    При каких условиях отображение одного множества в другое называют сюръекцией, инъекцией и биекцией? [I]
   10.    Что называют неподвижной точкой отображения? Сколько неподвижных точек у отображения у = sin х ? [I]
   11.  Какие элементарные функции вы знаете? [II]
   12.    Что такое область определения и область значения функции? [I]
   13.    Приведите примеры функций, непрерывных в интервале (а, b). В чем различие между монотонной и строго монотонной в некотором промежутке функциями? [I]
   14.  Что такое последовательность элементов множества? [I]
   15.    Какими свойствами обладает предел последовательности? [I]
   16.    Сформулируйте признак Вейерштрасса сходимости ограниченной последовательности. [I]