/logic2019

Primary LanguageTeX

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

Материалы

Лекция 1

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

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

Где почитать

Лекция 2

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

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

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

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

Где почитать

Лекция 3

Решётки

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

Где почитать

Лекция 4

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

Где почитать

Лекция 5

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

Где почитать

Лекция 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.