Дискретная математика: учебник для студентов высших технических учебных заведений

Титульный лист Выходные данные Предисловие Основные обозначения 1. Множества и отношения 1.1. Множества 1.2. Кортеж. Декартово произведение 1.3. Соответствия и бинарные отношения 1.4. Операции над соответствиями 1.5. Семейства множеств 1.6. Специальные свойства бинарных отношений 1.7. Отношения эквивалентности 1.8. Упорядоченные множества. Теорема о неподвижной точке 1.9. Мощность множества Д.1.1. Об одном парадоксе теории множеств Д.1.2. Метод характеристических функций Вопросы и задачи 2. Алгебры: группы и кольца 2.1. Операции. Понятие алгебраической структуры 2.2. Группоиды, полугруппы, группы 2.3. Кольца, тела, поля 2.4. Области целостности 2.5. Модули и линейные пространства 2.6. Подгруппы и подкольца 2.7. Теорема Лагранжа 2.8. Гомоморфизмы групп и нормальные делители 2.9. Гомоморфизмы колец Д.2.1. Кватернионы Вопросы и задачи 3. Полукольца и булевы алгебры 3.1. Полукольца. Основные примеры 3.2. Замкнутые полукольца 3.3. Решение систем линейных уравнений 3.4. Булевы алгебры 3.5. Решетки Вопросы и задачи 4. Алгебраические системы 4.1. Модели и алгебры 4.2. Подсистемы 4.3. Конгруэнции и фактор-системы 4.4. Гомоморфизмы 4.5. Прямые произведения алгебраических систем 4.6. Конечные булевы алгебры 4.7. Многосортные алгебры Вопросы и задачи 5. Теория графов 5.1. Основные определения 5.2. Способы представления 5.3. Деревья 5.4. Остовное дерево наименьшего веса 5.5. Методы систематического обхода вершин графа 5.6. Задача о путях во взвешенных ориентированных графах 5.7. Изоморфизм графов 5.8. Топологическая сортировка 5.9. Элементы цикломатики Вопросы и задачи 6. Булевы функции 6.1. Понятие булевой функции. Булев куб 6.2. Таблицы булевых функций 6.3. Фиктивные переменные. Равенство булевых функций 6.4. Формулы и суперпозиции 6.5. Дизъюнктивные и конъюнктивные нормальные формы 6.6. Построение минимальных ДНФ 6.7. Теорема Поста 6.8. Схемы из функциональных элементов Вопросы и задачи 7. Конечные автоматы и регулярные языки 7.1. Алфавит, слово, язык 7.2. Порождающие грамматики 7.3. Классификация грамматик и языков 7.4. Регулярные языки и регулярные выражения 7.5. Конечные автоматы. Теорема Клини 7.6. Детерминизация конечных автоматов 7.7. Минимизация конечных автоматов 7.8. Лемма о разрастании для регулярных языков Д.7.1. Обоснование алгоритма детерминизации конечных автоматов Д.7.2. Конечные автоматы с выходом. Структурный синтез Д.7.3. Морфизмы и конечные подстановки Д.7.4. Машины Тьюринга Вопросы и задачи 8. Контекстно-свободные языки 8.1. КС-грамматики. Деревья вывода. Однозначность 8.2. Приведенная форма КС-грамматики 8.3. Лемма о разрастании для КС-языков 8.4. Магазинные автоматы 8.5. Алгебраические свойства КС-языков Д.8.1. О методах синтаксического анализа КС-языков Д.8.2. Семантика формальных языков Д.8.3. Графовое представление МП-автоматов Вопросы и задачи Список рекомендуемой литературы Предметный указатель Оглавление