Математическая логика и теория алгоритмов

Высказывание, высказывательная форма, предикат. Свободные и связанные переменные высказывательной формы.
Операции над высказывательными формами и предикатами.
Формула алгебры высказываний, представление булевой функции формулой алгебры высказываний.
Тавтологии. Выполнимые и опровержимые формулы алгебры высказываний. Примеры.
Формула над классом функций, представление булевой функции в виде КНФ, СКНФ. Примеры.
Формула над классом функций, представление булевой функции в виде ДНФ, СДНФ. Примеры.
Представление булевых функций многочленами Жегалкина. Примеры.
Ряд Фурье булевой функции. Свойства коэффициентов Фурье. Спектральное представление булевой функции.
Быстрое преобразование Фурье (БПФ) булевой функции.
Минимизация ДНФ. Сокращенные ДНФ, тупиковые ДНФ. Метод Мак-Каски.
Метод Квайна минимизации ДНФ.
Замыкание системы булевых функций. Проблема функциональной полноты. Критерий Поста.
Предполные классы булевых функций (классы Поста). Замкнутость предполных классов. Оценки мощностей предполных классов.
Полиномиальные преобразования и полиномиальные функции. Полиномиальная полнота (представимость всякой функции k-значной логики полиномом).
Критерий полиномиальной полноты кольца вычетов.
Приведенный многочлен. Представимость всякой функции над конечным полем приведенным многочленом.
Терм. Атомарная (элементарная) формула. Формула исчисления предикатов. Ранг и длина формулы исчисления предикатов.
Интерпретация формулы исчисления предикатов. Значение формулы исчисления предикатов в точке.
Отношение равносильности на множестве формул исчисления предикатов. Равносильность всякой формулы исчисления предикатов своей приведенной нормальной форме.
Равносильность всякой формулы исчисления предикатов своей предваренной нормальной форме.
Вывод в исчислении предикатов. Аксиомы и правила вывода.
Выводимая формула исчисления предикатов. Теорема Геделя о полноте исчисления предикатов (без док-ва).
Машина Тьюринга как формализация понятия алгоритма.
Операции над детерминированными машинами Тьюринга. Тезис Тьюринга.
Емкостная и временная сложность алгоритмов, соотношение между этими сложностями.
Классификация алгоритмов на полиномиальные и экспоненциальные. Примеры.
Задачи распознавания. Недетерминированная машина Тьюринга. Класс задач NP.
Полиномиальная сводимость. NP-полные и NP-трудные задачи.
Теорема Кука о NP-полноте проверки выполнимости КНФ (без док-ва). Примеры других NP-полных задач.
Гипотеза PNP и ее значение в теории сложности.