по курсу "Математическая логика и теория алгоритмов"
Основные способы задания двоичных функций. Табличный способ задания.
Основные способы задания двоичных функций. Геометрический способ задания.
Основные способы задания двоичных функций. Задание двоичных функций формулами.
Нормальные формы двоичных функций. ДНФ и СДНФ. КНФ и СКНФ.
Многочлен Жегалкина двоичной функции.
Действительный многочлен двоичной функции.
Теорема о разложении двоичной функции в ряд Фурье.
Замыкание системы булевых функций и его свойства.
Полнота систем булевых функций. Утверждение о полноте системы k0.
Полнота систем булевых функций. Утверждение о полноте системы k1.
Полнота систем булевых функций. Утверждение о полноте системы k2.
Полнота систем булевых функций. Утверждение о полноте системы k3.
Полнота систем булевых функций. Утверждение о полноте системы k4.
Полнота систем булевых функций. Утверждение о полноте системы k5.
Шефферовы функции от двух переменных.
Замкнутые системы булевых функций. Утверждение о замкнутости класса Т0 .
Замкнутые системы булевых функций. Утверждение о замкнутости класса Т1 .
Замкнутые системы булевых функций. Утверждение о замкнутости класса L0 .
Замкнутые системы булевых функций. Утверждение о замкнутости класса L1 .
Замкнутые системы булевых функций. Утверждение о замкнутости класса S .
Замкнутые системы булевых функций. Утверждение о замкнутости класса М .
Критерий полноты системы булевых функций. Пример шефферовой функции от трех переменных.
Псевдобулевы функции. Базисы пространства псевдобулевых функций.
Функции к-значной логики. Представление к-значной функции, аналогичное СДНФ для двоичных функций. Аналоги операций дизъюнкция, конъюнкция и отрицание для кольца вычетов целых чисел.
Полные системы к-значных функций. Критерий Слупецкого (без доказательства). Утверждение о представлении к-значных функций многочленами (без доказательства).
Полные системы к-значных функций. Утверждение о полноте системы к-значных функций k1.
Полные системы к-значных функций. Утверждение о полноте системы к-значных функций k2.
Полные системы к-значных функций. Утверждение о полноте системы к-значных функций k3.
Полные системы к-значных функций. Утверждение о полноте системы к-значных функций k4.
Полные системы к-значных функций. Утверждение о полноте системы к-значных функций k5.
Импликанты и простые импликанты двоичных функций. Утверждение об импликантах двоичных функций.
Сложность двоичной функции. МДНФ двоичной функции. Утверждение об импликантах, входящих в МДНФ.
Сокращенная ДНФ и тупиковая ДНФ двоичной функции. Решение задачи минимизации для двоичных функций.
Геометрическая интерпретация минимизации ДНФ. Решение примера.
Метод Квайна вычисления сокращенной ДНФ двоичной функции.
Интерпретация Мак-Класки метода Квайна. Решение примера.
Утверждение о МДНФ монотонной функции.
Метод Петрика вычисления тупиковых ДНФ двоичных функций.
Алгебраические системы. Алгебры и модели. Определение и примеры.
Булева алгебра. Определение и примеры.
Частично упорядоченные множества. Определения и примеры. Диаграмма булевой алгебры.
Изоморфизм алгебраических систем.
Основные логические операции и их свойства. Алгебра высказываний.
Модель предикатов. Предикаты и операции над ними.
Логические операции "навешивания" на предикаты кванторов всеобщности и существования.
Общее понятие о логическом исчислении. Основные характеристики логического исчисления. Язык, синтаксис и семантика исчисления.
Понятие алгоритма. Основные требования к алгоритмам. Основные типы алгоритмических моделей.
Машина Тьюринга. Устройство и функционирование.
Вычисление функций на машине Тьюринга. Примеры построения машин Тьюринга, правильно вычисляющих следующие функции: f(x)=x+l, f(x)=0, f(x)=x+y.
Суперпозиция машин Тьюринга.
Соединения машин Тьюринга.
Ветвление машин Тьюринга.
Реализация цикла на машине Тьюринга.
Тезис Тьюринга.
Машины произвольного доступа (МПД). Устройство и функционирование.
Вычисление функций на МПД. Примеры.
Программы стандартного вида (для МПД).
Композиция программ (для МПД). Примеры.
Использование программ в качестве подпрограмм других программ (для МПД).
Тезис Черча для (МПД).
Частично рекурсивные функции и операции над ними. Примеры.
Тезис Черча (для частично рекурсивных функций).
Определение алгоритмически разрешимых и неразрешимых проблем. Примеры.
Определение функций временной и емкостной сложности машины Тьюринга. Теорема о соотношении функций временной и емкостной сложности для машины Тьюринга.
Определение класса сложности Р. Примеры.
Определение класса сложности NP. Примеры.
Теорема о сложности решения NP-задачи на детерминированной машине Тьюринга (без доказательства).
Понятие о полиномиальной сводимости задач. Определение NP-полной и NP-трудной задачи.
Утверждение о NP-полных задачах (без доказательства). Теорема Кука (без доказательства).
