Черемисинова Л.Д. Дискретная математика

Учебное пособие. — Минск: Белорусский государственный университет информатики и радиоэлектроники, 2019. — 299 с. — ISBN: 978-985-543-460-4.Изложены материалы по основным разделам дискретной математики, описаны комбинаторные алгоритмы на матрицах и графах. Издание основано на лекционном курсе, который читается автором в учреждении образования «Белорусский государственный университет информатики и радиоэлектроники» для студентов специальностей, связанных с вычислительной техникой и программированием.Предисловие.
Множества.
Основные понятия.
Множества и элементы.
Способы задания множеств.
Операции над множествами.
Отношения между множествами.
Отношения равенства и включения.
Булеан.
Разбиение и покрытие множеств.
Булева алгебра множеств.
Формулы над множествами.
Основные законы алгебры множеств.
Равносильные преобразования в алгебре множеств.
Задания.
Отношения.
Декартово произведение.
Отношения п-арные и бинарные.
Представление бинарных отношений.
Операции над бинарными отношениями.
Функциональные отношения и отображения.
Бинарные отношения на множестве.
Свойства бинарных отношений на множестве.
Отношение эквивалентности.
Отношения порядка.
Задания.
Комбинаторные задачи и вычислительная сложность.
Перечислительная комбинаторика.
Основные правила и конфигурации.
Подсчет числа конфигураций.
Связь числа сочетаний с биномиальными коэффициентами.
Сложность алгоритмов.
Оценка трудоемкости алгоритмов.
Сравнение скорости роста временной сложности.
Классы сложности алгоритмов.
Вычисление оценок трудоемкости алгоритмов.
Методы комбинаторного поиска.
Особенности комбинаторных задач.
Дерево поиска.
Задача о кратчайшем покрытии.
Задания.
Графы.
Графы: виды и задание.
Неориентированный граф.
Операции над графами.
Специальные типы графов.
Обобщения графов.
Части графов.
Ориентированный граф.
Графы и бинарные отношения.
Изоморфизм графов.
Отношение изоморфизма.
Установление изоморфизма графов.
Канонизация графов.
Обходы графа.
Достижимость и связность.
Эйлеровы графы.
Гамильтоновы графы.
Кратчайшие пути в графе.
Независимость и покрытия.
Доминирующие множества графа.
Независимые множества графа.
Клики графа.
Независимые множества и клики графа.
Вершинные покрытия графа.
Паросочетания и реберные покрытия.
Раскраски и планарность.
Раскраска графа.
Бихроматические графы.
Планарные графы.
Раскраска планарных графов.
Циклы и разрезы графа.
Деревья, леса, остовы.
Базис циклов. Цикломатическое число графа.
Базис разрезов.
Матрицы циклов и разрезов.
Числа графов.
Задания.
Математическая логика.
Основные понятия.
Переменные, операции.
Формулы и функции.
Вычисление значения формулы.
Отношения между формулами.
Равносильность.
Формальная импликация.
Выполнимость и общезначимость формул.
Булева алгебра.
Основные законы булевой алгебры.
Интерпретации булевой алгебры.
Равносильные преобразования формул.
Нормальные формы булевой алгебры.
Дизъюнктивная нормальная форма.
Совершенная дизъюнктивная нормальная форма.
Конъюнктивная нормальная форма.
Совершенная конъюнктивная нормальная форма.
Связь ДНФ и КНФ, взаимные преобразования.
Логика высказываний и логический вывод.
Высказывания.
Алгебраические представления.
Основные тавтологии логики высказываний.
Логический вывод.
Логика предикатов.
Предикаты и кванторы.
Теоретико-множественная интерпретация предикатов.
Формулы логики предикатов.
Нормальные формы логики предикатов.
Задания.
Булевы функции.
Булево пространство.
Графическое задание булева пространства.
Интервалы булева пространства.
Развертка гиперкуба на плоскость.
Карта Карно.
Булевы функции.
Основные определения.
Способы представления булевых функций.
Элементарные булевы функции.
Теоретико-множественная интерпретация операций над булевыми функциями.
Векторные вычисления булевых функций.
Некоторые важные классы булевых функций.
Двойственные функции.
Принцип двойственности.
Монотонные функции.
Линейные функции.
Разложение булевых функций по переменным.
Дизъюнктивное разложение Шеннона.
Конъюнктивное разложение Шеннона.
Системы булевых функций.
Задания.
Реализация булевых функций комбинационными схемами.
Функциональная полнота.
Функционально полные системы функций.
Важнейшие замкнутые классы.
Теорема о функциональной полноте.
Минимальная полная система функций.
Реализация булевых функций.
Релейно-контактные схемы.
Схемы на транзисторах.
Схемы из функциональных элементов.
Реализация булевых функций на программируемой логической матрице.
Минимизация булевых функций.
Упрощение дизъюнктивных нормальных форм.
Локальные методы упрощения ДНФ.
Сокращенные и минимальные дизъюнктивные нормальные формы.
Получение множества всех простых импликант.
Метод Квайна – Мак-Класки.
Построение и покрытие матрицы Квайна.
Визуальный метод минимизации булевых функций.
Представление булевой функции на карте Карно.
Минимизация ДНФ с помощью карт Карно.
Многошаговый процесс минимизации с помощью карты Карно.
Задания.
Литература.
Предметный указатель.