Дискретная математика. Вып. 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-е издание

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