Программа курса
«МАТЕМАТИЧЕСКАЯ ЛОГИКА»
для студентов 1-2 курсов ММФ НГУ
Программу составил д.ф.-м.н., доцент С.В.Судоплатов
Семестр
I. Исчисления высказываний.
1. Формулы ИВ, лемма о начале формулы ИВ. (Ершов, Палютин [1, § 2], [2, § 1.2])
2. Теоремы о подформулах формул ИВ. ([1, § 2], [2, § 1.2])
3. Аксиомы и правила вывода ИВ. ([1, § 3], [2, § 1.3])
4. Доказательства и теоремы ИВ, равносильность линейного доказательства и доказательства в виде дерева. ([1, § 3], [2, § 1.3])
5. Допустимые правила вывода ИВ. ([1, § 3], [2, § 1.3])
6. Теорема о подстановке. ([1, § 4], [2, § 1.4])
7. Эквивалентность формул, основные эквивалентности ИВ. ([1, § 4], [2, §1.4])
8. Теорема о замене. ([1, § 4], [2, § 1.4])
9. Нормальные формы. ([1, § 5], [2, § 1.5])
10. Теорема о существовании д.н.ф. ([1, § 5], [2, § 1.5])
11. Теорема о существовании к.н.ф. ([1, § 5], [2, § 1.5])
12. Теорема о существовании совершенной д.н.ф. ([1, § 5], [2, § 1.5])
13. Теорема о существовании совершенной к.н.ф. ([1, § 5], [2, § 1.5])
14. Интерпретация формул ИВ, теорема о непротиворечивости ИВ. ([1, § 6], [2, § 1.6])
15. Главная интерпретация формул ИВ, теорема о тождественной истинности доказуемых секвенций. ([1, § 6], [2, § 1.6])
16. Теорема о функциональной полноте ИВ. ([1, § 6], [2, § 1.6])
17. Теорема о полноте ИВ. ([1, § 7], [2, § 1.7])
18. Теорема о независимости ИВ. ([1, § 7], [2, § 1.7])
19. Исчисление высказываний гильбертовского типа (
).([1, § 8], [2, § 1.8])
20. Линейное доказательство в , вывод в из множества гипотез. ([1, § 8], [2, § 1.8])
21. Теорема о дедукции в . ([1, § 8], [2, § 1.8])
22. Теорема о равносильности ИВ и . ([1, § 8], [2, § 1.8])
II. Элементы теории множеств.
1. Аксиомы объемности, пустого множества и пары. ([1, § 14], [2, § 2.6])
2. Аксиомы объединения, бесконечности и степени. ([1, § 14], [2, § 2.6])
3. Аксиома регулярности и ее следствия. ([1, § 14], [2, § 2.6])
4. Аксиомы подстановки и выбора. ([1, § 14], [2, § 2.6])
5. Упорядоченные наборы (определение и основное свойство). ([1, § 10], [2, § 2.1])
6. Отношения на множествах, композиция и инверсия бинарных отношений, их свойства. ([1, § 10], [2, § 2.1])
7. Типы бинарных отношений. ([1, § 10], [2, § 2.1])
8. Отношения эквивалентности и разбиения, связь между ними. ([1, § 10], [2, § 2.1])
9. Функции, отображения, их типы и свойства. ([1, § 10], [2, § 2.1])
10. Частично упорядоченные множества, особые элементы (максимальные, минимальные и т.п.) и их свойства. ([1, § 11], [2, § 2.2])
11. Решетки, булевы решетки, булевы алгебры, связь булевых решеток с основными свойствами теоретико-множественных операций. ([1, § 11], [2, § 2.2])
12. Фундированные частично упорядоченные множества, принцип трансфинитной индукции. ([1, § 11], [2, § 2.2])
13. Начальные отрезки, определение и свойства. ([2, § 2.2])
14. Принцип максимума. ([1, § 11], [2, § 2.2])
15. Линейно и вполне упорядоченные множества, принцип полного упорядочения. ([1, § 11], [2, § 2.2])
16. Характеризация вполне упорядоченных множеств. ([2, § 2.2])
17. Принцип кардинального упорядочения. ([2, § 2.2])
18. Теорема об изоморфизме вполне упорядоченных множеств. ([2, § 2.2])
19. Сравнение множеств по мощности, Теорема Кантора-Бернштейна. ([1, § 13], [2, § 2.4])
20. Теорема Кантора. ([1, § 13], [2, § 2.4])
21. Теорема о сравнимости множеств по мощности. ([1, § 13], [2, § 2.4])
22. Ординалы и их свойства. ([1, § 13], [2, § 2.5])
23. Теорема о представлении вполне упорядоченных множеств. ([1, § 13], [2, § 2.5])
24. Кардиналы и мощность множества. ([1, § 13], [2, § 2.5])
25. Натуральные числа и счетные множества. ([1, § 13], [2, § 2.5])
26. Конечные и бесконечные множества, их свойства. ([1, § 13], [2, § 2.5])
27. Теорема о квадрате бесконечного множества. ([1, § 13], [2, § 2.5])
28. Мощность множества слов данного алфавита. ([1, § 13], [2, § 2.5])
29. Теорема об утверждениях, эквивалентных аксиоме выбора. ([1, § 14], [2, § 2.6])
30. Доказательство теоремы Кантора-Бернштейна, не зависящее от аксиомы выбора. ([2, § 2.6])
Семестр
