Вопросы к экзамену

1. Язык алгебры высказываний.

   Формулы языка алгебры высказываний.

   Булева интерпретация формул.

   Равносильность формул.

   Свойства отношения равносильности.

   Тавтологии и противоречия.

2. Высказывания.

   Интерпретация формул.

   Понятие логического следствия. Свойства логического следования. Критерии логичности следования.

3. Исчисление высказываний. Аксиомы и правила вывода. Определения доказательства и формальной теоремы. Примеры формальных теорем.

4. Доказательство, что формулы $¬(x_1 \land ¬x_1)$ и $(x_1 \lor ¬x_1)$ - формальные теоремы (леммы 2 и 3 к теореме о полноте.)

5. Понятие вывода и теорема дедукции для исчисления высказываний.

6. Непротиворечивость, полнота и разрешимость исчисления высказываний (леммы 2 и 3 используются без доказательства).

7. Метод резолюций в языке логики высказываний. Теорема о полноте метода резолюций для логики высказываний.

8. Язык логики 1-го порядка. Термы и формулы языка 1-го порядка. Свободные и связанные предметные символы. Интерпретация формул. Понятие модели. Истинность, общезначимость, выполнимость, противоречивость в модели, логическая противоречивость. Равносильность формул, связь с общезначимостью.

9. Законы логики 1-го порядка. Логическое следствие. Критерий логического следования.

10. Предварённая нормальная форма. Сколемова нормальная форма.

11. Подстановка и унификация в логике 1-го порядка.

12. Метод резолюций в логике 1-го порядка.

13. Эрбранов универсум и эрбанов базис множества дизъюнктов. UH-модель, индуцированная некоторой моделью. Критерий невыполнимости множества дизъюнктов.

14. Эрбраново дерево множества дизъюнктов. Теорема Эрбрана.

15. Теорема о полноте метода резолюций.

16. Аксиомы исчисления 1-го порядка. Выводимость. Противоречивость. Формальные теории.

17. Теорема дедукции для логики 1-го порядка.

18. Теорема о полноте исчисления языка 1-го порядка. Неразрешимость исчисления предикатов (формулировка).

19. Теории 1-го порядка с равенством.

20. Формальный натуральный ряд.

21. Формальная арифметика. Теорема Гёделя о неполноте формальной теории, содержащей формальную арифметику (формулировка).