"Математическая логика" для студентов, обучающихся по направлению "Информационные технологии".
Весенний семестр 2008/09 учебного года

Лектор Герасимов Александр Сергеевич

Экзаменационные вопросы

Язык логики высказываний и его семантика

1. Слова, вхождения, формальные языки: определения и примеры.
2. Язык логики высказываний.
3. Интерпретация языка логики высказываний, истинностное значение формулы.
4. Пропозициональные тавтологии, примеры.
5. Логика высказываний: логическое следствие, теорема о логическом следствии, логически эквивалентные формулы.
6. Теорема о подстановке пропозициональных формул в пропозициональную тавтологию.
7. Теорема об эквивалентной замене (семантический вариант) для логики высказываний.
8. Теорема о выражении булевой функции формулами, находящимися в конъюнктивной и дизъюнктивной нормальных формах.
9. Теорема о выражении булевой функции пропозициональной формулой, в которую из логических связок входят только две или одна.
10. Выражение булевой функции полиномом Жегалкина.

    Секвенциальное исчисление высказываний генценовского типа

11. Систематический поиск контрпримера для пропозициональной формулы.
12. Формулировка секвенциального исчисления высказываний генценовского типа.
13. Пример вывода в секвенциальном исчислении высказываний. Дерево поиска вывода и дерево вывода.
14. Теоремы о корректности и полноте секвенциального исчисления высказываний.
15. Некоторые правила, допустимые в секвенциальном исчислении высказываний.

    Язык логики предикатов и его семантика

16. Определение языка первого порядка.
17. Основные определения, касающиеся вхождений предметных переменных в предикатные формулы.
18. Интерпретация языка первого порядка, истинностное значение формулы.
19. Примеры языков первого порядка и их интерпретаций.
20. Выражение предиката формулой, примеры.
21. Свободные подстановки.
22. Конгруэнтные формулы. Лемма о чистоте переменных.
23. Переименование связанных переменных, правильные подстановки.
24. Общезначимые предикатные формулы, логическое следствие, теорема о логическом следствии, логически эквивалентные формулы.
25. Утверждения о логической эквивалентности некоторых предикатных формул, в том числе теорема об эквивалентной замене (семантический вариант).
26. Теорема о предварённой нормальной форме.

    Секвенциальное исчисление предикатов генценовского типа

27. Систематический поиск контрпримера для формулы с кванторами.
28. Формулировка секвенциального исчисления предикатов генценовского типа. Пример вывода в этом исчислении.
29. Теоремы о корректности и непротиворечивости секвенциального исчисления предикатов.
30. Теорема о полноте секвенциального исчисления предикатов (без доказательства). Допустимость правила сечения.
31. Теорема об обратимости пропозициональных правил вывода секвенциального исчисления предикатов.
32. Допустимость пропозициональных правил, формализующих некоторые естественные способы математических рассуждений.
33. Допустимость кванторных правил, формализующих некоторые естественные способы математических рассуждений.
34. Допустимость правил добавления.

    Формальные аксиоматические теории

35. Формальные аксиоматические теории: основные определения.
36. Теорема об истинности теорем теории в её моделях.
37. Критерий непротиворечивости теории.
38. Теорема о непротиворечивости теории, имеющей модель. Теорема о существовании модели (без доказательства). Теорема Лёвенгейма-Скулема. Теорема о компактности.
39. Теории с равенством: определения и примеры.
40. Теорема о существовании нормальной модели.
41. Теорема о компактности для нормальных моделей. Теорема о полноте исчисления предикатов для теорий с равенством.
42. Аксиомы элементарной арифметики.
43. Нестандартная модель арифметики.
44. Пример вывода и пример содержательного доказательства в элементарной арифметике.
45. Доказательство коммутативности сложения в элементарной арифметике.
46. Наивная теория множеств. Парадокс Рассела.
47. Аксиомы теории множеств Цермело-Френкеля.
48. Теория множеств Цермело-Френкеля: упорядоченная пара и теорема о её основном свойстве.
49. Отношения и функции в теории множеств Цермело-Френкеля. Аксиома выбора.
50. Натуральные и целые числа в теории множеств Цермело-Френкеля.
51. Формализация математических рассуждений в теории множеств Цермело-Френкеля с аксиомой выбора.

    Логика и вычислимость

52. Постановка проблемы эквивалентности для ассоциативных исчислений и проблемы равенства для полугрупп.
53. Теорема о существовании ассоциативного исчисления с неразрешимой проблемой эквивалентности.
54. Теоремы о неразрешимости проблемы общезначимости и проблемы выводимости для исчисления предикатов.
55. Перечислимость множества теорем рекурсивно аксиоматизируемой теории.
56. Эффективно неотделимые множества.
57. Теорема Гёделя о неполноте арифметики в форме Россера.
58. Теорема о неразрешимости арифметики.
59. Вторая теорема Гёделя.