Судоплатов С.В., Овчинникова Е.В. Дискретная математика

Учебное пособие. — Новосибирск: НГТУ, 2011. — 144 с.В книге излагаются основы теории множеств, алгебраических систем, теории графов и алгебры логики, которые образуют курс дискретной математики. Книга предназначена для студентов технических вузов, изучающих дискретную математику в рамках дистанционного образования.Предисловие.
Элементы теории множеств.
Множества и основные операции над ними.
Отношения. Функции. Взаимно однозначные соответствия.
Натуральные числа. Принцип математической индукции.
Мощность множества. Конечные и бесконечные множества.
Матрица бинарного отношения. Специальные бинарные отношения.
Отношения эквивалентности и разбиения. Фактор-множества.
Отношения порядка.
Задачи и упражнения.Алгебраические системы.
Определения и примеры.
Морфизмы.
Подсистемы.
Конгруэнции. Фактор-алгебры. Теорема о гомоморфизме.
Решетки и булевы алгебры.
Алгебры отношений и реляционные алгебры.
Задачи и упражнения.Элементы теории графов
Виды и способы задания графов
Подграфы и части графа. Операции над графами
Маршруты. Достижимость. Связность
Расстояния в графах
Нахождение кратчайших маршрутов
Степени вершин
Обходы графов
Остовы графов
Фундаментальные циклы
Разрезы
Раскраски графов
Планарные графы
Задачи и упражненияАлгебра логики
Формулы алгебры логики
Функции алгебры логики
Эквивалентность формул
Дизъюнктивные и конъюнктивные нормальные формы
Двухэлементная булева алгебра. Фактор-алгебра алгебры формул
Минимизация булевых функций в классе ДНФ
Карты Карно
Принцип двойственности для булевых функций
Полные системы булевых функций
Логические сети
Проверка теоретико-множественных соотношений с помощью алгебры логики
Задачи и упражненияВарианты контрольной работы