Учебное пособие — М.: МИИТ, 2004. — 71 с.
Предназначено для студентов специальностей, в учебных планах которых предусмотрена дисциплина "Дискретная математика". Содержит разделы: множества, бинарные отношения, функции, булевы функции, алгебра высказываний, предикаты, графы. Приведены варианты заданий и примеры их решения.Множества.
Основные понятия.
Способы задания множеств.
Основные операции над множествами.
Свойства операций над множествами.
Прямое произведение множеств.
Бинарные отношения.
Основные понятия.
Свойства отношений.
Отношения эквивалентности.
Отношения порядка.
Функции.
Основные понятия.
Мощности множеств.
Булевы функции.
Введение.
Основные логические операции.
Булевы функции.
Формулы.
Свойства логических операций.
Правила равносильных преобразований формул.
Нормальные формы.
Построение формулы по таблице истинности.
Необходимые и достаточные условия тождественности истинности (ложности) функций.
Принцип двойственности.
Задача минимизации булевой функции.
Моделирование алгебры высказываний при помощи релейно контактных схем.
Исчисление высказываний.
Введение.
Классическое исчисление высказываний.
Тождественно истинные и тождественно ложные формулы. Логическая эквивалентность.
Проверка выводов в логике высказываний. Проверка противоречивости набора формул.
Исчисление предикатов.
Введение.
Основные операции.
Операции над предикатами.
Определение формул логики предикатов. Равносильность формул.
Преобразования формул.
Приведенные формулы логики предикатов.
Графы.
Основные понятия.
Деревья.
Двудольные графы.
Количество ребер в графе.
Некоторые оптимизационные задачи на графах.
Примеры контрольных работ.
