Дехтярь М.И. Основы дискретной математики. Лекции 1-7

Предварительные сведения.
Содержание:
Множества.
Операции над множествами.
Как доказывать равенство множеств?
Отношения и функции. Мощность множества.
Задачи.
Индукция и комбинаторика.
Содержание:
Метод математической индукции.
Задачи.
Элементы комбинаторики.
Размещения, перестановки, сочетания.
Принцип включения и исключения.
Задачи.
Булевы функции и их представления.
Содержание:
Булевы функции от n переменных.
Геометрическое представление.
Табличное представление.
Булевы функции от 1-ой и 2-х переменных.
Формулы.
Булевы функции и логика высказываний.
Задачи.
Эквивалентность формул и нормальные формы.
Содержание:
Эквивалентность булевых формул.
Основные эквивалентности (тождества).
Эквивалентные преобразования формул.
Соглашения об упрощенной записи формул.
Дизъюнктивные и конъюнктивные нормальные формы.
Определение ДНФ и КНФ.
Совершенные ДНФ и КНФ.
Сокращенные ДНФ.
Многочлены Жегалкина.
Задачи.
Полные системы функций и теорема Поста.
Содержание:
Замкнутые классы функций.
Критерий полноты (теорема Поста).
Задачи.
Хорновские формулы и задача получения продукции.
Содержание:
Хорновские формулы.
Задача получения продукции.
Решение задачи о продукции.
Алгоритм ЗАМЫКАНИЕ(X,F).
Алгоритм ПрямаяВолна(X,y,F).
Алгоритм БыстроеЗамыкание(X,F).
Задачи.
Язык логики предикатов.
Содержание:
Утверждения о свойствах объектов и отношениях между ними.
Язык логики предикатов.
Синтаксис: формулы логики предикатов.
Семантика: системы и значения формул на их состояниях.
Эквивалентные формулы и нормальные формы.
Задачи.