Курс «Введение в математическую логику и теорию алгоритмов» читается студентам второго курса механико-математического факультета МГУ имени М. В. Ломоносова в 3 семестре.

Целью освоения дисциплины «Введение в математическую логику и теорию алгоритмов» является формирование представления об основах математической логики и развитие способности применять полученные теоретические знания к решению актуальных практических задач, формированию логического мышления, развитию абстрактного мышления, освоение аппарата математической логики. Задачей дисциплины является изучение основных логических исчислений, основ теории алгоритмов и сложности вычислений, основ теории моделей. Дисциплина «Введение в математическую логику и теорию алгоритмов» включает в себя такие разделы, как алгебра высказываний, исчисление высказываний, логика предикатов, исчисление предикатов, элементы теории алгоритмов.

Список всех тем лекций

Лекция 1. Аксиоматика. Логические формулы.
вопроса которыми занимается математическая логика. Две основные задачи теории алгоритмов. Булева алгебра, алгебра отношений Де Моргана, кванторы и логика предикатов. Программа Гильберта. Отождествление финитных рассуждений с доказательствами в арифметике Пеано. Континуум гипотеза. P=NP? И текущие результаты по ней. Тема логика высказываний. Введение (определение) элементарных высказываний. Логические связки. Определение пропозициональных формул. Лемма об однозначном определении формулы.

Лекция 2. Оценки. Булевы функции.
Пропозициональный язык. Подформулы. Оценки. Лемма о продолжении оценки. Доказательство. Понятие тавтологии, выполнимости. Значение формулы на оценке. Введение понятия булевых функций. Пример. Дополнительные пояснения для доказательства однозначности определения формул. Равносильность формул. Лемма о базовых равносильностях. Функциональная полнота. Лемма о сигнальной функции. Теорема о функциональной полноте. Совершенная дизъюнктивная нормальная форма (СДНФ).

Лекция 3. Булева алгебра.
Элементарная конъюнкция (Сигнальная формула). Теорема об эквивалентности СДНФ (Совершенная дизъюнктивная нормальная форма). Все аналогично СДНФ. Задача. Следствия из принципа двойственности для тавтологий. Булева алгебра. Отношение частичного порядка в булевой алгебре. Примеры бесконечных булевых алгебр. Теорема Стоуна. Лемма об общезначимости. 

Лекция 4. Булева алгебра.
Об общезначимых формулах в булевой алгебре. Схемы аксиом. Правила вывода. Примеры доказательства. Выводы из гипотез. О выводимости конъюнкции. Выводимость. Выводимость конъюнкции. Дополнительные пояснения к доказательству. Теорема дедукции. Правило силлогизма. Теорема о корректности аксиом CL для булевых алгебр.

Лекция 5. Система аксиом.
Теорема о корректности аксиом CL для булевых алгебр. Лемма об импликации Общезначимость 2й аксиомы. Общезначимость 8й аксиомы. Следствие непротиворечивости. Теорема о полноте исчисления высказываний. Лемма о критерии противоречия. Продолжение доказательства теоремы о полноте исчисления высказываний. Лемма о существовании максимальной подформулы. Свойства максимальных множеств. Завершение темы логики высказываний.

Лекция 6. Логика предикатов.
Определение понятий. Термы. Сигнатура колец (арифметическая). Лемма об однозначном анализе. Определение формул. Восстановление пропущенной части. Модель сигнатуры. Замкнутые термы. Лемма об определении значения терма. Лемма об однозначном определении замкнутой формулы. Замкнутые формулы. Теория-определение. Логическое (семантическое) следование. Свойства теории.

Лекция 7. Эквивалентность моделей.
Логическое (семантическое) замыкание. Лемма о совпадении логических замыканий теорий. Лемма об условиях полноты теории. Модели с оценкой. Лемма о корректности определения оцененного терма и оцененной формулы. Определение эквивалентности моделей. Изоморфность это отношение эквивалентности. Теорема о значении оцененного терма при преобразованиях.

Лекция 8. Нормальные модели.
Теорема. Теорема о следствии элементарной эквивалентности моделей из их изоморфности. Примеры моделей. Существование неарифметических подмножеств натуральных чисел. Условие верности оцененной формулы для модели. Верность аксиом в нормальной модели. Условие корректности определения модели.

Лекция 9. Теории и модели.
Корректное определение модели. Лемма о нормализации. Об оцененных термах и об оцененных формулах. Теорема о следствии полноты из сильной категоричности. Примеры сильно категоричных теорий Условие конечной аксиоматизируемости и сильной категоричности теории. Лемма 9.4.Условие истинности формулы задающей модель. Универсальное замыкание. О равносильности универсальных замыканий. Равносильные формулы. Об отношении эквивалентности в пространстве формул. О тавтологиях.   Список равносильных преобразований. 

Лекция 10. Преобразование формул к стандартному виду.
Формула с тесными отрицаниями. Лемма о равносильности любой формулы формуле с тесными отрицаниями. Предваренная нормальная форма. О равносильности всякой формулы предваренной нормальной форме. О предваренной нормальной форме равносильной логическим связкам. Исчисление предикатов. 

Лекция 11. Исчисление предикатов.
Системы гильбертовского типа. Эквивалентна лемме 4.2. Если в исчислении высказываний выводится формула A то в исчислении предикатов выводится S подстановка. Справедливость некоторых правил, в том числе правила Бернайса (ослабленные). О независимости обозначения переменных. Теорема о дедукции. Теорема о дедукции без правила обобщения. Правило вывода. Допустимость правила Бернайса. о корректности.

Лекция 12. Модальная логика.
О подстановке термов. Значения термов на изоморфизмах. Сигнатуры с равенством. Противоречивая теория. Если теория противоречива то в ней выводится любая формула. Если теория с равенством и имеет нормальную модель, тогда теория непротиворечива. Пример: Арифметика Пеано. Аксиомы. Семантика S5. Если A любая формула от аргумента u в модели M*, то она принимает такое же значение как формула A принимала в модели M или u.

Лекция 13. Модальная логика.
Эквивалентность. Правила монотонности импликаций. Модальные формулы глубины 1. О записи формулы глубины 1. О существовании конечного числа попарно не эквивалентных формул длины 1. О существовании конечного числа попарно не эквивалентных формул от n переменных. Если теория Г непротиворечива то существует максимальная теория которая содержит Г. Свойства максимальных множеств.

Лекция 14. Модальная логика. Теория множеств Цермело.
О существовании модели Гёделя о полноте О компактности Лёвенгейма-Сколема о понижении мощности О повышении мощности (Существование нестандартных моделей арифметики) Теория множеств N противоречива Теория множеств Цермело Кантора-Бернштейна Кантора Аксиома выбора

Лекция 15. Теория алгоритмов.
Понятие алгоритма Формализации этого понятия Понятие вычислимости Тезис Чёрча-Тьюринга Разрешимость Полуразрешимость Поста Перечислимость Тогда 1)если А - разрешимо, то h^(-1)(А) разрешимо 2)если А - перечислимо, то h[A] и h^(-1)(А) перечислимы Об универсальной вычислимой функции Существует перечислимое неразрешимое множество подмножество в N О разрешимости теорий первого порядка Гёделя об определимости Гёделя о неполноте