Математическая логика и основы теории алгоритмов. Радаев В.Н. - 13 стр.

UptoLike

ВУЗ: 

СГАУ | Самара

Составители: 

Рубрика: 

12 IV. Теория рекурсивных функций
19. Проблема разрешимости для исчисления предикатов. Классы распозна
ваемых формул исчисления предикатов.
20. Исчисление предикатов с равенством. Аксиомы рефлексивности и под
становочности равенства. Однозначность характеризации равенства аксио
мами равенства.
21. Формальные исчисления (формальные системы) первого порядка. Соб
ственные (нелогические) аксиомы. Правила вывода и вывод. Теоремы и
метатеоремы. Понятие о непротиворечивости формальной системы. Разре
шимые и неразрешимые формулы. Дедуктивно полные и неполные фор
мальные системы. Абсолютно полные (полные в смысле Поста) системы.
22. Проблема алгоритмической разрешимости для формальных исчисле
ний. Разрешающий метод для отображений, множеств и формальных ис
числений. Понятие об алгоритме и необходимость уточнения этого поня
тия. Разрешимые и неразрешимые формальные системы. Вычислимость.
Вычислимые функции и предикаты.
23. Модель формальной системы. Модель системы как модель множества
теорем: истинность теорем формальной системы во всякой ее модели. До
казательство непротиворечивости формальной системы с помощью модели
множества ее теорем.
24. Изоморфизм моделей. Категорические формальные системы.
25. Зависимость и независимость аксиом формальной системы. Доказа
тельство независимости с помощью моделей.
26. Теория групп как формальное исчисление. Собственные аксиомы тео
рии групп. Доказательство непротиворечивости теории групп.
27. Расширения формальной системы первого порядка. Существование
непротиворечивого полного расширения непротиворечивой формальной си
стемы первого порядка. Алгоритмическая неразрешимость проблемы по
строения непротиворечивого полного расширения.
28. Существование модели со счетной индивидной областью для непротиво
речивой формальной системы первого порядка (теорема G). Алгоритмиче
ская неразрешимость проблемы построения модели со счетной индивидной
областью. Теорема Сколема–Левенгейма. Теорема об альтернативе.
29. Семантическая и синтаксическая полнота исчисления предикатов. Тео
рема Геделя о полноте исчисления предикатов.
IV. Теория рекурсивных функций
1. Теоретико-числовая система Z (формальная арифметика). Аксиоматика
и правила вывода. Цифры. Полная и возвратная математическая индук
ция. Принцип наименьшего числа.
2. Стандартная модель N теоретико-числовой системы Z.
Ю.Н. Радаев

Страницы