Логика

Читается: 1-2 модуль 3 курса 
Пререквизиты: Основые понятия математики; ВЫчислимость и сложность; Логика
Трудоемкость: 5 кредитов

64 аудиторных часов:

• 32 часов лекций;
• 32 часов семинаров.

Формы контроля:

• экзамен;
• 1 контрольная работа;
• 2 домашних задания.

Преподаватели

Беклемишев Лев Дмитриевич

Базовая кафедра Математического института им. В.А. Стеклова РАН: Профессор

 

 О курсе

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

Содержание лекций:

1. Введение.
2. Предмет математической логики. Вопросы оснований математики.
3. Аксиоматическое построение элементарной геометрии, роль аксиомы о параллельных. Парадоксы теории множеств, cемантические парадоксы. Формальный аксиоматический метод Гильберта, программа Гильберта. Роль теорем Гёделя о неполноте.
4. Логика высказываний. Теорема о дизъюнктивной нормальной форме. Исчисление высказываний в секвенциальной форме Генцена. Теорема о полноте.
5. Интуиционизм как философия математики. Интерпретация интуиционистской логики по Брауэру-Гейтингу-Колмогорову. Интуиционистская логика высказываний, её модели Крипке. Теорема Крипке о полноте интуиционистской логики высказываний. Дизъюнктивное свойство. Теорема Гливенко.
6. Модальности и их возможные интерпретации. Модальные логики, логика S4, перевод Гёделя. Теорема о соответствии интуиционистской логики и модальной логики S4. Эпистемическое понимание модальности для системы с несколькими агентами. Логика S5, её полнота по Крипке. Модальность как доказуемость, логика доказуемости Гёделя-Лёба.
7. Логика предикатов.
8. Предикаты. Переменные и их области изменения. Кванторы. Языки
9. первого порядка: термы, формулы, подформулы. Примеры языков первого порядка: язык арифметики, язык элементарной геометрии.
10. Интерпретации (алгебраические системы, модели) для данного языка первого порядка. Истинность замкнутой формулы в данной
11. интерпретации. Предикаты, выразимые в данной интерпретации.
12. Аксиомы и правила вывода исчисления предикатов. Общезначимость аксиом исчисления предикатов. Теорема о корректности исчисления предикатов.
13. Теорема Гёделя о полноте исчисления предикатов (без доказательства). Теорема о компактности для логики предикатов.
14. Нестандартные модели арифметики, их существование.
15. Описание отношения порядка для счётных нестандртных моделей арифметики.
16. Элиминация кванторов. Теорема Тарского о разрешимости теории поля вещественных чисел и элементарной геометрии.
17. Формальная арифметика, её стандартная модель.
18. Сигма-определимость в стандартной модели арифметики.
19. Эквивалентность понятий перечислимого и сигма-определимого множества. Неперечислимость множества арифметических истин. Проблема распознавания истинности замкнутых арифметических формул, её алгоритмическая неразрешимость. Теоремы Гёделя о неполноте формальной арифметики (вторая теорема Гёделя о неполноте без доказательства).

Рекомендуемая литература:

1. Мендельсон Э.  Введение в математическую логику. --- М.: Наука, 1984. --- 320 с.
2. Успенский В. А., Верещагин Н. К., Плиско В. Е. Вводный курс математической логики. М.: Физматлит, 2002. --- 128 с.
3. Клини С.К. Математическая логика. --- М.: Мир, 1973. ---    480 с.
4. Верещагин Н. К., Шень А. Лекции по математической логике и теории алгоритмов. Часть 2. Языки и исчисления. --- М.: МЦНМO, 2000. --- 288 с.