Раздел 1. Множества и отношения

Тема 1. Введение в дисциплину. Множества и способы их задания

Понятие множества. Способы задания множеств. Характеристические функции. Конечные и счетные множества. Диаграммы Эйлера-Венна. Собственное и несобственное подмножества. Операции над множествами. Законы алгебры множеств. Мощность множества. Формула включений и исключений.

Тема 2. Кортежи и прямое произведение множеств
Элементы комбинаторики

Кортежи и прямое произведение множеств. Операции над кортежами, комбинаторика. Проекция.

Тема 3. Отношения, соответствия и отображения

Отношения: отношение эквивалентности, отношение порядка. Бинарные отношения, матрица бинарного отношения. Способы задания бинарных отношений. Соответствия и отображения. Композиция бинарных отношений. График.

Раздел 2. Элементы математической логики

Тема 4. Высказывания

Основные понятия. Определения. Основные логические операции. Таблицы истинности. Формулы алгебры высказываний. Эквивалентность формул. Элементы теории доказательств: принцип математической индукции, принцип двойственности, система натурального вывода, прямоеобратное рассуждение. Принцип математической индукции.

Тема 5. Предикаты и кванторы

Предикаты. Кванторы. Исчисление предикатов. Диаграммы Эйлера.

Тема 6. Булевы функции

Двоичная арифметика. Булевы функции. Реализация булевых функций формулами. СДНФ и СКНФ. Карта Карно.Полные системы булевых функций. Важнейшие замкнутые классы булевых функций. Теорема Поста о полноте. Двойственность булевых функций.

Тема 7. Минимизация булевых функций

Задача минимизации булевых функций. Постановка задачи минимизации в классе ДНФ. Построение сокращенной ДНФ: геометрический метод, метод Квайна-Мак-Класки, метод Блейка. Поиск минимальных ДНФ.

Тема 8. Элементы теории алгоритмов

Понятие алгоритма. Вычислимые функции. Примитивно-рекурсивные функции.Частично-рекурсивные функции. Машина Тьюринга.Понятие сложности алгоритма.

Раздел 3. Элементы комбинаторики

Тема 9. Комбинаторика

Правила суммы и произведения. Принцип включения и исключения. Размещения и перестановки. Сочетания. Бином Ньютона. Биномиальные коэффициенты для отрицательных и дробных показателей. Свойства биномиальных коэффициентов.

Тема 10. Рекурсия

Рекуррентные соотношения. Возвратные последовательности. Числа Фибоначчи. Приемы вычисления сумм. Числа Каталана. Случайное блуждание.

Раздел 4. Элементы теории графов