Данилов В.Г., Дубнов В Л., Лакерник А.Р., Райцин А.М. Дискретная математика

Учебное пособие для вузов. — М.: Горячая линия-Телеком, 2008. — 136 с.Изложены сведения из четырёх разделов дискретной математики: теории множеств - множества и операции над ними, отношения и их классификация, отображения, алгебраические системы и их морфизмы; математической логики - высказывания, булевы формулы и булевы функции, нормальные формы, минимизация булевых формул, предикаты и их выполнимость, предикатные формулы, соответствие между булевыми формулами и булевыми теоретико-множественными операциями; теории графов - рассматриваются основные задачи теории графов с упором на оптимизацию и алгоритмический подход к решению задач, в том числе контактные схемы, задача оптимизации путей с весами из полугруппы (инструмент многокритериальной оптимизации), задача о максимальном потоке в транспортной сети с простым и эффективным алгоритмом её решения; теории конечных автоматов, с рассмотрением таких задач, как инимизация числа состояний автомата, распознавание множеств, синтез автоматов.
Для студентов вузов, обучающихся по направлению подготовки бакалавров и магистров 550400 - «Телекоммуникации».Введение
Основные понятия теории множеств
Предварительные сведения из теории множеств
Операции на множествах и их специальные свойства
Элементы математической логики
Высказывания. Операции над высказываниями
Зависимости между операциями
Функции алгебры логики
Булевы формулы. Логическая оболочка системы булевых функций
Разложение функций по переменным
Совершенная дизъюнктивная нормальная форма
Совершенная конъюнктивная нормальная форма
Двойственность
Полнота и замкнутость
Многочлены Жегалкина
Классы Поста. Теорема Поста
Импликанты и минимизация ДНФ
Предикаты и кванторы
Предикатные формулы и операции над множествами
Задача выполнимости предиката
Основные определения и задачи теории графов
Основные определения
Сети, контактные схемы и булевы формулы
Задача, с которой началась теория графов
Задачи об оптимальных путях
Простые циклы в графах. Цикломатическое число графа
Эйлерова характеристика плоского графа
Потоки в транспортных сетях
Теорема о системе различных представителей и её приложение к теории графов
Поток, насыщающий выходные дуги
Элементы теории конечных автоматов
Понятие автомата
Варианты автоматов
Автоматы и графы
Минимизация числа состояний автомата
Распознавание множеств автоматами
Детерминизация источников и синтез автоматов
Список литературы
Приложение: задания для домашних контрольных работ
Список основных обозначений
Предметный указатель