Главная страница
Навигация по странице:

  • I. Исчисления высказываний.

  • II. Элементы теории множеств.

  • 3 семестр I. Язык и логика предикатов.

  • II. Исчисления предикатов.

  • III. Аксиоматизируемые классы. Теория арифметики.

  • IV. Разрешимые и неразрешимые теории. Теорема Гёделя о неполноте.

  • Программа практических занятий по математической логике 2 семестр

    		•

    Программа курса математическая логика


    Скачать 92 Kb.
    НазваниеПрограмма курса математическая логика
    Дата16.12.2018
    Размер92 Kb.
    Формат файлаdoc
    Имя файлаvoprML_NSU.doc
    ТипПрограмма курса
    #60505



    Программа курса

    «МАТЕМАТИЧЕСКАЯ ЛОГИКА»

    для студентов 1-2 курсов ММФ НГУ
    Программу составил д.ф.-м.н., доцент С.В.Судоплатов


    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])
    3 семестр
    I. Язык и логика предикатов.
    1. Понятие сигнатуры (языка) и алгебраической системы (структуры) данной сигнатуры. ([1, § 15], [2, § 3.1])

    2. Морфизмы алгебраических систем. ([1, § 15], [2, § 3.1])

    3. Подсистемы, подсистемы, порожденные множествами; существование и единственность наименьшей подсистемы, содержащей данное множество. ([1, § 15], [2, § 3.1])

    4. Направленное множество алгебраических систем, существование и единственность системы, содержащей все системы направленного множества. ([1, § 15], [2, § 3.1])

    5. Обогащения и обеднения систем, примеры. ([1, § 15], [2, § 3.1])

    6. Изоморфизм счетных плотных линейных порядков с одинаковыми концами. ([1, § 15], [2, § 3.1])

    7. Термы и формулы данной сигнатуры. ([1, § 16], [2, § 3.2])

    8. Свободные и связанные вхождения переменных. ([1, § 16], [2, § 3.2])

    9. Значение терма в системе, нахождение наименьшей подсистемы, содержащей данное множество. ([1, § 16], [2, § 3.2])

    10. Истинность формулы в системе. ([1, § 16], [2, § 3.2])

    11. Сохранение истинности формулы при изоморфизме. ([1, § 16], [2, § 3.2])

    12. Фильтры булевой алгебры; центрированные множества, их расширения до ультрафильтров. ([1, § 12], [2, § 2.3])

    13. Критерий того, что фильтр является ультрафильтром. ([1, § 12], [2, § 2.3])

    14. Декартовы и фильтрованные произведения алгебраических систем. ([1, § 17], [2, § 3.3])

    15. Теорема Лося. ([1, § 17], [2, § 3.3])

    16. Локальная теорема Мальцева. ([1, § 17], [2, § 3.3])
    II. Исчисления предикатов.
    1. Исчисление . ([1, § 18], [2, § 4.1])

    2. Тавтологии, сохранение эквивалентностей ИВ в . ([1, § 18], [2, § 4.1])

    3. Доказуемость секвенции . ([1, § 18], [2, § 4.1])

    4. Доказуемость секвенции . ([1, § 18], [2, § 4.1])

    5. Допустимость в правила подстановки в секвенцию термов вместо переменных. ([1, § 18], [2, § 4.1])

    6. Теорема о непротиворечивости . ([1, § 18], [2, § 4.1])

    7. Доказуемость секвенций, выражающих симметричность и транзитивность равенства. ([1, § 18], [2, § 4.1])

    8. Доказуемость секвенций, выражающих подстановку равных термов в терм и в формулу. ([1, § 18], [2, § 4.1])

    9. Основные эквивалентности . ([1, § 19], [2, § 4.2])

    10. Теорема о замене в . ([1, § 19], [2, § 4.2])

    11. Пренексная и приведенная нормальные формы. ([1, § 20], [2, § 4.3])

    12. Теорема о существовании модели: формулировка и построение максимального непротиворечивого множества формул. ([1, § 21], [2, § 4.4])

    13. Теорема о существовании модели: формулировка и построение константной модели. ([1, § 21], [2, § 4.4])

    14. Теорема Гёделя о полноте. ([1, § 21], [2, § 4.4])

    15. Теорема о существовании моделей как угодно большой мощности. ([1, § 21], [2, § 4.4])

    16. Исчисление предикатов гильбертовского типа. ([1, § 22], [2, § 4.5])

    17. Теорема о дедукции для исчисления предикатов гильбертовского типа. ([1, § 22], [2, § 4.5])

    18. Теорема об эквивалентности и исчисления предикатов гильбертовского типа. ([1, § 22], [2, § 4.5])
    III. Аксиоматизируемые классы. Теория арифметики.
    1. Аксиоматизируемые классы, критерий аксиоматизируемости. ([1, § 25], [2, § 5.2])

    2. Сохранение аксиоматизируемости при взятии объединения и пересечения. ([1, § 25], [2, § 5.2])

    3. Связь конечной аксиоматизируемости с сохранением аксиоматизируемости при взятии дополнения. ([1, § 25], [2, § 5.2])

    4. Система аксиом арифметики Пеано. ([1, § 38], [2, § 7.5])

    5. Выводимость атомарных формул и их отрицаний в арифметике Пеано. ([1, § 38], [2, § 7.5])
    IV. Разрешимые и неразрешимые теории. Теорема Гёделя о неполноте.
    1. Гёделевская нумерация. ([1, § 38], [2, § 7.3])

    2. Теорема о рекурсивной перечислимости множества гёделевских номеров доказуемых формул. ([1, § 38], [2, § 7.3])

    3. Теорема о представимости рекурсивных функций в арифметике Пеано. ([1, § 38])

    4. Теорема о неразрешимости арифметики. ([1, § 38], [2, § 7.5])

    5. Теорема Гёделя о неполноте. ([1, § 38], [2, § 7.5])

    6. Теорема Чёрча о неразрешимости . ([1, § 38], [2, § 7.5])

    7. Разрешимость полной рекурсивно аксиоматизируемой теории. ([1, § 38])

    8. Элементарные подсистемы, критерий элементарности подсистем. ([1, § 24], [2, § 5.1])

    9. Элементарная диаграмма и ее свойство. ([1, § 24], [2, § 5.1])

    10. Теоремы Лёвенгейма-Скулема. ([1, § 24], [2, § 5.1])

    11. Теорема о полноте категоричной теории. ([1, § 29], [2, § 5.6])

    12. Разрешимость теорий одноместных предикатов, поля комплексных чисел, плотных линейных порядков, поля вещественных чисел, векторных пространств. ([1, § 39], [2, § 8.1-8.3])
    Программа практических занятий

    по математической логике
    2 семестр
    1. Понятие формулы. Таблицы истинности. Семантическая эквивалентность (2 часа). Лавров, Максимова (ЛМ), Часть 2, § 1, N 1-3, 7-10, 19-20.

    2. Вывод в исчислении высказываний. Допустимые правила. Вывод основных эквивалентностей (6 часов). ЛМ, Часть 2, § 3, N 1-9, 14.

    3. Приведение к нормальным формам (2 часа). ЛМ, Часть 2, § 1, N 24.

    4. Контрольная работа (2 часа).

    5. Приведение к совершенным нормальным формам (2 часа). ЛМ, Часть 2, § 1, N 29, 30, 32, 33, 35-40.

    6. Функционально полные системы связок (2 часа). ЛМ, Часть 2, § 2, N 2-6, 8-13.

    7. Исчисление высказываний гильбертовского типа (4 часа). ЛМ, Часть 2, § 3, N 17-40.

    8. Контрольная работа (2 часа).

    9. Множества и операции над ними. (2 часа). ЛМ, Часть 1, § 1.

    10. Декартово произведение. Отношения и функции (2 часа). ЛМ, Часть 1, § 2, N 1-27.

    11. Специальные бинарные отношения (4 часа). ЛМ, Часть 1, § 3, N 6-11, 26-31, 34-42; § 5, N 30-43.

    12. Мощность множества (4 часа). ЛМ, Часть 2, § 4, N 7-36; § 6, N 8, 9.

    3 семестр
    1. Понятие терма и формулы данной сигнатуры. Запись свойств на языке первого порядка (4 часа). ЛМ, Часть 2, § 4.

    2. Истинность и выполнимость. Приведение к предваренной нормальной форме (4 часа). ЛМ, Часть 2, § 5, N 7-19, 30-37, 42.

    3. Выводы в исчислении предикатов (4 часа). ЛМ, Часть 2, § 6, N 1-10, 14-30, § 7, N 1.

    4. Локальная теорема Мальцева (4 часа). ЛМ, Часть 2, § 7, N 12-17; § 9, N 1-3, 5, 7, 8.

    5. Фильтрованные произведения (4 часа). ЛМ, Часть 2, § 8, N 1-16; 29, 30, 44-51.

    6. Контрольная работа (2 часа).

    7. Примитивно рекурсивные и частично-рекурсивные функции (4 часа). ЛМ, Часть 3, § 1, N 1-32.

    8. Машины Тьюринга. Функции, вычислимые на машинах Тьюринга (2 часа). ЛМ, Часть 3, § 2, N 1-10.

    9. Рекурсивные и рекурсивно перечислимые множества. (2 часа). ЛМ, Часть 3, § 3, N 1-29.

    10. Рекурсивно аксиоматизируемые, разрешимые и неразрешимые теории (2 часа). ЛМ, Часть 2, § 7, N 13-17.

    11. Формальная арифметика. Представимость рекурсивных функций (2 часа). ЛМ, Часть 2, § 7, N 18-37.

    ОСНОВНАЯ ЛИТЕРАТУРА
    1. Ершов Ю.Л., Палютин Е.А. Математическая логика. – М.: Наука, 1979, 1987; СПб.: Лань, 2004, 2005, 2006.

    2. Ершов Ю.Л., Палютин Е.А. Математическая логика. – М.: ФИЗМАТЛИТ, 2011.

    3. Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов. – М.: Наука, 1975, 1984, или М.: ФИЗМАТЛИТ, 1995, 2001, 2004, 2006.
    ДОПОЛНИТЕЛЬНАЯ ЛИТЕРАТУРА
    1. Гончаров С.С. Счетные булевы алгебры и разрешимость. – Новосибирск: Научная книга, 1996.

    2. Гончаров С.С., Ершов Ю.Л. Конструктивные модели. – Новосибирск: Научная книга, 1999.

    3. Ершов Ю.Л. Проблемы разрешимости и конструктивные модели. – М.: Наука, 1980.

    4. Ершов Ю.Л. Определимость и вычислимость. – Новосибирск: НИИ МИОО

    НГУ, Научная книга, 1996 или М.: Экономика, 2000.

    5. Кейслер Г., Чэн Ч.Ч. Теория моделей. – М.: Мир, 1977.

    6. Куратовский К., Мостовский А. Теория множеств. – М.: Мир, 1970.

    7. Мальцев А.И. Алгоритмы и рекурсивные функции. – М.: Наука, 1965, 1986.

    8. Мальцев А.И. Алгебраические системы. – М.: Наука, 1970.

    9. Мендельсон Э. Введение в математическую логику. – М.: Наука, 1971, 1984.

    10. Непейвода Н.Н. Прикладная логика. – Новосибирск: Изд-во НГУ, 2000.

    11. Новиков П.С. Элементы математической логики. – М.: Наука, 1973.

    12. Роджерс Х. Теория рекурсивных функций и вычислимость. – М.: Мир, 1972.

    13. Соар Р. Вычислимо перечислимые множества и степени. – Казань: Казанское мат. общество, 2000.

    14. Справочная книга по математической логике / Под ред. Дж. Барвайса. – М.: Наука, 1982. Т. 1–4.

    15. Судоплатов С.В., Овчинникова Е.В. Дискретная математика. – М.: Юрайт, 2016.

    16. Судоплатов С.В., Овчинникова Е.В. Математическая логика и теория алгоритмов. – М.: Юрайт, 2016.

    17. Чень Ч., Ли Р. Математическая логика и автоматическое доказательство теорем. – М.: Наука, 1983.

    написать администратору сайта