В.Б. Шехтман - Программа и задачи курса ЕНС - Математическая логика и алгоримы (1162046), страница 2
Текст из файла (страница 2)
Замкнутые формулы (предложения).12. Интерпретация сигнатуры. Оцененные термы и формулы. Значение оцененного терма в интерпретации. Значениеоцененной формулы в интерпретации. Нормальные интерпретации.13. Универсальное замыкание. Истинность произвольной формулы в интерпретации. Выполнимость и общезначимость.Теория первого порядка. Модель теории первого порядка. Пример выполнимой формулы, не имеющей конечныхмоделей.14. Допустимая подстановка терма вместо переменной в формулу.15. Классическое исчисление предикатов сигнатуры Ω (PCΩ ).
Доказательство. Теоремы. Вывод из данного множестваформул.16. Теорема дедукции для PCΩ . Примеры теорем исчисления предикатов.17. Леммы о двойной подстановке в термы и формулы. Теорема корректности для PCΩ .18. Теорема корректности и теорема о непротиворечивости для теорий первого порядка.=19. Исчисление предикатов с равенством PC=Ω . Теорема корректности для PCΩ и для теорий первого порядка с равенством. Примеры теорий первого порядка с равенством.20. Элементарная теория данной интерпретации.
Полные теории. Свойства полных теорий. Теории Хенкина. Экзистенциально полные теории.21. Лемма о свежих константах. Лемма о расширении непротиворечивой теории до непротиворечивой теории Хенкина.Лемма Линденбаума.22. Построение счетной модели для полной и экзистенциально полной теории без равенства.23. Теорема Гёделя о полноте для исчисления предикатов без равенства (в двух формах: существование модели длянепротиворечивой теории и доказуемость общезначимых формул). Теорема Лёвенгейма – Сколема для теорий первого порядка без равенства.24.
Теорема о существовании нормальной модели для непротиворечивой теории с равенством.25. Полнота исчисления предикатов с равенством. Теорема Лёвенгейма – Сколема для теорий первого порядка с равенством.26. Теорема компактности для теорий первого порядка. Признак существования бесконечных моделей.27. Изоморфизм интерпретаций. Сохранение значений термов и формул при изоморфизме.28. Изоморфность и элементарная эквивалентность интерпретаций. Существование нестандартных моделей арифметики.29.
Теорема о логическом следовании. Полнота теории как элементарная эквивалентность всех ее моделей.30. Сильная категоричность и счетная категоричность. Полнота сильно категоричных теорий. Полнота счетно категоричных теорий без конечных моделей (признак Вота). Примеры сильной и счетной категоричности.Алгоритмы31. Общее понятие алгоритма.
Система Поста. Вывод в системе Поста.32. Перечислимые и разрешимые множества слов. Сохранение перечислимости для объединений и пересечений. Сохранение разрешимости для булевских операций.33. Вычислимые частичные словарные функции. Разрешимость как вычислимость характеристической функции. Сохранение перечислимости для проекций.34. Кодирование систем Поста.
Гёделев номер системы Поста. Построение универсальной системы Поста.35. Построение перечислимого неразрешимого множества натуральных чисел.36. Преобразование системы Поста в теорию первого порядка.37. Теорема Чёрча о неразрешимости исчисления предикатов.Последняя компиляция: 18 мая 2006 г.Обновления документа — на сайтах http://dmvn.mexmat.net,http://dmvn.mexmat.ru.Об опечатках и неточностях пишите на dmvn@mccme.ru.4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
