[ Московский государственный университет
Механико-математический факультет
“Введение в математическую логику”
1-й курс, 2-й семестр
Программа
Введение
Предмет математической логики. Вопросы оснований математики. Аксиоматическое построение элементарной геометрии, роль аксиомы о параллельных. Парадоксы теории множеств, семантические парадоксы. Формальный аксиоматический метод Гильберта, программа Гильберта. Роль теорем Гёделя о неполноте.
Логика высказываний Высказывания и логические связки. Формулы логики высказываний, понятие подформулы. Истинностные таблицы для логических связок и формул.
Выполнимые формулы, тавтологии, тождественно ложные формулы. Алгоритм распознавания выполнимости. Семантическое следование в логике высказываний. Равносильность формул логики высказываний, связь с тождественной истинностью; важнейшие равносильности. Операции подстановки и замены подформулы на равносильную.
Связь между формулами логики высказываний от n переменных и булевыми функциями. Теорема о функциональной полноте.
Дизъюнктивные и конъюнктивные нормальные формы. Приведение формул логики высказываний к совершенной дизъюнктивной (конъюнктивной) нормальной форме.
Исчисление высказываний Аксиомы и правила вывода исчисления высказываний. Понятие вывода и выводимой формулы; примеры. Корректность исчисления высказываний.
Выводимость из гипотез, её простейшие свойства. Теорема о дедукции для исчисления высказываний.
Непротиворечивые и максимальные непротиворечивые множества формул в исчислении высказываний. Теорема Линденбаума.
Теорема о полноте исчисления высказываний. Свойства сильной полноты и компактности.
Логика предикатов Предикаты. Переменные и их области изменения. Кванторы. Языки первого порядка: термы, формулы, подформулы. Примеры языков первого порядка. Свободные и связанные вхождения переменных. Замкнутые формулы.
Подстановка терма вместо переменной.
Модели (алгебраические системы, интерпретации) для данного языка первого порядка. Истинность замкнутой формулы в данной модели. Предикаты, выразимые в данной модели.
Общезначимые и выполнимые формулы языка первого порядка, примеры.
Семантическое следование в логике первого порядка, его связь с понятиями выполнимости и общезначимости. Равносильность формул языка первого порядка, важнейшие равносильности. Переименование связанных переменных.
Операции подстановки и замены подформулы на равносильную. Приведение формулы к предварённой нормальной форме.
Понятие изоморфизма моделей. Сохранение значения формулы при изоморфизме. Доказательство невыразимости с помощью изоморфизма моделей, примеры.
Теория первого порядка, её аксиомы и теоремы. Модель данной теории.
Понятие выполнимой теории. Примеры теорий: теория строгих частичных порядков, теория отношения эквивалентности, теория простых графов.
Теории первого порядка с равенством. Нормальные модели. Теорема о существовании нормальной модели у выполнимой теории с равенством. Примеры теорий с равенством: теория групп, формальная арифметика.
Понятие совместной теории. Элементарная теория данной модели. Элементарная эквивалентность моделей. Понятие полной теории.
Интерпретируемость одной модели в другой. Перевод формулы при данной интерпретации. Взаимная интерпретируемость моделей элементарной геометрии плоскости и поля вещественных чисел. Теорема о переносе свойства разрешимости элементарной теории с интерпретирующей модели на интерпретируемую.
Исчисление предикатов Аксиомы и правила вывода исчисления предикатов. Теорема о тавтологии. Выводимость в теории, простейшие свойства выводимости. Доказуемые, опровержимые, независимые формулы для данной теории. Теорема о дедукции для исчисления предикатов. Общезначимость аксиом исчисления предикатов. Теорема о корректности исчисления предикатов.
Теорема Гёделя о полноте исчисления предикатов (без доказательства). Теорема Мальцева о компактности для логики предикатов. Теорема Лёвенгейма–Сколема (для счётной сигнатуры).
Нестандартные модели арифметики, их существование. Понятие галактики. Описание отношение порядка на элементах данной галактики. Плотность порядка на множестве галактик.
Теория алгоритмов Основные понятия теории алгоритмов. Пошаговый характер выполнения алгоритма. Функция, вычисляемая данным алгоритмом; область определения вычислимой функции. Вычисление словарных и числовых функций на машинах Тьюринга. Тезис Чёрча–Тьюринга.
Разрешимые множества. Нумерация пар натуральных чисел. Нумерация словарного пространства. Эквивалентные определения перечислимого множества. Свойства объединения, пересечения и дополнения разрешимых и перечислимых множеств. Теорема Чёрча–Поста. Перечислимость области определения и области значений вычислимой функции. Теорема о графике вычислимой функции.
Кодирование машин Тьюринга. Существование универсальной машины Тьюринга. Универсальные функции. Пример вычислимой функции, не имеющей всюду определённого вычислимого продолжения. Существование неразрешимого перечислимого множества. Алгоритмическая неразрешимость проблемы самоприменимости и проблемы остановки машин Тьюринга. Существование неотделимой пары перечислимых множеств.
Задача распознавания свойств вычислимых функций по их программам.
Главные универсальные функции. Теорема Райса.
Разрешимые и неразрешимые теории Эффективно аксиоматизируемые, разрешимые теории. Теорема о разрешимости полной эффективно аксиоматизируемой теории. Примеры полных эффективно аксиоматизируемых теорий: элементарная геометрия, теория алгебраически замкнутых полей нулевой характеристики, теория упорядоченного поля действительных чисел (без доказательств).
Метод элиминации кванторов. Полнота и разрешимость теории плотных линейно упорядоченных множеств без первого и последнего элемента.
Формальная арифметика Пеано, её стандартная модель. 1 определимость в стандартной модели арифметики. Эквивалентность понятий перечислимого и 1 -определимого множества. Неперечислимость множества арифметических истин. Проблема распознавания истинности замкнутых арифметических формул, её алгоритмическая неразрешимость. Теоремы Гёделя о неполноте формальной арифметики.
1 -полнота арифметики Пеано и арифметики Робинсона Q (без детального доказательства). Неразрешимость арифметики Пеано, неразрешимость исчисления предикатов в арифметическом языке. Теорема Гёделя–Россера.
Рекомендуемая литература [1] Мендельсон Э. Введение в математическую логику. М.: Наука, 1984. 320 с.
[2] Успенский В. А., Верещагин Н. К., Плиско В. Е. Вводный курс математической логики.
М.: Физматлит, 2002. 128 с.
[3] Колмогоров А. Н., Драгалин А. Г. Математическая логика. М.: УРСС, 2004. 240 с.
[4] Лавров И. А., Максимова Л. Л. Задачи по теории множеств, математической логике и теории алгоритмов. М.: Физматлит, 2004. 256 с.
[5] Клини С. К. Математическая логика. М.: Мир, 1973. 480 с.
[6] Верещагин Н. К., Шень А. Лекции по математической логике и теории алгоритмов.
Часть 2. Языки и исчисления. М.: МЦНМ, 2000. 288 с.
[7] Верещагин Н. К., Шень А. Лекции по математической логике и теории алгоритмов.
Часть 3. Вычислимые функции. М.: МЦНМ, 1999. 176 с.
«