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

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

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

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

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

1. 2019.09.02. Семинар № 1: Начала теории множеств.
   Д/З: screen | лист A4
   О задаче число сюръекций (pdf).
   Читать: Верещагин, Шень «Начала теории множеств», глава 1.
2. 2019.09.16. Семинар № 2: Упорядоченные множества. Арифметика порядков.
   Д/З: screen | лист A4
   Читать: Верещагин, Шень «Начала теории множеств», глава 2, разделы 2.1–2.4.
3. 2019.09.30. Семинар № 3: Логика высказываний: выполнимость, эквивалентность формул, СДНФ.
   Д/З: screen | лист A4
   Читать: Верещагин, Шень «Языки и исчисления», глава 1, разделы 1.1, 1.2.
4. 2019.10.14. Семинар № 4: Язык логики предикатов, выразимость, невыразимость.
   Д/З: screen | лист A4
   Читать: Верещагин, Шень «Языки и исчисления», глава 3, разделы 3.1–3.3.
5. 2019.10.28. Семинар № 5: Выразимость в арифметике, β-функция Гёделя; общезначимость и выполнимость формул.
   Д/З, включая письменную работу:
   screen | лист A4
   Читать: Верещагин, Шень «Языки и исчисления», разделы 3.4, 4.1.
6. 2019.11.11. Семинар № 6: Исчисление предикатов, теории с равенством, компактность.
   Д/З: screen | лист A4
7. 2019.11.25. Семинар № 7: Теория алгоритмов: вычислимые функции, разрешимые и перечислимые множества.
   Д/З: screen | лист A4 (new)
   Видео по теме:
   •  1. Вычислимое и невычислимое (А.В.Спивак, 14 мин)
   •  2. Вычислимые функции, перечислимые множества (А.В.Спивак, 10 мин)
   •  3. Разрешимые и перечислимые функции (А.В.Спивак, 12 мин)
   •  Основы теории вычислимости (Дмитрий Ицыксон, ПОМИ* РАН, 76 мин)
   *ПОМИ — Петербургское отделение Математического института им. В.А.Стеклова.
8. 2019.12.09. Семинар № 8: Теория алгоритмов: невычислимые функции, неразрешимые и неперечислимые множества
   Д/З: [ pdf (screen) | pdf (paper A4) ] (new)
   Видео по теме:
   •  4. Универсальная вычислимая функция (А.В.Спивак, 6 мин)
   •  5. Алгоритмическая неразрешимость проблемы остановки (А.В.Спивак, 8 мин)
   •  6. Неразрешимое перечислимое множество (А.В.Спивак, 11 мин)

Видео по теме:
 Видео лекций проф. Л. Д. Беклемишева (осень 2019)
 «Аксиоматический метод» (проф. Л.Д.Беклемишев, канал «Постнаука»)
 «Компьютерные доказательства» (проф. Л.Д.Беклемишев, канал «Постнаука»)

Страница семинаров осени 2016, 2017, 2018 гг

Литература

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