questions

Введение в математическую логику и
теорию алгоритмов
Вопросы к экзамену
Н.К. Верещагин
1. Определение пропозициональных формул. Таблица истинности.
2. Аксиомы и правила вывода исчисления высказываний ИВ. Вывод из
гипотез. Теорема корректности.
3. Лемма о дедукции. Производные правила: разбор случаев, доказательства от противного.
4. Лемма о таблице истинности. Теорема полноты ИВ.
5. Синтаксис и семантика языка первого порядка с примерами. Нормальные интерпретации.
6. Изоморфные и элементарно эквивалентные интерпретации. Теорема
об элементарной эквивалентности эпиморфных интерпретаций.
7. Логические теории и их модели. Семантическое следование. Совместные и семантически полные теории. Аксиоматизация рациональных чисел с отношением порядка (полнота без доказательства), независимость
аксиом.
8. Логические теории и их модели. Семантическое следование. Совместные и семантически полные теории. Аксиоматизация натуральных чисел
с функцией перехода к следующему (полнота без доказательства), независимость аксиом.
9. Аксиомы и правила вывода исчисления предикатов ИП. Вывод из
замкнутых гипотез (= дополнительных аксиом). Теорема корректности
(без аккуратного доказательства общезначимости двух аксиом).
10. Выводы формул ∃x∀yϕ → ∀y∃xϕ, ¬∀xϕ ↔ ∃x¬ϕ, ¬∃xϕ ↔ ∀x¬ϕ.
ϕ↔ψ
ϕ↔ψ
, ∃xϕ↔∃xψ
,
11. Производные правила: правило обобщения, ∀xϕ↔∀xψ
ϕ↔ψ
ϕ↔ψ
,
, . . .. Семантически эквивалентные и выводимо экви(ϕ∧η)↔(ψ∧η) ¬ϕ↔¬ψ
валентные формулы.
12. Лемма о дедукции для ИП.
13. Аксиомы равенства и исчисление предикатов с равенством. Теорема
Геделя о полноте (без доказательства). Теорема Геделя о полноте для
нормальных моделей с доказательством (точнее, с выводом из теоремы
Геделя для ИП без равенства).
1
14. Первые пять аксиом теории множеств ZFC: объемности, пустого множества, регулярности, объединения, неупорядоченной пары. Примеры
моделей этих аксиом. Существование объединения двух множеств.
15. Упорядоченные пары по Куратовскому. Основное свойство упорядоченных пар: они совпадают титтк их первые компоненты совпадают и
вторые компоненты совпадают. Отношения и функции.
16. Аксиома степени. Аксиома выделения. Пересечение и разность множеств (доказательство существования). Декартово произведение и его
существование. Определение функций формулами. Существование области определения функции
17. Аксиома замены и ее использование для определения функций. Аксиома выбора.
18. Индуктивные множества. Натуральные числа. Доказательство аксиом Пеано. Аксиома бесконечности и существование множества натуральных чисел. Принадлежность, как линейный порядок на натуральных числах.
19. Общие теоремы о рекурсивных определениях. Рекурсивные определения сложения, умножения и возведения в степень на натуральных числах.
20. Вполне упорядоченные множества и ординалы. Теорема о минимальном ординале. Теорема о сравнимости ординалов.
21. Трансфинитная индукция. Трансфинитная рекурсия.
22. Лемма Цорна.
23. Теорема Цермело.
24. Равномощные множества, конечные и счетные множества. Кардиналы. Неравномощность разных натуральных чисел друг другу и ω.
25. Теорема Кантора — Бернштейна.
26. Теорема о том, что бесконечный кардинал равномощен своему декартову квадрату.
2