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

Механико-математического факультета МГУ


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

Лектор: профессор Валентин Борисович Шехтман
Осень 2018 года

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

 

 

    • Даты пересдач: 14 и 21 февраля (четверг), 16:45, аудитории 424 и 425 (2 ГУМ).

 

    • Расписание экзаменов зимней сессии по данному курсу:
      Дата Аудитория Группы (преподаватель семинаров)
      10 января 14-08 (ГЗ) 202 (Плиско), 204 (Яворская), 205 (Плиско)
      14 января 429 (2ГУМ) 207 (Золин), 209 (Кузнецов)
      15 января 428 (2ГУМ) 203 (Яворская), 206 (Плиско)
      23 января 429 (2ГУМ) 208 (Золин), 210 (Крупский)
      24 января 413 (2ГУМ) 201 (Плиско), 211 (Кузнецов), 212 (Крупский)
    • Программа курса (pdf)

 

    • Материалы:
        • 2018.09.06. Лекция 01: слайды (введение)
        • 2018.09.13. Лекция 02: конспект
          Логика высказываний: формулы, лемма об однозначном анализе формул, подформулы, оценки и значения формул, булевы функции, равносильность формул, сигнальные формулы, теорема о функциональной полноте.
        • 2018.09.20. Лекция 03: конспект
          Логика высказываний: нормальные формы (СДНФ, СКНФ), двойственность.
          Булевы алгебры (БА), изоморфизм БА, частичный порядок в БА, оценка переменных в БА, значение формул в БА, равносильность, общезначимость формул на БА.
        • 2018.09.27. Лекция 04: конспект
          Булевы алгебры: теорема: множество общезначимых формул в любых БА одно и то же.
          Исчисление высказываний (ИВ): аксиомы и правила вывода ИВ, выводимые формулы (определение, примеры), выводимость из гипотез, производные правила вывода, допустимые правила вывода. Теорема о дедукции для ИВ. Корректности ИВ для булевых алгебр.
        • 2018.10.04. Лекция 05: конспект
          Исчисление высказываний: Следствие: ИВ непротиворечиво. Теорема о полноте ИВ (относительно двухэлементной БА, а значит, и относительно любой нетривиальной БА). Непротиворечивые, максимальные непротиворечивые множества формул. Принадлежность формул максимальным непротиворечивым множествам согласована с булевыми связками.
        • 2018.10.11. Лекция 06: конспект
          Языки первого порядка: синтаксис: сигнатура, термы, формулы, лемма об однозначном анализе термов и формул.
          Языки первого порядка: семантика: модель, интерпретирующая функция, значение замкнутого терма в модели, значение замкнутой атомарной формулы в модели (для незамкнутых определение дано в лекции 7), нормальная модель; выполнимая и общезначимая (замкнутая) формула; теория, выполнимая теория; чистая теория равенства Eq; логическое следование формулы из теории; полная теория; элементарная теория модели; теория Eq неполна.
        • 2018.10.18. Лекция 07: конспект
          Эквивалентные теории, элементарно эквивалентные модели. Эквивалентные условия для полноты теории. Определение значения произвольных (не обязательно замкнутых) термов и формул, путём добавления в сигнатуру всех элементов модели в качестве констант. Изоморфизм моделей; преобразование значения терма и значения формулы при изоморфизме
        • 2018.10.25. Лекция 08: конспект
          Теорема: изоморфные модели элементарно эквивалентны. Определимость формулами отношений в модели. Автоморфизм модели. Теорема: всякое определимое в данной модели отношение (предикат) инвариантно при любых автоморфизмах.
          Стандартная теория равенства сигнатуры Ω (состоит из аксиом о свойствах равенства и аксиом инвариантности относительно равенства всех функциональных и предикатных символов сигнатуры Ω). Теорема: во всякой нормальной модели сигнатуры Ω истинна стандартная теория равенства данной сигнатуры. Построение по произвольной модели M сигнатуры  Ω элементарной эквивалентной ей, но уже нормальной, модели M’ сигнатуры Ω.
        • 2018.11.01. Лекция 09: конспект
          Теорема: сильная категоричность теории, содержащей стандартную теорию равенства данной сигнатуры, влечет ее полноту. Конечная аксиоматизируемость элементарной теории (в языке с равенством) любой конечной модели. Следствие: для конечных моделей элементарная эквивалентность моделей равносильна изоморфизму моделей. Общезначимость формул, равносильные формулы; универсальное замыкание формулы.
        • 2018.11.08. Лекция 10: конспект
          Теорема: любые подстановочные примеры тавтологий общезначимы. Лемма: равносильность формул согласована с булевыми связками, кванторами, операцией взятия подстановочного примера. Предваренная нормальная форма. Приведение формул к эквивалентной ПНФ.
        • 2018.11.15. Лекция 11: конспект
          Исчисление предикатов: аксиомы и правила вывода ИП, выводимость формул (из гипотез). Всякий подстановочный пример тавтологии выводим в ИП. Допустимые правила вывода, в том числе правила Бернайса. Теорема дедукции. Теорема о корректности ИП.
        • 2018.11.22. Лекция 12: конспект
          Исчисление предикатов с равенством. Теорема о корректности ИП с равенством (относительно нормальных моделей). Выполнимые теории. Всякая выполнимая теория (с или без равенства) непротиворечива. Арифметика Пеано.
          Модальное исчисление S5. Модальные формулы. Схемы аксиом исчисления S5. Семантика Крипке для S5. Общезначимые и выполнимые модальные формулы. Теорема о корректности S5. Стандартный перевод модальных формул в язык первого порядка (с одноместными предикатными символами). Лемма: истинность модальной формулы в модели Крипке равносильна истинности (в соответствующей модели) универсального замыкания её стандартного перевода.
        • 2018.11.29. Лекция 13: конспект
          Свойства исчисления S5: равносильность нескольких утверждений — выводимость формулы в S5, выводимость ее стандартного перевода A* в ИП, общезначимость формулы во всех моделях, истинность ее стандартного перевода во всех моделях, аналогично для конечных моделей. (Доказательство этой теоремы занимает всю эту лекцию, для чего вводятся следующие понятия.)
          Доказуемая эквивалентность модальных формул. Модальные формулы глубины 1. Лемма: существует лишь конечное число попарно неэквивалентных модальных формул глубины 1 от переменных p1,…,pn. Теорема: в S5 всякая формула эквивалентна некоторой формуле глубины 1. Следствие: в S5 существует лишь конечное число попарно неэквивалентных модальных формул от переменных p1,…,pn.
          Непротиворечивые (в S5) и максимальные непротиворечивые (в S5) множества модальных формул. Всякое непротиворечивое множество формул содержится в некотором максимальом непротиворечивом. Построение модели из совокупности всех максимальных непротиворечивых формул.
        • 2018.12.06. Лекция 14: конспект (полный) (new)
          Полнота исчисления предикатов. Теорема о существовании модели (у всякой непротиворечивой теории). Теорема Гёделя о полноте ИП (без и с равенством). Теорема Гёделя – Мальцева о компактности: если каждое конечное подмножество множества формул Г выполнимо, то и всё множество формул Г выполнимо. Теорема Лёвенгейма – Сколема о понижении мощности (для счетной сигнатуры: если теория выполнима, то она выполнима в не более чем счетной модели; аналогично для сигнатур произвольной мощности). Теорема о повышении мощности: а) если теория имеет сколь угодно большие конечные модели, то она имеет и бесконечную модель; б) если теория в сигнатуре Ω имеет бесконечную модель, то она имеет модели любых мощностей, превышающих мощность Ω.
          Нестандартная модель арифметики: из компактности вытекает существование модели, в которой верно то же, что и в натуральных числах, но не изоморфная натуральным числам.
          Теория множеств. Наивная теория множеств; её противоречивость.
          Теория множеств Цермело: аксиомы (объёмности, пары, объединения, степени, выделения, бесконечности). Вывод следствий: существание пустого множества; совокупность всех множеств является собственным классом. Введение натуральных чисел (по фон Нейману). Введение декартова произведения, функций, биекций, равномощности множеств. Теорема Кантора – Бернштейна. Теорема Кантора о множестве-степени. Аксиома выбора — эквивалентные формулировки.
        • 2018.12.13. Лекция 15: конспект (в сокращении) (new)
      Теория алгоритмов: базовые свойства алгоритмов. Вычислимые функции (на натуральных числах или на словах в некотором конечном алфавите). Разрешимые множества (натуральных чисел или слов в конечном алфавите). Разрешимость конечных множеств. Замкнутость разрешимых множеств относительно пересечения, объединения, дополнения. Полуразрешимые и перечислимые множества, их замкнутость относительно пересечения и объединения. Теорема Поста. Доказательство эквивалентности полуразрешимости и перечислимости множеств. Образ / прообраз разрешимого или перечислимого множества относительно вычислимой функции.
      Универсальная вычислимая функция, теорема о ее существовании. Существование перечислимого неразрешимого множества (подмножества натуральных чисел).
      Разрешимость множества всех формул, всех замкнутых формул в конечной сигнатуре. Перечислимость теории, заданной разрешимым множеством аксиом. Разрешимость полной теории, заданной разрешимым множеством аксиом.
      Арифметичность любого перечислимого множества. Теорема Гёделя о неполноте арифметики.

 

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

 

 

  • Досрочный экзамен состоялся 26 декабря в 10:00 в ауд. 429.
  • «Факультатив» или «коллоквиумы»: по вторникам с 16:45 15:00.
    Аудитория: 433 (с 15:00) и 429 (с 16:45);
    но, вероятно, сразу в 429 будем! Критерии: см. ниже. Список задач (обновлен 17.11.2018)

    Внимание! Во вторники 11 и 18 декабря начинаем в 15:00.
    Задач по теории алгоритмов не будет; задачи от 17.11.2018 — последние.
    Срок приема задач 16-20 и 21-26 — до самого конца (т.е. 18 декабря).
    Критерии: нужно решить около 80% задач из каждого из 4-х разделов (см. ниже). Если в разделах 1 и 2 (которые сейчас уже не принимаются) маленький недобор процента, то должен быть выше процент по разделам 3 и 4 (и наоборот). При выполнении этих критериев дается Бонус 1 (название условное). При решении 80% лишь из трёх разделов — дается Бонус 2 (название условное). Расшифровка (ранее частично озвучивавшаяся) этих бонусов — на коллоквиумах. Бонус 2 кроме того является допуском к досрочному экзамену.
    Раздача «бонусов-1» будет производиться на досрочном (и на основных) экзамене.

    Детальный подсчет количества задач (из которого видно, что в некоторых задачах подпункты А, Б, В считаются самостоятельными задачами):
    •  Раздел 1: задачи 1-7, а именно, 1, 2, 3А, 3Б, 3В, 4, 5, 6, 7А, 7Б (итого 10 задач, нужно решить 8).
    •  Раздел 2: задачи 8-15, а именно, 8, 9, 10, 11, 12, 13, 14, 15 (итого 8 задач, нужно решить 6).
    •  Раздел 3: задачи 16-20, а именно, 16, 17А, 17Б, 17В, 18, 19, 20 (итого 7 задач, нужно решить 6).
    •  Раздел 4: задачи 21-26, а именно, 21, 22А, 22Б, 23, 24Б, 24В, 24Г, 25А, 25Б, 25В, 26 (задача 24А тривиальная, поэтому она не учитывается; итого 11 задач; из них нужно решить 8).

    Решайте и приходите рассказывать Ваши решения!
    Студенты каждой группы приходят раз в две недели, а именно:
    • группы 201, 202, 205, 206, 208, 212 приходят: 02 и 16 и 30 октября, 13 и 27 ноября, 11 декабря.
    • группы 203, 204, 207, 209, 210, 211 приходят: 09 и 23 октября, 06 и 20 ноября, 04 и 18 декабря.
    Просьба приходить только в дни вашей группы.

    На этих коллоквиумах студенты рассказывают преподавателю (в индивидуальном порядке) решения предложенных выше задач на углубленное понимание предмета, не требующих, однако, дополнительных теоретических познаний, выходящих за рамки курса. Узкая цель — решить достаточное количество задач, что будет учтено на экзамене. Широкая цель — более глубокое знакомство с математической логикой и теорией алгоритмов, которое может перерасти в выбор кафедры, области научных интересов и научного руководителя.

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

(почти все книги доступны в Сети в электронном виде)

  1. Крупский В.Н., Плиско В.Е. Математическая логика и теория алгоритмов. — М.: Академия, 2013. — 416 с.
  2. Верещагин Н. К., Шень А. Лекции по математической логике и теории алгоритмов. Часть 2. Языки и исчисления, издание 4-е, исправленное. — М.: МЦНМО, 2012. — 240 с. [PDF]
  3. Верещагин Н. К., Шень А. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции, издание 4-е, исправленное. — М.: МЦНМО, 2012. — 158 с. [PDF]
  4. Мендельсон Э. Введение в математическую логику. — М.: Наука, 1971. — 320 с.
  5. Успенский В. А., Верещагин Н. К., Плиско В. Е. Вводный курс математической логики. 2-е изд. — М.: Физматлит, 2002. — 128 с.
  6. Колмогоров А. Н., Драгалин А. Г. Математическая логика. — М.: УРСС, 2004. — 240 с.
  7. Лавров И. А., Максимова Л. Л. Задачи по теории множеств, математической логике и теории алгоритмов, 3-е изд. — М.: Физматлит, 1995. — 256 с.
  8. Клини С. К. Математическая логика. — М.: Мир, 1973. — 480 с.
  9. Лавров И. А. Математическая логика. — М.: Академия, 2006. — 240 с.
  10. Крупский В. Н., Плиско В. Е. Теория алгоритмов. — М.: Академия, 2009. — 208 с.