1. Высказывания, булевы операции. Формулы, матрицы истинности. Равносильность. Принцип двойственности.
2. Нормальные формы (КНФ и ДНФ). Проблема разрешимости в алгебре высказываний.
3. Логические следствия. Построение формулы по матрице истинности. Совершенные нормальные формы. Вывод всех следствий из данной системы посылок. Релейно-контактные схемы.
4. Исчисление высказываний. Алфавит. Формулы. Аксиомы и правила вывода. Доказуемость. Метатеория.
5. Формальные системы исчисления высказываний. Непротиворечивость и полнота. Независимость аксиом.
6. Высказывательные формулы и предикаты. Булевы операции над предикатами. График предиката. Кванторы, свободные и связанные переменные.
7. Понятие модели. Язык алгебры предикатов данной модели.
8. Язык алгебры предикатов. Выполнимые, общезначимые и ложные формулы. Равносильность формул алгебры предикатов.
9. Предваренная нормальная форма. Проблема разрешимости в алгебре предикатов.
10. Пример формулы, выполнимой на бесконечной модели, но не выполнимой на конечных моделях.
11. Решение проблемы разрешимости для формул, построенных из одноместных предикатов.
12. Разрешающие функции. Теорема Левенгейма-Сколема.
13. Исчисление предикатов. Непротиворечивость и полнота.

---

Университет | Отделение прикладной математики | Рабочие программы