Skip to content
/ logic2018 Public

Materials & home works for IFMO'2018 logic course

Notifications You must be signed in to change notification settings

shd/logic2018

Repository files navigation

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

Материалы

Лекция 1

Введение издалека: общая топология

  • Определения и примеры
  • Связность

Где почитать

  • Глава 2 из конспекта
  • Виро О.Я., Иванов О.А., Нецветаев Н.Ю., Харламов В.М., Элементарная топология

Лекция 2

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

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

Где почитать

  • Главы 3-4 из конспекта

Лекция 3

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

  • Теорема о дедукции
  • Теорема о корректности
  • Теорема о полноте

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

  • BHK-интерпретация логических связок
  • Теоретико-множественная интерпретация логических связок
  • Формализация интуиционистской логики: варианты 10 аксиомы.
  • Топологическая интерпретация логических связок

Где почитать

Лекция 4

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

  • Ещё раз о философии, мотивация определений
  • Теорема Гливенко (формулировка)
  • Решётки: общее определение, дистрибутивная, импликативная

Где почитать

Лекция 5

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

  • Алгебры Гейтинга и Булевы алгебры
  • Алгебра Линденбаума
  • Полнота Алгебр Гейтинга как моделей ИИВ

Где почитать

Лекция 6

Качественные свойства ИИВ

  • Модели Крипке
  • Модель Крипке есть алгебра Гейтинга
  • Нетабличность ИИВ
  • Гёделевы алгебры
  • Гёделевизация алгебры Линденбаума
  • Гомоморфизм алгебр Гейтинга

Где почитать

Лекция 7

Дизъюнктивность ИИВ и исчисление предикатов

  • Дизъюнктивность ИИВ (⊢α∨β влечёт ⊢α или ⊢β)
  • Язык исчисления предикатов

Лекция 8

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

  • Структуры и модели в ИП, предметное множество
  • Свободные и связанные вхождения, свобода для подстановки
  • Аксиомы и правила вывода в ИП
  • Теорема о дедукции
  • Теорема о корректности ИП (начало)

Где почитать

Лекция 9

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

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

Где почитать

Лекция 10

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

  • Аксиоматика Пеано
  • Теория 1 порядка
  • Формальная арифметика
  • Примитивно-рекурсивные функции

Где почтитать

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

Лекция 11

Представимость функций в формальной арифметике

  • Минимизация. Рекурсивные функции.
  • Бета-функция Гёделя.
  • Представимость рекурсивных функций в формальной арифметике.

Где почтитать

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

Лекция 12

Гёделева нумерация, арифметизация математики, рекурсивность представимых в формальной арифметике функций

  • Гёделева нумерация.
  • Любая представимая в формальной арифметике функция рекурсивна.
  • Формулировка и идея доказательства первой теоремы Гёделя о неполноте арифметики.

Где почтитать

  • Э. Мендельсон. Введение в математическую логику. М. "Наука", 1971

Лекция 13

Теоремы Гёделя о неполноте арифметики

  • Первая теорема Гёделя о неполноте формальной арифметики (с доказательством).
  • Первая теорема Гёделя о неполноте формальной арифметики в форме Россера.
  • Условия выводимости Гильберта-Бернайса-Лёба.
  • Вторая теорема Гёделя о неполноте формальной арифметики (с кратким изложением доказательства).

Где почтитать

  • Э. Мендельсон. Введение в математическую логику. М. "Наука", 1971

Лекция 14

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

  • Мотивация создания теории множеств.
  • Краткое изложение аксиоматики Цермело-Френкеля.

About

Materials & home works for IFMO'2018 logic course

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages