Математическая логика (ОТиПЛ)

Элементы теории алгоритмов.

1. Интуитивное понятие алгоритма, вычислимой функции. Ансамбли конструктивных объектов. Область возможных исходных данных. Область применимости алгоритма. Примеры алгоритмов. Вычислимая функция.

2. Модели вычислений. Машины Тьюринга. Машины с неограниченными регистрами (МНР). Тезис Чёрча.

3. Разрешимость, перечислимость подмножества ансамбля конструктивных объектов. Критерий разрешимости перечислимого множества (теорема Поста). Свойства перечислимых, разрешимых множеств. Теорема о графике вычислимой функции. Теорема о проекции.

4. Универсальная вычислимая функция. Невозможность вычислимой функции, универсальной для класса всех всюду определённых вычислимых функций. Главная универсальная вычислимая функция. Теорема о трансляторе (s-m-n-теорема).

Примеры неразрешимых проблем. Неразрешимость проблемы остановки. Примеры неразрешимых перечислимых множеств.

Многозначная (m-сводимость). Свойства m-сводимости. Теорема Райса о неразрешимости нетривиальных классов в.ф. Примеры применения теоремы Райса.

Диофантовы множества. Десятая проблема Гильберта и ее отрицательное решение.

Логика высказываний

1. Язык логики высказываний. Логические связки и таблицы истинности. Приведение формул к дизъюнктивной и конъюнктивной нормальным формам. Булевы функции. Полные системы булевых функций. Теорема Поста. Полиномы Жегалкина.

2. Гильбертовский вариант исчисления для логики высказываний. Алфавит, формулы, схемы аксиом и правила вывода исчисления высказываний. Вывод, выводимая формула. Семантическая корректность исчисления высказываний.

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

3. Генценовский вариант исчисления для логики высказываний. Понятие секвенциального вывода. Эквивалентность гильбертовского и генценовского вариантов исчисления высказываний. Теорема об устранении сечения. Алгоритм поиска вывода в исчислении высказываний.

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

1. Язык первого порядка. Понятие переменной, предиката, квантора. Сигнатура языка первого порядка, терм, формула. Применение языков первого порядка для описания фрагментов естественных языков.

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

2. Семантика языков первого порядка. Интерпретация языка первого порядка. Выполнимые формулы, общезначимые формулы. Равносильность формул языка первого порядка. Основные равносильности. Предваренные формулы. Приведение формулы к предваренной форме.

3. Исчисление предикатов. Схемы аксиом и правила вывода исчисления предикатов. Вывод из гипотез в исчислении предикатов. Теорема о дедукции для исчисления предикатов. Теорема о корректности исчисления предикатов.

Теорема Гёделя о полноте исчисления предикатов. Невозможность аксиоматизации предиката равенства в языке первого порядка. Нормальные модели. Исчисление предикатов с равенством, его корректность и полнота относительно нормальных моделей.

Неразрешимость исчисления предикатов.

4. Теории первого порядка. Примеры теорий первого порядка: теория равенства, теория плотного линейного порядка, теория групп, теория полей, арифметика Пеано.

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

Невозможность аксиоматизации свойства конечности в языке первого порядка. Существование счётных нестандартных моделей арифметики.

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

1. Логика 2-го порядка, основные отличия ее от логики 1-го порядка. Определение предиката равенства. Формула, выражающая конечность. Аксиоматизация арифметики. Неперечислимость логики второго порядка.

Неклассические логики

1. Интуиционистская логика высказываний. Конструктивное понимание логических связок, семантика Крипке.

Аксиомы интуиционистского исчисления высказываний. Теорема о корректности и полноте интуиционистского исчисления высказываний относительно семантики Крипке.

Доказательство невыводимости законов исключенного третьего и снятия двойного отрицания в интуиционистском исчислении высказываний. Свойство дизъюнктивности для интуиционистской логики. Невозможность задания интуиционистских связок истинностными таблицами с конечным числом значений.

2. Многозначная логика.

3. Модальная логика. Язык модальной логики. Примеры модальностей в естественном языке. Системы аксиом для логик K, K4, S4, S5, GL, Grz. Семантика Крипке для модального языка. Классы шкал Крипке, соответствующие основным аксиомам логик K, K4, S4, S5, Grz. Полнота K, K4, S4, S5, Grz относительно семантики Крипке. Вложение интуиционистской логики высказываний в S4.

4. Временные операторы, языки временных логик. Логика данной шкалы времени. Примеры временных логик: логики линейного времени, логики ветвящегося времени. Перевод формул языка пропозициональной временной логики на языки классической логики I-го и II-го порядка. Пример неэлементарной временной логики. Разрешимость линейных временных логик. Временные логики и верификация программ.

Основная литература

1. Булос Дж., Джеффри Р. Вычислимость и логика. М.: Мир, 1994. [С. 12-55, 131-152, 167-180, 253-274.]

2. Мендельсон Э. Введение в математическую логику. М.: Наука, 1984. [С. 19-81, 86-102.]

3. Лавров И. А, Максимова Л. Л. Задачи по теории множеств, математической логике и теории алгоритмов. М.: Физ.-мат. литература, 1995. [С. 50-107, 124-147.]

4. Роджерс Х. Теория рекурсивных функций и эффективная вычислимость. М., Мир, 1972. [С. 11-68, 81-110.]

5. Столл Р. Множества, логика, аксиоматические теории. М.: Просвещение, 1968. [С. 72-191.]

6. Успенский В. А., Верещагин Н. К., Плиско В. Е. Вводный курс математической логики. М.: МГУ, 1991 [С. 17-90, 96-98, 103-133.]

Дополнительная литература

1. Справочная книга по математической логике / Под ред. Дж. Барвайза. Часть 1, Теория моделей. М.: Наука, 1982. [С. 13-55.]

2. Гейтинг А. Интуиционизм. М., Мир, 1965.

3. Катленд Н. Вычислимость. Введение в теорию рекурсивных функций. М.: Мир, 1983. [С. 9-33, 75-114.]

4. Клини С. К. Математическая логика. М.: Мир, 1973. [С. 11-176, 270-296.]

5. Линдон Р. Заметки по логике. М.: Мир, 1968. [С. 11-88.]

6. Успенский В. А. Лекции о вычислимых функциях. М., Физматгиз, 1960. [С. 24-32, 53-81.]

7. Чень Ч., Ли Р. Математическая логика и автоматическое доказательство теорем. М.: Наука, 1983. [С. 11-52.]

8. Фейс Р. Модальная логика. М.: Наука

9. Van Benthem J. Essays in Logical Semantics. Studies in Linguistics and Philosophy. Dordrecht: D.Reidel Publishing Company, 1986.

10. Van Dalen D. Logic and Structure. Universitext. Springer-Verlag, 1994

11. Gamut L. T. F. Logic, Language, and Meaning. University of Chicago Press, Chicago, 1991

12. McCawley J. D. Everything that linguists have always wanted to know about logic. Chicago: University of Chicago Press. 1981.

Программу составили Л. Д. Беклемишев, Е. Ю. Ногина, В. Е. Плиско и Т. Л. Яворская.