Математическая логика и алгоритмы (2014)

Программа экзамена

Логика предикатов

1. Сигнатура 1-го порядка. Термы, атомарные формулы, формулы. Вхождение

буквы в слово. Свободные и связанные вхождения переменных в формулы.

Замкнутые термы и формулы.

2. Интерпертация сигнатуры (в другой терминологии - модель; структура).

Нормальная интерпретация сигнатуры с равенством. Расширенная сигнатура.

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

3. Гомоморфизм и изоморфизм интерпретаций. "Сохранение" значений:

оцененных термов при гомоморфизме, оцененных формул без равенства при сюръективном гомоморфизме, оцененных формул с равенством при изоморфизме.

4. Композиция гомоморфизмов. Изоморфность интерпретаций.

5. Определимые (выразимые) в данной интерпретации предикаты и отношения; их инвариантность при автоморфизмах.

6. Элементарная теория интерпретации. Элементарная эквивалентность.

Элементарная эквивалентность изоморфных структур.

7. Теории 1-го порядка. Модель теории. Выполнимые теории. Сильно категоричные теории. Теорема о сильной категоричности элементарной теории конечной структуры в конечной сигнатуре (с равенством).

8. Подстановка терма вместо переменной в терм и формулу. Коллизия переменных. Свободная подстановка.

9. Исчисление предикатов 1-го порядка в данной сигнатуре без равенства. Схемы аксиом и правила вывода. Доказательство (вывод) из множества гипотез.

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

10. (Мета)теорема о дедукции для исчисления предикатов. Связь между выводимостью в конечной теории и выводимостью в исчислении предикатов.

11. Производные и допустимые правила в исчислении предикатов. Допустимость производных правил.

12. Примеры допустимых правил и теорем исчисления предикатов: правила Бернайса, монотонности для кванторов, контрапозиции, силлогизма; снятие двойного отрицания, переименование связанной переменной, взаимодействие кванторов с отрицанием.

13. Условие истинности для формулы с несколькими кванторами общности.

Универсальное замыкание формулы. Эквивалентность различных его вариантов.

14. Определение общезначимости для формулы с параметрами. Равносильные (эквивалентные) формулы. Равносильность как отношение эквивалентности на формулах.

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

16. Лемма о сложной подстановке для термов.

17. Лемма о сложной подстановке для формул.

18. Общезначимость кванторных аксиом исчисления предикатов. Теорема корректности для исчисления предикатов.

19. Логическое (семантическое) следование. Теорема корректности для теорий первого порядка. Противоречивые теории. Непротиворечивость выполнимых теорий.

20. Полные теории. Свойства полных теорий.

21. Лемма Линденбаума о расширении непротиворечивой теории до полной.

22. Лемма о свежей константе.

23. Теории Хенкина. Расширение непротиворечивой теории до непротиворечивой теории Хенкина.

24. Теорема о выполнимости непротиворечивой теории без равенства в счетной сигнатуре.

25. Теорема Гёделя о полноте для исчисления предикатов без равенства.

30. Теорема Гёделя о полноте для теорий без равенства: совпадение семантического и синтаксического следования. Теорема Лёвенгейма - Сколема для теорий без равенства в счетной сигнатуре.

31. Исчисление предикатов с равенством.

32. Нормальные интерпретации. Нормальная выполнимость и общезнаичмость.

Нормальная общезначимость аксиом равенства. Нормальное логическое следование. Теорема корректности для теорий 1-го порядка с равенством.

Непротиворечивость нормально выполнимых теорий.

33. Лемма о «нормализации» модели аксиом равенства.

34. Теорема о нормальной выполнимости непротиворечивой теории с равенством в счетной сигнатуре.

35. Теорема Гёделя о полноте для исчисления предикатов с равенством. Теорема Гёделя о полноте для теорий с равенством: совпадение нормального семантического и синтаксического следования. Теорема Лёвенгейма - Сколема для теорий с равенством.

36. Теорема Гёделя - Мальцева о компактности для теорий с равенством. Признак существования бесконечной модели.

37. Счетно категоричные теории. Признак полноты Вота. Примеры счетно категоричных теорий: теория неограниченных плотных линейных порядков; теория бесконечных множеств в сигнатуре равенства.

Формальная арифметика и вычислимость 38. Сигнатура арифметики. Арифметика Робинсона, арифметика Пеано; их непротиворечивость. Истинная арифметика.

39. Существование нестандартных моделей арифметики.

40. Нумералы. Некоторые теоремы о нумералах в арифметике Робинсона.

41. Примитивно рекурсивные и общерекурсивные функции. Примеры примитивно рекурсивных функций.

42. Примитивно рекурсивные предикаты. Ограниченные кванторы и ограниченные -операторы. Построение примитивно рекурсивных функций с помощью ограниченных сумм, ограниченных произведений, «разбором случаев».

43. Представимость числовой функции в арифметической теории (определение). Представимость базисных примитивно рекурсивных функций.

44. Сохранение представимости при подстановке представимых функций в представимую.

45. Сохранение представимости при применении (определенного) -оператора.

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

Восстановление пары по ее номеру.

47. Бета-функция Гёделя и ее свойства. Теорема о свойствах бета-функции в арифметике Робинсона.

48. Сохранение представимости при применении оператора примитивной рекурсии. Представимость общерекурсивных функций.

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

Функции длины (lh), соединения (), проектирования ([x]y ), начального 50. Машины Тьюринга. Определение вычислимой частичной функции Nk N.

Кодирование конфигураций машины натуральными числами.

51. Примитивно рекурсивная функция G(x,n), вычисляющая код конфигурации, полученной из конфигурации с кодом х за время n (для данной машины Тьюринга).

52. Примитивно рекурсивная функция, определяющая значение функции, вычислимой на машине Тьюринга, по заключительной конфигурации машины.

53. Частичная рекурсивность числовых функций, вычислимых по Тьюрингу.

54. Разрешимые множества. Сохранение разрешимости при булевых операциях.

55. Перечислимые множества (эквивалентные определения). Сохранение перечислимости при объединении и пересечении.

56. Теорема Поста (критерий разрешимости множества).

57. Сохранение перечислимости для образов и прообразов относительно вычислимых функций. Сохранение разрешимости для прообразов относительно вычислимых всюду определенных функций.

58. Кодирование машин Тьюринга. Теорема об универсальной машине Тьюринга (без док.). Теорема об универсальной вычислимой функции.

59. Построение перечислимого неразрешимого подмножества N.

60. Арифметические множества. Арифметичность перечислимых множеств натуральных чисел.

61. Разрешимые и перечислимые множества слов. Теорема Поста для множеств слов.

62. Перечислимость множества теорем рекурсивно аксиоматизируемой теории первого порядка (в конечной сигнатуре).

63. Разрешимые теории первого порядка. Разрешимость полной рекурсивно аксиоматизируемой теории (в конечной сигнатуре).

64. Неперечислимость истинной арифметики. 1-я теорема Гёделя о неполноте.

65. Гёделевская нумерация арифметических формул. Теорема Клини Фефермана о неподвижной точке.

66. Существенная неразрешимость арифметики (теорема Тарского - Мостовского Робинсона). Теорема Чёрча о неразрешимости исчисления предикатов.

67. Теорема Тарского "о невыразимости истины". Неарифметичность истинной 68. Формальная доказуемость в арифметической теории. Формальная непротиворечивость. 2-я теорема Гёделя о неполноте.

ЛИТЕРАТУРА

1. Н.К. Верещагин, А.Х. Шень. Лекции по математической логике и теории алгоритмов. Часть 2: Языки и иcчисления. M., МЦНМО, 2000. http://www.mccme.ru 2. В.А. Успенский, Н.К. Верещагин, В.Е. Плиско. Вводный курс математической логики. Издательство МГУ. М., 1991 и 1997. Физматлит, 2002.

3. Справочная книга по математической логике под ред. Дж. Барвайса. Ч. 1.

Теория моделей. М., Наука, 1982.

4. Э. Мендельсон. Введение в математическую логику. М.,1984. 5. А.Н.Колмогоров, А.Г.Драгалин. Математическая логика. Серия "Классический университетский учебник", 2005.

6. В.Н. Крупский, В. Е. Плиско. Математическая логика и теория алгоритмов, Академия, 2013.

7. Дж. Булос, Р. Джеффри. Вычислимость и логика. М., Мир, 1994.

8. Дж. Шенфилд. Математическая логика. М., Наука, 1975.

9. С.К. Клини. Математическая логика. М., Мир, 1973.

10. С.К. Клини. Введение в метаматематику. М., ИЛ, 1957.