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

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

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

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

Лекция 3. Замкнутые классы булевых функций.
Повторение предыдущей лекции Класс самодвойственных функций Свойства самодвойственных функций Лемма о несамодвойственной функции Следствие из леммы Класс монотонных функций Лемма о немонотонной функции Порождающие системы Теорема о функциональной полноте Две леммы для замкнутых классов Определение предполного класса Теорема о существовании пяти предполных классов Различия булевых функций и функций k-значной логики

Лекция 4. Функции k-значной логики.
Функции k-значной логики Конечное число функций Условие существенной переменной Элементарные функции Функции от одной переменной Функции от двух переменных Замыкание множества функций Построение полных множеств Первая универсальная форма Вторая универсальная форма Полная система из двух функций Характеристика функций I Реализация всех функций от одной переменной Функция Вебба Критерий Поста

Лекция 5. Отличия булевых и функций k-значной логики.
Алгоритм проверки полноты произвольной конечной системы Малая теорема Ферма Третье универсальное разложение функции Теорема о единственности полученного полинома для функции Следствие из теоремы Булевы и функции k-значной логики, существенно зависящие от переменных Замкнутые классы k-значной логики без базиса Замкнутые классы k-значной логики с бесконечным базисом Наличие у Pk континуума различных замкнутых классов

Лекция 6. Теорема Кузнецова о функциональной полноте.
Система, где любое множество функций k-значной логики является полным Сохранение множества функции Лемма о замкнутом классе, содержащем все селекторные функции Пример сохранения множества Лемма о множестве функций с двумя условиями Теорема Кузнецова о функциональной полноте Следствие из теоремы Графы

Лекция 7. Графы.
Изоморфизм графов Подграфы Пути, цепи и циклы Деревья Ориентированные пути, цепи и циклы Схемы из функциональных элементов Функции, реализуемые в вершинах схемы Автоматы Ограниченно-детерминированная функция

Лекция 8. Информационные деревья.
Информационное дерево Функция задержки Пример функции суммирования Поддерево Две вершины с поддеревьями Эквивалентные поддеревья Ограниченно-детерминированная функция Пример Диаграмма Мура Автоматы Обобщенные функции выходов и переходов

Лекция 9. Автоматные функции.
Автоматные функции Доказательство первого утверждения Автомат задержки Реализация автоматов схемами Обратные связи Пример автомата Изоморфные автоматы Отличимость состояний Отличимость автоматов Приведенные автоматы

Лекция 10. Теоремы Мура.
Первая теорема Мура Невозможность усиления теоремы Вторая теорема Мура Невозможность усиления теоремы Периодические слова Свойство k-периодичности Лемма о преобразовании периодических слов Следствие (о сохранении k-периодичности) Условие сохранения k-периодичности

Лекция 11. Схемы реализации булевых функций.
Суперпозиция на автоматных функциях Теорема о несуществовании полной системы АФ Схемы реализации булевых функций Представление в дизъюнктивной форме Совместная реализация конъюкций

Лекция 12. Методы Шеннона и каскадов.
Вспомогательная задача Метод Шеннона Метод каскадов Пример Оценка по методу каскадов Нижняя оценка функции Шеннона Утверждение об изоморфных схемах Утверждение об условии изоморфности Теорема о значениях функции Шеннона