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

Стр.2

Стр.5

Стр.702

Стр.703

Стр.704

Премии Правительства Российской Федерации в области науки и техники за 2003 год Комплекс учебников удостоен МАТЕМАТИКА В ТЕХНИЧЕСКОМ УНИВЕРСИТЕТЕ Выпуск 19

Стр.2

УДК 512.5+519.1(075.8) ББК 22.174 Á43 Рецензенты: член-корреспондент РАН Ю.Н. Павловский, профессор А.К. Платонов Á43 Áåëîóñîâ, À. È. ìàíà, 2020. Дискретная математика : учебник для вузов / А. И. Белоусов, Ñ. Á. Ткачев ; под ðåä. 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 ISBN 978-5-7038-4905-7 (âûï. 19) ISBN 978-5-7038-3845-7 © Белоусов À.È., Ткачев Ñ.Á., 2001 © Белоусов À.È., Ткачев Ñ.Á., 2006, с изменениями © Оформление. Издательство МГТУ èì. Í. Ý. Áàóìàíà, 2020

Стр.5

ОГЛАВЛЕНИЕ Предисловие ........................................ . 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

Стр.702

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

Стр.703

Оглавление 703 Д7.1. Обоснование алгоритма детерминизации конечных автоматов .................................... . 513 Ä7.2. Конечные автоматы с âûõîäîì. Структурный синтез . . 520 Ä7.3. Морфизмы и конечные подстановки .............. . 532 Ä7.4. Машины Тьюринга ............................ . 537 Вопросы и çàäà÷è.............................. . 546 8. Контекстно-свободные языки ........................ . 554 8.1. ÊÑ-ãðàììàòèêè. Деревья âûâîäà. Îäíîçíà÷íîñòü.... . 554 8.2. Приведенная форма КС-грамматики .............. . 569 8.3. Лемма о разрастании для ÊÑ-ÿçûêîâ.............. . 581 8.4. Магазинные автоматы . . . . . . . . . . . . . . . . . . . . . . . . . . . 590 8.5. Алгебраические свойства ÊÑ-ÿçûêîâ .............. . 616 Ä8.1. О методах синтаксического анализа ÊÑ-ÿçûêîâ ..... . 635 Ä8.2. Семантика формальных языков .................. . 652 Ä8.3. Графовое представление ÌÏ-àâòîìàòîâ............ . 670 Вопросы и çàäà÷è.............................. . 674 Литература ......................................... . 679 Предметный óêàçàòåëü................................ . 684

Стр.704