• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Логика

Читается: 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 с.