Skip to content

shd/logic2024

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

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

Материалы

Лекция 1

Что такое логика и математическая логика. Исчисление высказываний

  • История вопроса. Логика.
  • Парадоксы теории множеств, необходимость формализации математики, программа Гильберта.
  • Язык исчисления высказываний
  • Теория моделей, оценка высказываний
  • Теория доказательств, доказательства, выводимость
  • Теорема о корректности исчисления высказываний

Где почитать

  • Н.К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Языки и исчисления. https://www.mccme.ru/free-books/shen/shen-logic-part2-2.pdf
  • Конспекты 2011 и 2018 года по логике.
  • Хрестоматия по истории математики. Арифметика и алгебра. Теория чисел. Геометрия. Пособие для студентов физ.-мат. фак. пед. ин-тов. Под ред. А.П. Юшкевича. - М.: Просвещение, 1976. - 318 с.
  • О противоречиях в математическом анализе: Джордж Беркли, «Аналитик. Беседа, адресованная неверному математику: где исследуется, являются ли объект, принципы и выводы современного анализа более отчетливо задуманы или более явно выведены, чем религиозные мистерии и точки веры» --- М.: Мысль, 1978

Лекция 2

Теоремы об исчислении высказываний, интуиционистское исчисление высказываний

  • Теорема о дедукции
  • Теорема о полноте исчисления высказываний
  • Интуиционистское исчисление высказываний: история
  • BHK-интерпретация связок
  • Формализация ИИВ через изменение 10 схемы аксиом
  • Общая топология, базовые определения
  • Топологическое пространство как модель ИИВ

Где почитать

Лекция 3

Модели интуиционистского исчисления высказываний

  • Мотивационный пример: Изоморфизм Карри-Ховарда
  • Непрерывность, компактность
  • Решётки, алгебра Гейтинга и булева алгебра
  • Алгебра Линденбаума

Где почитать

Лекция 4

Теоремы об интуиционистском исчислении высказываний

  • Модели Крипке
  • Теорема о нетабличности ИИВ
  • Теорема о дизъюнктивности ИИВ
  • Теорема о разрешимости ИИВ

Где почитать

Лекция 5

Исчисление предикатов

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

Где почитать

  • Бочаров В.А., Маркин В.И. Введение в логику: учебник. -- М.: ИД <<Форум>>: ИНФРА-М. 2008.
  • Н.К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Языки и исчисления. https://www.mccme.ru/free-books/shen/shen-logic-part2-2.pdf
  • Стефан К. Клини, Математическая логика. Перевод с английского Ю.А. Гастева. Под редакцией Г.Е. Минца. Москва: Издательство «Мир». Редакция литературы по математическим наукам, 1973
  • Материалы по языку <<Алгол-60>>. https://www.algol60.org

Лекция 6

Теорема о полноте исчисления предикатов

  • Непротиворечивые множества формул
  • Модели для непротиворечивых множеств формул
  • Теорема Гёделя о полноте исчисления предикатов
  • Следствие о полноте исчисления предикатов
  • Непротиворечивость исчисления предикатов
  • Теорема Гёделя о компактности бескванторного подмножества исчисления предикатов

Где почитать

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

Лекция 7

Неразрешимость исчисления предикатов, аксиоматика Пеано

  • Машина Тьюринга
  • Неразрешимость исчисления предикатов
  • Аксиоматика Пеано
  • Порядок теории. Теории первого порядка
  • Формальная арифметика

Где почитать

  • П.Дж. Коэн, Теория множеств и континуум-гипотеза --- М.: Изд-во <<Мир>>, 1969.
  • Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений --- М.: Вильямс, 2002.

Лекция 8

Арифметизация логики

  • История вопроса, работы Лейбница
  • Рекурсивные функции
  • Функция Аккермана, доказательство того, что она не является примитивно-рекурсивной
  • Выразимость отношений и представимость функций в формальной арифметике
  • Бета-функция Гёделя, теорема о представимости рекурсивных функций в арифметике
  • Гёделева нумерация, теорема о рекурсивности представимых в формальной арифметике функций.

Где почитать

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

Лекция 9

Общие свойства формальной арифметики, теоремы Гёделя о неполноте

  • Обзор общих свойств формальной арифметики (корректность, непротиворечивость, полнота, разрешимость).
  • Классическая модель формальной арифметики, её корректность.
  • Омега-непротиворечивость, семантическая и синтаксическая полнота.
  • Первая теорема Гёделя о неполноте арифметики.
  • Теорема Гёделя о неполноте арифметики в форме Россера.
  • Consis
  • Условия выводимости Гильберта-Бернайса-Лёфа.
  • Лемма об автоссылках, другая формулировка теоремы Гёделя о неполноте арифметики.
  • Вторая теорема Гёделя о неполноте арифметики.

Где почитать

  • П.Дж. Коэн, Теория множеств и континуум-гипотеза --- М.: Изд-во <<Мир>>, 1969.
  • Гилберт Д., Бернайс П., Основания математики --- М.: Изд-во <<Наука>>, 1982.

Лекция 10

Теоремы о формальной арифметике, (частично) разрешимые задачи исчисления предикатов

  • Ещё о Consis
  • Неразрешимость формальной арифметики, теорема Тарского о невыразимости истины.
  • Какие задачи можно пытаться решать.
  • Эрбранов универсум

Где почитать

  • Гилберт Д., Бернайс П., Основания математики --- М.: Изд-во <<Наука>>, 1982.
  • Ч. Чень, Р. Ли, Математическая логика и автоматическое доказательство теорем --- М.: Изд-во <<Наука>>, 1983.

Лекция 11

Метод резолюций

  • Теорема Эрбрана
  • Метод резолюций
  • Унификация
  • Метод резолюций для исчисления предикатов
  • Использование метода резолюций

Где почитать

  • Ч. Чень, Р. Ли, Математическая логика и автоматическое доказательство теорем --- М.: Изд-во <<Наука>>, 1983.

Лекция 12

Лямбда-исчисление

  • Бестиповое лямбда-исчисление
  • Натуральный вывод
  • Импликационный фрагмент интуиционистского исчисления высказываний
  • Просто-типизированное лямбда исчисление, изоморфизм Карри-Ховарда
  • Обзор различных теорий, основанных на лямбда-исчислении и их приложений в математике и программировании.

Где почитать

Лекция 13

Теория множеств

  • История возникновения теории
  • Аксиомы теории множеств
  • Ординалы

Где почитать

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

Лекция 14

Алгебраические типы, мощность множеств

  • Дизъюнктное объединение множеств.
  • Алгебраические типы
  • Мощность множеств и кардинальные числа
  • Теорема Кантора-Бернштейна
  • Диагональный метод и теорема Кантора
  • Континуум-гипотеза
  • Теорема Лёвенгейма-Сколема
  • Парадокс Сколема

Где почитать

  • Френкель А.А., Бар-Хиллел И. Основания теории множеств. --- УРСС, 2010
  • П.Дж. Коэн, Теория множеств и континуум-гипотеза --- М.: Изд-во <<Мир>>, 1969.
  • Chris Taylor, The Algebra of Algebraic Data Types. https://www.youtube.com/watch?v=YScIPA8RbVE

Лекция 15

Аксиома выбора

  • Формулировки аксиомы выбора: определения, лемма Цорна, теорема Цермело
  • Доказательство эквивалентности (кроме вывода леммы Цорна)
  • Использование аксиомы выбора (на примере эквивалентности пределов по Гейне и по Коши)
  • Теорема Диаконеску (ИИП + ZF влечёт исключённое третье)
  • Ослабленные варианты аксиомы
  • Усиленный вариант аксиомы: универсум фон-Неймана и аксиома конструктивности.

Где почитать

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

Лекция 16

Трансфинитная индукция. Доказательство непротиворечивости формальной арифметики

  • Математическая и трансфинитная индукция, различные формулировки.
  • Система S-бесконечность
  • Сечения. Теорема об устранении сечений
  • Теорема о непротиворечивости формальной арифметики

Где почитать

  • П.Дж. Коэн, Теория множеств и континуум-гипотеза --- М.: Изд-во <<Мир>>, 1969.
  • Френкель А.А., Бар-Хиллел И. Основания теории множеств. --- УРСС, 2010
  • Э. Мендельсон, Введение в математическую логику --- М.: Изд-во <<Наука>>, 1971.

About

No description, website, or topics provided.

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages