Дискретная математика (3600,00 руб.)

Стр.4

Стр.701

Стр.702

Стр.703

УДК 512.5+519.1(075.8) ББК 22.174 Б43 Издание доступно в электронном виде по адресу https: //bmstu .press / catalog / item/6993 / Рецензенты: член-корреспондент РАН Ю.Н. Павловский, профессор А .К . Платонов Белоусов, А . И. Б43 Дискретная математика : учебник для вузов / А . И. Белоусов, С. Б. Ткачев ; под ред. В. С. Зарубина, А . П. Крищенко. — 7-е изд., испр. — Москва : Издательство МГТУ им. Н. Э. Баумана, 2021. — 703, [1] с. : ил. — (Математика в техническом университете ; вып. 19). ISBN 978-5-7038-3845-7 ISBN 978-5-7038-5536-2 (вып. 19) В девятнадцатом выпуске серии «Математика в техническом университете» изложены теория множеств и отношений, элементы современной абстрактной алгебры, теория графов, классические понятия теории булевых функций, а также основы теории формальных языков, куда включены теории конечных автоматов, регулярных языков, контекстно-свободных языков и магазинных автоматов. В анализе графов и автоматов особое внимание уделено алгебраическим методам. Содержание учебника соответствует курсу лекций, который авторы читают в М ГТУ им. Н.Э. Баумана. Для студентов технических университетов. Может быть полезен преподавателям, аспирантам и инженерам. УДК 512.5+519.1(075.8) ББК 22.174 Уважаемые читатели! Пожелания, предложения, а также сообщения о замеченных опечатках и неточностях Издательство просит направлять по электронной почте: info@baumanpress.ru ®> Белоусов А .И ., Ткачев С.Б., 2001 © Белоусов А .И ., Ткачев С.Б., 2021, с изменениями ISBN 978-5-7038-5536-2 (вып. 19) ISBN 978-5-7038-3845-7 '£) Оформление. Издательство МГТУ им. Н.Э. Баумана, 2021

Стр.4

ОГЛАВЛЕНИЕ П р еди слови е .............................................................................................. 5 Основные обозначения ........................................................................... 12 1. Множества и отн ош ени я .................................................................. 23 1.1. М н ож е с тв а .................................................................................. 23 1.2. Кортеж. Декартово произведение........................................ 36 1.3. Соответствия и бинарные отношения................................. 39 1.4. Операции над соотв етстви ям и ............................................. 49 1.5. Семейства м н ож е с т в ................................................................ 58 1.6. Специальные свойства бинарных о тн ош ений ................. 59 1.7. Отношения экви ва лен тн о сти ............................................... 67 1.8. Упорядоченные множества. Теорема о неподвижной т о ч к е .............................................................................................. 72 1.9. Мощность множества................................................................ 85 Д1.1. Об одном парадоксе теории м н ож е с тв ............................... 96 Д1.2. Метод характеристических ф ункций ................................. 98 Вопросы и задачи ....................................................................... 101 2. А лгебры : группы и к о л ь ц а ............................................................. 107 2.1. Операции. Понятие алгебраической с тр у к т у ры ............ 107 2.2. Группоиды, полугруппы , группы ........................................ 115 2.3. Кольца , тела, п о л я .................................................................... 128 2.4. Области ц е ло с тн о с ти ............................................................... 134 2.5. Модули и линейные пространства ...................................... 138 2.6. Подгруппы и п о д к о л ьц а ......................................................... 140 2.7. Теорема Л а гр а нж а .................................................................... 144 2.8. Гомоморфизмы групп и нормальные д е л и т е л и .............. 149 2.9. Гомоморфизмы к о л е ц ............................................................. 157 Д2.1. К в а т ер н и оны .............................................................................. 160 Вопросы и задачи ....................................................................... 162 3. П олукольц а и булевы а л г е б р ы ...................................................... 166 3.1. П олукольца . Основные п р им еры ........................................ 166 3.2. Замкнутые п о л у к о л ьц а ........................................................... 172 3.3. Решение систем линейных уравнений ............................... 185 3.4. Булевы а л г е б р ы ......................................................................... 193 3.5. Р еш е т к и ....................................................................................... 200 Вопросы и задачи ....................................................................... 211

Стр.701

702 Оглавление 4. Алгебраические системы .................................................................. 214 4.1. Модели и а л г е б р ы .................................................................... 214 4.2. П о д си с т ем ы ................................................................................ 218 4.3. Конгруэнции и фактор-системы .......................................... 224 4.4. Гомоморфизмы ........................................................................... 229 4.5. Прямые произведения алгебраических си стем .............. 240 4.6. Конечные булевы алгебры ...................................................... 246 4.7. Многосортные а л г е б р ы ........................................................... 251 Вопросы и задачи ....................................................................... 258 5. Теория г р а ф о в ..................................................................................... 260 5.1. Основные определения............................................................. 261 5.2. Способы представления ........................................................... 271 5.3. Д ер ев ь я ......................................................................................... 280 5.4. Остовное дерево наименьшего веса...................................... 288 5.5. Методы систематического обхода вершин г р а ф а 293 5.6. Задача о путях во взвешенных ориентированных граф ах ............................................................................................ 307 5.7. Изоморфизм графов .................................................................. 321 5.8. Топологическая сор ти р овк а ................................................. 328 5.9. Элементы цикломатики ........................................................... 335 Вопросы и задачи ....................................................................... 346 6. Булевы функции.................................................................................. 352 6.1. Понятие булевой функции. Булев к у б ............................... 352 6.2. Таблицы булевых ф ункций .................................................... 361 6.3. Фиктивные переменные. Равенство булевых функций 365 6.4. Ф ормулы и суперпозиции ...................................................... 370 6.5. Дизъюнктивные и конъюнктивные нормальные ф ормы ............................................................................................ 382 6.6. Построение минимальных Д Н Ф .......................................... 385 6.7. Теорема П о с т а ........................................................................... 404 6.8. Схемы из функциональных элементов ............................... 421 Вопросы и задачи ....................................................................... 430 7. Конечные автоматы и регулярные я зы к и ................................. 434 7.1. Алфавит, слово, я з ы к ............................................................. 436 7.2. Порождающие грамматики .................................................... 445 7.3. Классификация грамматик и языков ................................. 458 7.4. Регулярные языки и регулярные выражения................. 462 7.5. Конечные автоматы. Теорема К л и н и ................................. 466 7.6. Детерминизация конечных автоматов ............................... 491 7.7. Минимизация конечных автоматов ................................... 501 7.8. Лемма о разрастании для регулярных я зы к о в .............. 507

Стр.702

Оглавление 703 Д7.1. Обоснование алгоритма детерминизации конечных ав том а тов ..................................................................................... 513 Д7.2. Конечные автоматы с выходом. Структурный синтез . . 520 Д7.3. Морфизмы и конечные под стан овки ................................. 532 Д7.4. Машины Т ью р и н г а .................................................................. 537 Вопросы и задачи ....................................................................... 546 8. Контекстно-свободные я зы к и ...................................................... 554 8.1. КС-грамматики. Деревья вывода. Однозначность 8.2. Приведенная форма КС -грамматики ................................. 569 8.3. Лемма о разрастании для КС -языков ................................. 581 8.4. Магазинные автоматы ............................................................. 590 8.5. Алгебраические свойства КС -язы ков ................................. 616 Д8.1. О методах синтаксического анализа КС -язы ков ............ 635 Д8.2. Семантика формальных я зы к о в ........................................... 652 Д8.3. Графовое представление МП-автоматов............................ 670 Вопросы и задачи ....................................................................... 674 Л и т ер а т ур а ................................................................................................ 679 Предметный указатель ........................................................................... 684 554

Стр.703