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

Введение в математическую логику и теорию алгоритмов 2020-2021 (Беклемишев)

Лекторы:

акад. РАН, проф. Лев Дмитриевич Беклемишев
(1-й поток, 201-206 группы)

проф. Мати Рейнович Пентус
(2-й поток, 207-212 группы)

Пересдачи 13 (СБ), 16 (ВТ), 20 (CБ) 22 (ПН) февраля
начинаются в 16:45

 

    • (new) Типовые задачи (неполный список), такие задачи нужно уметь решать на экзамене.

 

    • В день экзамена в 9:00 пересдачи в 16:45 билеты студентам сдающих групп будут раздаваться на следующем сайте, для скачивания билета нужно ввести номер зачётки (Внимание: для успешного скачивания билета необходимо в браузере разрешить данному сайту «показывать всплывающие окна», либо можно скачать билет по ссылке, которая появится после ввода номера зачетки):
      https://sites.google.com/view/mathlogica2020/

      Важно: на решение двух задач из билета отводится 1 час, плюс 15 минут на загрузку решений в Dropbox на проверку. Существенное опоздание с загрузкой решений может привести к незасчитанным задачам.

 

 

 

 

Расписание консультаций по ВМЛиТА

Ссылка Zoom рассылается старостам групп

ВС 03 января 10:00 (Л.Д.Беклемишев) ✓
ПТ 08 января 10:00 (Л.Д.Беклемишев) ✓
ПН 11 января 9:30 (М.Р.Пентус) ✓
ВТ 19 января 10:00 (М.Р.Пентус)

Расписание экзаменов по ВМЛиТА

Билеты выдаются в 9:00.

Дата Группы (и преп. семинаров)
ПН 04 января 203 (Плиско / Колмаков)
207 (Яворская)
ВТ 05 января 204 (Плиско / Колмаков)
208 (Яворская)
СБ 09 января 202 (Плиско / Красненкова)
ВТ 12 января 209 (Крупский / Оноприенко)
210 (Золин)
ЧТ 14 января 201 (Плиско / Красненкова)
206 (Крупский / Оноприенко)
СР 20 января 211 (Яворская)
212 (Золин)
ПТ 22 января 205 (Крупский / Оноприенко)

Лекции

 YouTube: Видео лекций Беклемишева (осень 2020)

Разделы курса, конспекты, слайды:

  1. Теория множеств (pdf)
  2. Логика высказываний:
    • 2020.10.23: Лекция 8 (слайды, pdf):
      Формулы логики высказываний, оценки переменных, тавтологии, равносильности, ДНФ и СДНФ (КНФ и СКНФ).
  3. Логика предикатов:
      • 2020.10.30: Лекция 9 (слайды, pdf)
        Предикаты, модели, синтаксис логики предикатов (термы и формулы), семантика логики предикатов (значение терма, истинность формулы), предикаты, определимые в модели.
      • 2020.11.06: Лекция 10 (слайды, pdf)
        Предикаты, определимые в модели, гомоморфизм, изоморфизм и автоморфизм моделей, доказательство невыразимости предиката в модели методом автоморфизма, автоморфизмы плоскости с отношением «между» и отношением равенства длин отрезков.Выполнимые и общезначимые формулы, эквивалентные формулы; основные равносильности.Правило подстановки и правило эквивалентной замены в логике предикатов. Теорема о предваренной нормальной форме.
      • 2020.11.13: Лекция 11 (слайды, pdf)
        Теория 1-го порядка, ее модель, теория с равенством, нормальная модель, аксиомы формальной арифметики, аксиомы теории множеств ZFC.Аксиомы элементарной геометрии (планиметрии), теорема Тарского о полноте и разрешимости элементарной геометрии.Исчисление предикатов, понятие выводимости формулы в исчислении, свойства выводимости.
      • 2020.11.20: Лекция 12 (слайды, pdf)
        Теорема о дедукции для исчисления предикатов. Непротиворечивая теория. Метод доказательства непротиворечивости теории путем предъявления ее модели. Метод доказательства независимости формулы от теории путем предъявления контрмодели формулы, являющейся моделью теории. Примеры непротиворечивых теорий. Вопрос о непротиворечивости теории множеств ZFC.Теорема Гёделя о полноте исчисления предикатов (эквивалентность двух формулировок, без док-ва самой теоремы). Теорема Гёделя – Мальцева о компактности исчисления предикатов.Существование нестандартных моделей арифметики. Их структура с точки зрения линейного порядка < — совокупность «галактик» есть плотный линейный порядок без наибольшего элемента, но с наименьшим элементом; каждая галактика, кроме первой, упорядочена как Z (множество целых чисел); первая упорядочена как N (множество натуральных чисел).
    • 2020.11.27: Лекция 13 (слайды, pdf)
      Элементарная теория модели. Элементарно эквивалентные модели. Подмодель и элементарная подмодель. Теорема Лёвенгейма – Сколема. Следствия о существовании счетных моделей теории полей вещественных чисел, элементарной геометрии, теории множеств. Доказательство теоремы Лёвенгейма – Сколема.Существование элементарных подмоделей промежуточных мощностей. Теорема Мальцева о повышении мощности модели и ее следствие для формальной арифметики.
  4. Теория алгоритмов
      • Понятие алгоритма. Неформальное представление о вычислимых функциях. Тезис Чёрча – Тьюринга. Вычислительные модели. Определение машины Тьюринга. Примеры простейших машин.
      • 2020.12.04: Лекция 14 (слайды, pdf)
        Машины Трюринга. Понятие «машина Тьюринга вычисляет функцию f». Вычислимые по Тьюрингу функции. Вычислимые нумерации пар натуральных чисел, n-ок натуральных чисел, множества всех конечных последовательностей натуральных чисел, множества всех слов в конечном алфавите.Разрешимые множества (n-ок натуральных чисел). Замкнутость семейства разрешимых множеств относительно пересечения, объединения, дополнения.Перечислимые множества. Замкнутость семейства перечислимых множеств относительно пересечения и объединения. Диофантовы уравнения, диофантовы множества (натуральных чисел). Теорема Матиясевича о неразрешимости множества диофантовых уравнений, имеющих решения.
    • 2020.12.11: Лекция 15 (слайды, pdf)
      Теорема Поста: множество разрешимо тогда и только тогда, когда оно и его дополнение перечислимы. Теорема о графике.Эффективно аксиоматизируемые теории. Перечислимость всякой эфф. аксиоматизируемой теории, и наоборот. Разрешимость всякой полной эффективно аксиоматизируемой теории. Примеры таких теорий.Кодирование машин Тьюринга. Разрешимость множества кодов всех программ машин Тьюринга. Универсальная машина Тьюринга, описание ее работы.Понятие функции, универсальной для данного семейства функций. Вычислимость универсальной функции для семейства всех вычислимых функций (из N в N).
    • 2020.12.18: Лекция 16 (слайды, pdf)
      Вычислимая функция, не продолжаемая до тотальной вычислимой. Построение перечислимого, но неразрешимого множества. Неразрешимость «проблемы остановки». Построение неотделимой пары перечислимых множеств.Понятие главной универсальной функции. Теорема: универсальная функция, построенная по универсальной машине Тьюринга, является главной.Теорема Успенского — Райса о неразрешимости индексного множества всякого нетривиального свойства вычислимых функций.

 YouTube: Видео лекций Беклемишева (осень 2019)

Лекции других лет

Семинары

Видеоматериалы по темам курса

 

 

 

  • Основы теории вычислимости (Дмитрий Ицыксон, ПОМИ* РАН, 76 мин)
    *ПОМИ — Петербургское отделение Математического института им. В.А.Стеклова.

Факультатив (просеминар)

 

 

    • 09.11 (ПН) и 10.11 (ВТ): аспиранты Илья Мещерин и Валерия Кирова
      и проф. Василий Александрович Любецкий
      Темы: «Случайные числа и абсолютно неразрешимые проблемы»
      и «Теория графов в биоинформатике»

 

 

 

 

Описание: В дополнение к семинарам будут проводиться дополнительные (факультативные) занятия в жанре просеминара 1 раз в две недели (как и семинары). На них сотрудники кафедры будут рассказывать о темах, не затронутых в курсе, о направлениях исследований, которыми занимаются они и которыми могут заниматься студенты, выбрав нашу кафедру (в конце 2-го курса).

Вторая половина занятия обычно будет отведена решению задач. В конце занятия будет даваться короткий тест-пятиминутка. Накопленные результаты этих тестов будут учитываться и приведут к бонусам при сдаче экзамена.

Цель — познакомить студентов с различными гранями «Математической логики и теории алгоритмов», которые не освещаются (или мало освещены) в базовом курсе лекций, дать представление о том, чем занимается тот или иной сотрудник кафедры, с тем чтобы студенты имели больше возможностей для выбора направления исследований и научного руководителя.

Информацию о направлениях исследований, ведущихся на кафедре, и возможных научных руководителях вы можете также найти на доске кафедры, которая размещена на 16-м этаже в лифтовом холле, а также на этой и этой страницах.

Рекомендуемая литература