Основы дискретной математики. Лекции 1-7

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