Учебное пособие. — Екатеринбург: Издательство Уральского
университета, 2015. — 108 с. ISBN: 978-5-7996-1387-7.
В учебном пособии рассматриваются элементы дискретной математики:
логические исчисления, предикаты, булевы функции, комбинаторика,
теория графов, автоматы и алгоритмы. Приведено решение типовых
задач. Предназначается для студентов всех форм обучения всех
специальностей. Рекомендовано методическим советом УрФУ в качестве
учебного пособия для студентов, обучающихся по направлениям
подготовки 231300 — Прикладная математика; 141100 — Энергетическое
машиностроение; 140400 — Электроэнергетика и электротехника; 140100
— Теплоэнергетика и теплотехника; 141403 — Атомные станции:
проектирование, эксплуатация и инжиниринг; 280700 — Техносферная
безопасность.
Логические исчисления.
Множество, отношения, функции.
Множества.
Основное свойство множеств.
Способы задания множеств.
Операции с множествами.
Свойства А, В, С.
Отношения.
Основное свойство.
Теорема (об отношениях эквивалентности).
Структуры порядка.
Операции с отношениями.
Функции.
Предикаты.
Операции над предикатами.
Кванторы.
Предикатные формулы. Тавтологии.
Исчисление предикатов.
Булевы функции.
Определение и примеры.
Суперпозиция функций.
Тождества.
Дизъюнктивная нормальная форма БФ.
Полиномы Жегалкина.
Замкнутые классы БФ.
Теорема Поста.
Комбинаторика.
Основные правила.
Элементарные комбинаторные функции.
Свойства числа сочетаний.
Задача (о кроликах).
Теория графов.
Определение и задание графа.
Операции с множествами.
Изоморфизм графов.
О сложности алгоритмов.
Маршруты.
Связность.
Эйлеровы пути.
Деревья.
Потоки в сетях.
Алгоритм поиска максимального потока.
Расстояние в графах.
Двудольные графы.
Алгоритм проверки двудольности связного графа.
Паросочетание.
Плоские и планарные графы.
Автоматы и языки.
Языки.
Операции с языками.
Автоматы. Распознаватели.
Моноид переходов конечного автомата.
Распознавание автоматом и моноидом.
Свойства распознаваемых языков.
Замкнутость множества распознаваемых языков относительно произведения и итерации.
Рациональность и распознаваемость языков.
Множество, отношения, функции.
Множества.
Основное свойство множеств.
Способы задания множеств.
Операции с множествами.
Свойства А, В, С.
Отношения.
Основное свойство.
Теорема (об отношениях эквивалентности).
Структуры порядка.
Операции с отношениями.
Функции.
Предикаты.
Операции над предикатами.
Кванторы.
Предикатные формулы. Тавтологии.
Исчисление предикатов.
Булевы функции.
Определение и примеры.
Суперпозиция функций.
Тождества.
Дизъюнктивная нормальная форма БФ.
Полиномы Жегалкина.
Замкнутые классы БФ.
Теорема Поста.
Комбинаторика.
Основные правила.
Элементарные комбинаторные функции.
Свойства числа сочетаний.
Задача (о кроликах).
Теория графов.
Определение и задание графа.
Операции с множествами.
Изоморфизм графов.
О сложности алгоритмов.
Маршруты.
Связность.
Эйлеровы пути.
Деревья.
Потоки в сетях.
Алгоритм поиска максимального потока.
Расстояние в графах.
Двудольные графы.
Алгоритм проверки двудольности связного графа.
Паросочетание.
Плоские и планарные графы.
Автоматы и языки.
Языки.
Операции с языками.
Автоматы. Распознаватели.
Моноид переходов конечного автомата.
Распознавание автоматом и моноидом.
Свойства распознаваемых языков.
Замкнутость множества распознаваемых языков относительно произведения и итерации.
Рациональность и распознаваемость языков.