Белоусов А.И., Ткачев С.Б. Дискретная математика

Учеб. для вузов / Под ред. B.C. Зарубина, А.П. Крищенко. - 3-е изд., стереотип. - М.: Изд-во МГТУ им. Н.Э. Баумана, 2004. - 744 с. - (Сер. Математика в техническом университете; Вып. XIX). - ISBN 5-7038-1769-2 (Вып. XIX), ISBN 5-7038-1270-4.В девятнадцатом выпуске серии "Математика в техническом университете" изложены теория множеств и отношений, элементы современной абстрактной алгебры, теория графов, классические понятия теории булевых функций, а также основы теории формальных языков, куда включены теории конечных автоматов, регулярных языков, контекстно-свободных языков и магазинных автоматов. В анализе графов и автоматов особое внимание уделено алгебраическим методам.
Содержание учебника соответствует курсу лекций, который авторы читают в МГТУ им. Н. Э. Баумана.
Для студентов технических университетов. Может быть полезен преподавателям, аспирантам и инженерам.OCR.Множества и отношения.
Множества.
Кортеж. Декартово произведение.
Соответствия и бинарные отношения.
Операции над соответствиями.
Семейства множеств.
Специальные свойства бинарных отношений.
Отношения эквивалентности.
Упорядоченные множества. Теорема о неподвижной точке.
Мощность множества.
Об одном парадоксе теории множеств.
Метод характеристических функций.
Вопросы и задачи.Алгебры: группы и кольца.
Операции. Понятие алгебраической структуры.
Группоиды, полугруппы, группы.
Кольца, тела, поля.
Области целостности.
Модули и линейные пространства.
Подгруппы и подкольца.
Теорема Лагранжа.
Гомоморфизмы групп и нормальные делители.
Гомоморфизмы колец.
Кватернионы.
Вопросы и задачи.Полукольца и булевы алгебры.
Полукольца. Основные примеры.
Замкнутые полукольца.
Решение систем линейных уравнений.
Булевы алгебры.
Решетки.
Вопросы и задачи.Алгебраические системы.
Модели и алгебры.
Подсистемы.
Конгруэнции и фактор-системы.
Гомоморфизмы.
Прямые произведения алгебраических систем.
Конечные булевы алгебры.
Многосортные алгебры.
Вопросы и задачи.Теория графов.
Основные определения.
Способы представления.
Деревья.
Остовное дерево наименьшего веса.
Методы систематического обхода вершин графа.
Задача о путях во взвешенных ориентированных графах.
Изоморфизм графов.
Топологическая сортировка.
Элементы цикломатики.
Вопросы и задачи.Булевы функции.
Понятие булевой функции. Булев куб.
Таблицы булевых функций.
Фиктивные переменные. Равенство булевых функций.
Формулы и суперпозиции.
Дизъюнктивные и конъюнктивные нормальные формы.
Построение минимальных ДНФ.
Теорема Поста.
Схемы из функциональных элементов.
Вопросы и задачи.Конечные автоматы и регулярные языки.
Алфавит, слово, язык.
Порождающие грамматики.
Классификация грамматик и языков.
Регулярные языки и регулярные выражения.
Конечные автоматы. Теорема Клини.
Детерминизация конечных автоматов.
Минимизация конечных автоматов.
Лемма о разрастании для регулярных языков.
Обоснование алгоритма детерминизации конечных автоматов.
Конечные автоматы с выходом. Структурный синтез.
Морфизмы и конечные подстановки.
Машины Тьюринга.
Вопросы и задачи.Контекстно-свободные языки.
КС-грамматики. Деревья вывода. Однозначность.
Приведенная форма КС-грамматики.
Лемма о разрастании для КС-языков.
Магазинные автоматы.
Алгебраические свойства КС-языков.
О методах синтаксического анализа КС-языков.
Семантика формальных языков.
Графовое представление МП-автоматов.
Вопросы и задачи.