Программа курса математическая логика для студентов 1-2 курсов



Скачать 59.92 Kb.
страница2/2
Дата30.07.2018
Размер59.92 Kb.
ТипПрограмма курса
1   2
Исчисления предикатов

1. Теорема о корректности для секвенциального исчисления предикатов с

равенством (СИПР)


  1. Теорема о существовании модели для СИПР

  2. Теорема о полноте СИПР

4. Теорема Левенгейма-Скулема

5. Локальная теорема Мальцева

6. Теорема о расширении

7. Теорема Эрбрана

8. Теорема о дедукции в гильбертовском исчислении высказываний

9. Вывод в гильбертовском исчислении предикатов. Примеры выводов

10. Вывод в гильбертовском исчислении предикатов. Теорема о подстановке вместо пропозициональной переменной

11. Вывод из гипотез в гильбертовском исчислении предикатов. Свойства выводов

12. Слабая теорема о корректности для гильбертовских исчислений ИП и ИПР

13. Теорема о дедукции в гильбертовском исчислении предикатов

14. Теорема о погружении ИПР в ИП

15. Эквивалентность секвенциального и гильбертовского исчислений предикатов

16. Сильная теорема о полноте для ИПР

17. Аксиоматизируемые классы. Критерий конечной аксиоматизируемости.


2. Алгоритмы и рекурсивные функции


  1. Примитивно рекурсивные функции. Определение, примеры

  2. Операторы суммирования и произведения. Ограниченный mu-оператор

  3. Теорема о возвратной рекурсии

  4. Канторовская нумерация пар и n-ок чисел

5. Оператор минимизации для частичных числовых функции. Частично рекурсивные и общерекурсивные функции

6. Функция Геделя и ее свойства

7. Определение машины Тьюринга. Примеры

8. Вычислимость и правильная вычислимость на машинах Тьюринга. Примеры вычислимых функций

9. Правильная вычислимость частично рекурсивных функций

10. Нумерация машин Тьюринга

11. Частичная рекурсивность вычислимых функций

12. Теорема о нормальной форме Клини

13. Существование универсальной частично рекурсивной функции

14. Существование частично рекурсивной функции, не имеющей рекурсивного доопределения

15. Рекурсивные и рекурсивно перечислимые множества. Замкнутость относительно теоретико-множественных операций

16. Теорема о проекции рекурсивно перечислимого множества

17. Теорема об области определения частично рекурсивной функции и ее следствия

18. Теорема Поста о рекурсивных множествах

19. Существование нерекурсивного, рекурсивно перечислимого множества

20. Рекурсивность множества значений монотонной общерекурсивной функции

21. Теорема о графике

22. Основная теорема о рекурсивно перечислимых множествах

23. Теорема о составном определении частично рекурсивной функции

24. Свойства m-сводимости; существование m-универсального множества


3. Теорема Геделя о неполноте арифметики
1. Геделевская нумерация языка арифметики. Рекурсивность основных множеств и функций

2. Рекурсивная перечислимость множества теорем ИПР

3. Теория Ао формальной арифметики. Лемма о стандартной модели

4. Существование нестандартной модели теории Ао

5. Рекурсивная перечислимость множества теорем теории Ао

6. Теорема о неразрешимости теории Ао

7. Теорема Черча о неразрешимости ИПР

8. Аксиоматизируемые, полные и разрешимые теории



9. Теорема Геделя о неполноте арифметики
ЛИТЕРАТУРА


  1. Ю.Л.Ершов, Е.А.Палютин. Математическая логика.- М.: Наука, 1979 или позже.

  2. И.А.Лавров, Л.Л.Максимова. Задачи по теории множеств, математической логике и теории алгоритмов.- М.: Наука, 1975 или позже.

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

профессор Л.Л.Максимова


Поделитесь с Вашими друзьями:
1   2


База данных защищена авторским правом ©znate.ru 2019
обратиться к администрации

    Главная страница