Предисловие

Математическая логика
Множества с отношениями и операциями
Множества и операции над ними
Отображения множеств
Отношения на множестве Отношения эквивалентности и порядка
Множества с операциями
Аксиоматическое построение системынатуральных чисел
Мощность множества Конечные и бесконечные множества

Алгебра высказываний
Основные логические операции и их свойства
Формулы алгебры высказываний
Эквивалентные формулы
Приведенные формулы и нормальные формы
Выполнимые и тождественно истинные формулы
Сокращенные, тупиковые и минимальные ДНФ
Алгоритм нахождения тупиковых ДНФ по сокращенной ДНФ

Исчисление высказываний
Общее понятие о логическом исчислении
Язык, аксиомы и правила вывода исчисления высказываний
Доказуемые формулы исчисления высказываний
Вспомогательные правила вывода
Полнота и непротиворечивость исчисления высказываний

Алгебра предикатов
Предикатыи операции над ними
Формулы алгебры предикатов
Эквивалентность формул Основные соотношения эквивалентности
Приведенные и предваренные формулы

Исчисление предикатов
Язык, аксиомы и правила вывода исчисления предикатов
Выводимость и доказуемость формул
Семантика исчисления предикатов
Понятие о теории моделей
Проблема разрешимости в логике предикатов

Дискретные функции
Дискретные функции и способы их задания
Способы задания булевых функций
Полные системы и замкнутые классы булевых функций
Функции k-значной логики и способы их задания Полные системы
Критерии полноты систем функций k-значной логики
Полиномиальное представление функций k-значной логики

Представление дискретных функций в базисах функциональных пространств
Базисы линейных функциональных пространств Базис характеров
Преобразование Фурье Коэффициенты Фурье и Уолша–Адамара
Матричный подход к представлению булевых функций

Классификация дискретных функций с помощью групп преобразований
Эквивалентность функций Группы инерции
Функции, инвариантные относительно группы
Функции c тривиальной группой инерции в аффинной группе
Перечисление G-типов Лемма Бернсайда
Инварианты Нахождение групп инерции и проверка эквивалентности

Вероятностные и комбинаторные свойства и параметры дискретных функций
Вероятностная функция булевой функции
Линейные приближения (аппроксимации) булевы хфункций
Коэффициент аддитивности дискретных функций

Некоторые специальные классы дискретных функций
Корреляционно-иммунные функции
k-устойчивы ефункции
Бент-функции
Бент-отображения

Декомпозиция булевых функций
Простая декомпозиция
Разложимые функции
Сложные декомпозиции
Группы инерции суперпозиции булевых функций в группах

Теория алгоритмов
Элементы теории алгоритмов
Нормальные алгоритмы
Принцип нормализации алгоритмов
Машины Тьюринга
Нумерация слов и арифметизация алгоритмов
Рекурсивные функции
Примеры алгоритмически неразрешимых проблем

Сложность алгоритмов и вычислений
Сложность нормальных алгоритмов, вычисляющих булевы функции
Сложности вычислений на машинах Тьюринга
Классификации задач по сложности их решения на машинах Тьюринга
О сложностной классификации систем булевых уравнений
Асимптотические оценки сложности алгоритмов
Дискретные преобразования Фурье
Понятие о вероятностных алгоритмах

Приложение
Методические рекомендации по организации изучения математической логики, теории алгоритмов, теории дискретны хфункций

Литература