Кафедра математической логики и теории алгоритмов

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

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

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

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

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

    1. 2020.09.02 & 09. Семинар № 1: Начала теории множеств.
      Д/З: screen | лист A4
      О задаче число сюръекций (pdf).
      Читать: Верещагин, Шень «Начала теории множеств», глава 1 (см. PDF ниже).

 

    1. 2020.09.16 & 23. Семинар № 2: Упорядоченные множества. Арифметика порядков.
      Д/З: screen | лист A4
      Читать: Верещагин, Шень «Начала теории множеств», глава 2, разделы 2.1–2.4.

 

    1. 2019.09.30 & 07. Семинар № 3: Логика высказываний: выполнимость, эквивалентность формул, СДНФ.
      В 212 группе семинар прошел онлайн. Ссылка (ограниченного доступа) на видеозапись: .
      Материалы: [ screen | видео ] Читать: Верещагин, Шень «Языки и исчисления», глава 1, разделы 1.1, 1.2.

 

    1. 2020.10.14 & 19. Семинар № 4: (разбор задач про СДНФ и двойственность) Язык логики предикатов, выразимость, невыразимость.
      Д/З: screen | лист A4
      Читать: Верещагин, Шень «Языки и исчисления», глава 3, разделы 3.1–3.3.

 

    1. 2020.10.26 & 02 ноября. Семинар № 5: Выразимость в арифметике, β-функция Гёделя; общезначимость и выполнимость формул.
      Д/З, включая письменную работу: screen
      Читать: Верещагин, Шень «Языки и исчисления», разделы 3.4, 4.1.

 

    1. 2020.11.09 & 16. Семинар № 6: Исчисление предикатов, построение выводов формул и выводов формул из гипотез. Компактность, теории с равенством, аксиоматизируемые и конечно аксиоматизируемые классы моделей.
      Д/З: [ слайды | screen ]

 

    1. 2020.11.23 & 30. Семинар № 7: Новая тема: Теория алгоритмов: вычислимые функции, разрешимые и перечислимые множества.
      Материалы и задачи: [ слайды | screen | лист A4 ] Видео по теме:
      •  1. Вычислимое и невычислимое (А.В.Спивак, 14 мин)
      •  2. Вычислимые функции, перечислимые множества (А.В.Спивак, 10 мин)
      •  3. Разрешимые и перечислимые функции (А.В.Спивак, 12 мин)
      •  Основы теории вычислимости (Дмитрий Ицыксон, ПОМИ* РАН, 76 мин)
      *ПОМИ — Петербургское отделение Математического института им. В.А.Стеклова.

 

  1. 2020.12.07 & 14. Семинар № 8: Теория алгоритмов: невычислимые функции, неразрешимые и неперечислимые множества
    Материалы задачи:
    [ слайды (new) | Видео (new) | screen | лист A4 ] Видео по теме:
    •  4. Универсальная вычислимая функция (А.В.Спивак, 6 мин)
    •  5. Алгоритмическая неразрешимость проблемы остановки (А.В.Спивак, 8 мин)
    •  6. Неразрешимое перечислимое множество (А.В.Спивак, 11 мин)

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

Семинары прошлых лет: 2018 | 2019

Литература

  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 ]
Состав кафедры