shd / logic2019

Курс математической логики, КТ, весна 2019

Материалы

• Конспект

• Конспект 2011 года

• Теоретические домашние задания

• Вопросы к коллоквиуму 2-3-4 апреля

• Вопросы к зачёту

• Репозиторий: описание и образцы решения 0-й практической задачи

• Краткая инструкция по утилите make

Лекция 1

Исчисление высказываний

• Немного об истории вопроса
• Язык исчисления высказываний
• Оценка высказываний
• Общезначимость, следование, выполнимость
• Доказательство высказываний, выводимость
• Теорема о дедукции

Где почитать

• Н.К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Языки и исчисления. https://www.mccme.ru/free-books/shen/shen-logic-part2-2.pdf
• Конспект 2011 года по логике.

Лекция 2

Исчисление высказываний: теоремы

• Теорема о дедукции: завершение доказательства
• Теорема о корректности
• Теорема о полноте

Интуиционистское исчисление высказываний

• Интерпретация Брауэра-Гейтинга-Колмогорова

Где почитать

• Н.К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Языки и исчисления. https://www.mccme.ru/free-books/shen/shen-logic-part2-2.pdf
• Конспект 2011 года по логике.
• В.Е.Плиско, В.Х.Хаханян, Интуиционистская логика, Мех-Мат МГУ 2009 (http://lpcs.math.msu.su/~plisko/intlog.pdf)

Лекция 3

Решётки

• Определение решёток
• Дистрибутивные и импликативные решётки
• Булевы и псевдобулевы алгебры
• Оценка высказываний с помощью решёток

Где почитать

• В.Е.Плиско, В.Х.Хаханян, Интуиционистская логика, Мех-Мат МГУ 2009 (http://lpcs.math.msu.su/~plisko/intlog.pdf)

Лекция 4

• Алгебра Линденбаума
• Полнота ИИВ с алгеброй Гейтинга
• Гёделева алгебра
• Операция Г(A)
• Естественный изоморфизм f: Г(A)->A и его свойства
• Дизъюнктивность ИИВ
• Нетабличность ИИВ (формулировки)

Где почитать

• В.Е.Плиско, В.Х.Хаханян, Интуиционистская логика, Мех-Мат МГУ 2009 (http://lpcs.math.msu.su/~plisko/intlog.pdf)

Лекция 5

• Язык исчисления предикатов
• Оценки для формул исчисления предикатов
• Аксиомы и правила вывода в исчислении предикатов
• Теоремы о дедукции и о корректности (формулировки)

Где почитать

• Н.К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Языки и исчисления. https://www.mccme.ru/free-books/shen/shen-logic-part2-2.pdf
• Конспект 2011 года по логике.

Лекция 6

• Теорема о корректности исчисления предикатов
• Теорема Гёделя о полноте исчисления предикатов (формулировка)
• Теорема о существовании модели для непротиворечивого бескванторного множества формул
• Следствие о полноте исчисления предикатов

Где почитать

• Конспект 2011 года по логике.
• П.Дж. Коэн, Теория множеств и континуум-гипотеза --- М.: Изд-во <<Мир>>, 1969.
• Н.К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Языки и исчисления. https://www.mccme.ru/free-books/shen/shen-logic-part2-2.pdf

Лекция 7

• Теорема Гёделя о полноте исчисления предикатов (доказательство)

Где почитать

• Конспект 2011 года по логике.
• П.Дж. Коэн, Теория множеств и континуум-гипотеза --- М.: Изд-во <<Мир>>, 1969.
• Н.К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Языки и исчисления. https://www.mccme.ru/free-books/shen/shen-logic-part2-2.pdf

Лекция 8

• Машина Тьюринга
• Разрешимость языка
• Теорема о неразрешимости языка доказуемых формул исчисления предикатов

Лекция 9

• Аксиоматика Пеано
• Формальная арифметика
• Рекурсивные функции

Где почитать

• Конспект 2011 года по логике.

Лекция 10

• Выразимость отношений в формальной арифметике
• Представимость функций в формальной арифметике
• Характеристические функции для отношений
• Представимость рекурсивных функций в формальной арифметике

Где почитать

• Конспект 2011 года по логике.
• Э. Мендельсон, Введение в математическую логику --- М.: Изд-во <<Наука>>, 1971.

Лекция 11

• Гёделева нумерация
• Рекурсивность представимых функций
• Омега-непротиворечивость
• Формулировка первой теоремы Гёделя о неполноте арифметики

Где почитать

• Конспект 2011 года по логике.
• Э. Мендельсон, Введение в математическую логику --- М.: Изд-во <<Наука>>, 1971.

Лекция 12

• Первая теорема Гёделя о неполноте арифметики
• Формулировка первой теоремы Гёделя о неполноте арифметики в форме Россера
• Условия выводимости Гильберта-Бернайса-Лёфа
• Формулировка второй теоремы Гёделя о неполноте арифметики

Где почитать

• Конспект 2011 года по логике.
• Э. Мендельсон, Введение в математическую логику --- М.: Изд-во <<Наука>>, 1971.

Лекция 13

• Теория множеств. История: наивная теория множеств, парадоксы, попытки разрешения ситуации
• Формализации теории множеств. Аксиоматика Цермело-Френкеля
• Порядок: частичный, линейный, полный
• Ординальные и кардинальные числа
• Аксиома выбора, неконструктивная и конструктивная математика

Где почитать

• Конспект 2011 года по логике.
• А. Френкель, И. Бар-Хиллел, Основания теории множеств --- М.: Изд-во <<Мир>>, 1966.
• П.Дж. Коэн, Теория множеств и континуум-гипотеза --- М.: Изд-во <<Мир>>, 1969.