Семинары по базовому курсу дискретной математики, посвященному теории дискретных функций. В курсе рассматриваются функции алгебры логики, графы, основы кодирования.

Список всех тем лекций

Семинар 1. Булевы функции. Часть 1.
Булева функция Сколько всего булевых функций Булевы функции от двух переменных Булевы функции, обладающие некоторыми свойствами

Семинар 2. Булевы функции. Часть 2.
Существенная и несущественная (фиктивная) переменная Добавление и удаление фиктивной переменной Равные функции Основные эквивалентности Решение задач с применением основных эквивалентностей Симметрические функции Функции, которые зависят от всех своих переменных существенно Задача (при каких значениях n заданная функция зависит от всех своих переменных) Задача (при каких значениях n заданная функция зависит от всех своих переменных) Разложение функции по первой переменной

Семинар 3. Булевы функции. Часть 3.
Совершенная конъюнктивная нормальная форма (повторение) Пример Лемма о сводимости Двойственная функция Полные системы Представление функции в виде полинома Жегалкина Алгоритм построения полинома Жегалкина (наиболее быстрый) Задачи (построение полинома Жегалкина) Доказательство утверждения о том, что любую функцию можно выразить полиномом Жегалкина единственным образом

Семинар 4. Булевы функции. Полином Жегалкина.
(полином Жегалкина) (полином Жегалкина) Замыкание Замкнутые классы

Семинар 5. Булевы функции. Замкнутые классы.
Повторение материала предыдущего семинара Замкнутый класс L (класс линейных функций) Класс монотонных функций Мощности классов Примеры

Семинар 6. Булевы функции. Полнота булевых функций.
Замкнутые классы (повторение материала предыдущих лекций) Предполная система функций Критерий Поста (предполный класс) (предполный класс) Теорема Поста Определение полноты булевых функций Задача (определение полноты функции) Задача (определение полноты функции)

Семинар 7. Функции k-значной логики. Часть 1.
Функции k-значной логики Сколько всего функций k-значной логики переменных переменной переменных Полная система Пример (представление заданной функции в виде универсальной формы) Задача (лемма о сводимости) Задача (лемма о сводимости) Задача (полнота системы)

Семинар 8. Функции k-значной логики. Часть 2.
Повторение материала предыдущего семинара Задача (полнота системы) - продолжение решения задачи из семинара 7 Отношение эквивалентности Задача (доказательство полноты системы) Задача (доказательство полноты системы) Монотонность

Семинар 9. Схемы из функциональных элементов. Часть 1.
Примеры) Схемы из функциональных элементов Максимально эффективная реализация булевой функции Вычисление сложности конкретных функций Сложность функции голосования

Семинар 10. Схемы из функциональных элементов. Часть 2.
Повторение материала предыдущего семинара Задача (реализовать схемой сложностью 4) Задача (реализовать схемой сложностью 6) Функция Шеннона Метод каскадов Задача (о сложности реализации сумматора)

Семинар 11. Схемы из функциональных элементов. Часть 3.
Сложность сумматора Сложность симметрической функции Задача (реализация функций отрицания трёх переменных) Задача (реализации сложности функции произведения переменных) Автоматы

Семинар 12. Детерминированные функции. Часть 1.

Семинар 13. Детерминированные функции. Часть 2.