Введение в математическую логику
и теорию алгоритмов (семинары)
мех-мат ф-т, 2-й курс, осень 2018 года
к.ф.-м.н. с.н.с. Е.Е.Золин

Вторник, ауд. 407, раз в 2 недели
15:00-16:35 (207 группа)
16:45-18:05 (208 группа)

Дни занятий:
11 и 25 сентября
09 и 23 октября
06 и 20 ноября
04 и 18 декабря

Внимание! Письменное домашнее задание нужно сдать 20 ноября 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: Логика первого порядка: компактность
  7. 2018.12.04. Семинар № 7: Теория алгоритмов: вычислимые функции, разрешимые и перечислимые множества
  8. 2018.12.18. Семинар № 8: Теория алгоритмов: невычислимые функции, неразрешимые и неперечислимые множества


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

Литература

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