УТВЕРЖДАЮ
Проректор по научной работе
«____» ___________ 20__г.
ПРОГРАММА
по дисциплине: Математическая логика и теория алгоритмов
по специальности: 01.01.06 - математическая логика, алгебра и теория чисел
Всего __126_____ учебных часов
Всего __56_____ аудиторных занятий в часах
Всего __70_____ часов на самостоятельную работу аспиранта
Программа составлена на основании паспорта научной специальности 01.01.06 – математическая логика, алгебра и теория чисел и учебного плана подготовки аспирантов
Составитель Программы
Профессор, д. ф.м. н. _________________
Программа рассмотрена на заседании ученого совета математического факультета МГПУ
Председатель ученого совета
______________
(подпись) (Ф. И.О.)
«23» сентября 2009 г.
«СОГЛАСОВАНО»
Начальник управления
аспирантуры и докторантуры _____________ ________________
(подпись) (Ф. И.О.)
Лекционный курс
Порядковый номер лекции | Раздел, тема учебного курса, содержание лекции | Количество часов |
1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. | Понятие алгоритма и его уточнения. Вычислимость по Тьюрингу. Частично рекурсивные функции, рекурсивно перечислимые и рекурсивные множества. Тезис Чёрча. Универсальные вычислимые функции. Существование перечислимого неразрешимого множества. Алгоритмические проблемы. Построение полугруппы с неразрешимой проблемой распознавания равенства. Классы P и NP. Полиномиальная сводимость и NP-полные задачи. Теорема об NP-полноте задачи ВЫПОЛНИМОСТЬ. Логика высказываний. Представимость булевых функций формулами логики высказываний. Логика высказываний. Представимость булевых функций формулами логики высказываний. Конъюнктивные и дизъюнктивные нормальные формы. Исчисление высказываний. Полнота и непротиворечивость. Логика предикатов. Приведение формул логики предикатов к предварённой нормальной форме. Исчисление предикатов. Непротиворечивость. Теорема о дедукции. * Полнота исчисления предикатов. Теорема Мальцева о компактности. *Элементарные теории классов алгебраических систем. Категоричные в данной мощности теории. Теорема о полноте теории, не имеющей конечных моделей и категоричной в бесконечной мощности. Разрешимые теории. Теория плотного линейного порядка. Формальная арифметика. Теорема о представимости вычислимых функций в формальной артифметике (без доказательства). *Теорема Гёделя о неполноте формальной арифметики. Теорема Тарского о невыразимости арифметической истинности в арифметике. *Неразрешимость алгоритмической проблемы выводимости для арифметики и логики предикатов. *Аксиоматическая теория множеств. Порядковые числа, принцип трансфинитной индукции. Аксиома выбора. | 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 |
Практические занятия
Порядковый номер | Содержание практического занятия | Количество часов |
1. 2. 3. 4. 5. 6. 7. 8. | Понятие алгоритма и его уточнения. Вычислимость по Тьюрингу. Частично рекурсивные функции, рекурсивно перечислимые и рекурсивные множества. Тезис Чёрча. Универсальные вычислимые функции. Существование перечислимого неразрешимого множества. Алгоритмические проблемы. Логика высказываний. Представимость булевых функций формулами логики высказываний. Конъюнктивные и дизъюнктивные нормальные формы. Исчисление высказываний. Полнота и непротиворечивость. Логика предикатов. Приведение формул логики предикатов к предварённой нормальной форме. Исчисление предикатов. Непротиворечивость. Теорема о дедукции. Теорема о полноте теории, не имеющей конечных моделей и категоричной в бесконечной мощности. Разрешимые теории. Теория плотного линейного порядка. | 2 2 2 2 2 2 2 2 |
Основная литература
1. Вычислительные машины и труднорешаемые
задачи. М.: Мир, 1982.
2. , Палютин логика. 2-е изд. М.: Наука, 1987.
3. Мальцев и рекурсивные функции. 2-е изд. М.: Наука, 1986.
4. Введение в математическую логику. 3-е изд. М.: Наука, 1984.
5. Новиков математической логики. 2-е изд. М.: Наука, 1973.
6. Ершов разрешимости и конструктивные модели. М.: Наука, 1980.
Содержание и объем самостоятельной работы аспирантов
Разделы и темы Программы самостоятельного изучения дисциплины | Перечень домашних заданий или других вопросов для самостоятельного изучения | Сроки выполнения | Объем часов |
1. Теория моделей
2. Теория доказательств
| 1. Элементарная эквивалентность. 2. Аксоиматизируемые классы. 3. Скулемовские функции. 4. Механизм совместности. 5. Счетная однородность и универсальность. 6. Категоричность. 7. Генцевская система G. 8. Обратимость правил. 9. Вопросы по теме исследования. | Первый год обучения Первый год обучения Первый год обучения Первый год обучения Первый год обучения Первый год обучения Второй год обучения Второй год обучения Второй год обучения | 7 7 7 7 7 7 7 7 14 |
Основная литература
1. , Палютин логика. 2-е изд. М.: Наука, 1987.
2. Введение в математическую логику. 3-е изд. М.: Наука, 1984.
3. Новиков математической логики. 2-е изд. М.: Наука, 1973.
4. Ершов разрешимости и конструктивные модели. М.: Наука, 1980.
