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



Внимание! Лекции находятся здесь.

Семинары, осенний семестр 2018 года (группы 207 и 208, ауд. 407).
Даются 2 файла PDF с одинаковым содержанием:
а) для печати на листах A4,
б) для просмотра на экране моб. устройства.
  1. 2018.09.11. Семинар № 1: Логика высказываний
    pdf (screen) | pdf (paper A4) ]
  2. 2018.09.25. Семинар № 2: Исчисление высказываний
  3. 2018.10.09. ауд.413! Семинар № 3: Языки первого порядка, выразимость
  4. 2018.10.23. Семинар № 4: Язык арифметики; автоморфизмы, невыразимость
  5. 2018.11.06. Семинар № 5: Логика первого порядка: исчисление предикатов
  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 ]