Введение в математическую логику (семинары, осень 2018)

Семинары по курсу
Введение в математическую логику и теорию алгоритмов

к.ф.-м.н., с.н.с. Е.Е.Золин

Материалы семинаров и домашние задания

Даются 2 файла PDF с одинаковым содержанием:
а) для просмотра на экране мобильного устройства,
б) для печати на листах A4.

1. 2018.09.11. Семинар № 1: Логика высказываний
   [ pdf (screen) | pdf (paper A4) ]
2. 2018.09.25. Семинар № 2: Исчисление высказываний
   [ pdf (screen) | pdf (paper A4) ]
3. 2018.10.09. Семинар № 3: Языки первого порядка, выразимость
   [ pdf (screen) | pdf (paper A4) ]
4. 2018.10.23. Семинар № 4: Язык арифметики; автоморфизмы, невыразимость
   [ pdf (screen) | pdf (paper A4) ]
5. 2018.11.06. Семинар № 5: Логика первого порядка: вынесение кванторов; общезначимые формулы; исчисление предикатов
   Письменное домашнее задание — на стр. 2 (или 3 в «screen»). Его необходимо сдать 20.11.2018.
   [ pdf (screen) | pdf (paper A4) ]
6. 2018.11.20. Семинар № 6: Логика первого порядка: компактность
   Группа 207: доп. занятие 27 ноября 15:00 (взамен почти пропущенного 20 ноября); сбор у ауд. 407.
   [ pdf (screen) | pdf (paper A4) ] Доп. материал: Нестандартные модели арифметики
7. 2018.12.04. Семинар № 7: Теория алгоритмов: вычислимые функции, разрешимые и перечислимые множества
   [ pdf (screen) | pdf (paper A4) ] Видео по теме:
   •  1. Вычислимое и невычислимое (А.В.Спивак, 14 мин)
   •  2. Вычислимые функции, перечислимые множества (А.В.Спивак, 10 мин)
   •  3. Разрешимые и перечислимые функции (А.В.Спивак, 12 мин)
   •  Основы теории вычислимости (Дмитрий Ицыксон, ПОМИ* РАН, 76 мин)
   *ПОМИ — Петербургское отделение Математического института им. В.А.Стеклова.
8. 2018.12.18. Семинар № 8: Теория алгоритмов: невычислимые функции, неразрешимые и неперечислимые множества
   [ pdf (screen) | pdf (paper A4) ] Видео по теме:
   •  4. Универсальная вычислимая функция (А.В.Спивак, 6 мин)
   •  5. Алгоритмическая неразрешимость проблемы остановки (А.В.Спивак, 8 мин)
   •  6. Неразрешимое перечислимое множество (А.В.Спивак, 11 мин)

Видео по теме:
• «Аксиоматический метод» (проф. Л.Д.Беклемишев, канал «Постнаука»)
• «Компьютерные доказательства» (проф. Л.Д.Беклемишев, канал «Постнаука»)
• «Нестандартные модели — хорошо это или плохо?» (проф. В.А.Успенский, Летняя школа «Современная математика», г.Дубна, 2006)

Литература

1. Крупский В.Н., Плиско В.Е . Математическая логика и теория алгоритмов, Москва, Изд. центр «Академия», 2013. (наиболее близко к семинарам)
2. Верещагин Н.К., Шень А.Х. Языки и исчисления, 4-е издание, Москва, МЦНМО, 2012. [доступно в сети: pdf ]
3. Верещагин Н.К., Шень А.Х. Вычислимые функции, 4-е издание, Москва, МЦНМО, 2012. [доступно в сети: pdf ]
4. Успенский В.А. Лекции о вычислимых функциях, Москва, Физматгиз, 1960. [доступно в сети]
5. Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов, 5-е издание, Москва, Физматлит, 2004. [доступно в сети] (можно пользоваться и более ранними изданиями)
6. Успенский В.А., Верещагин Н.К., Плиско В.Е. Вводный курс математической логики, 2-е издание. Москва, Физматлит, 2004 г. [доступно в сети]
7. Подольский В.В. «Вычислимые функции. Перечислимые и разрешимые множества», конспект. [ pdf + pdf ]