Home

Пятница, 27 марта, 18:00, к. 106

  • The directory /tmp/drutex-478350a04cab00f74bb8085792410b48-1 has been created.
  • The directory /tmp/drutex-478350a04cab00f74bb8085792410b48-2 has been created.
  • The directory /tmp/drutex-478350a04cab00f74bb8085792410b48-3 has been created.

Пятница, 27 марта, комната 106. Начало в 18:00.

Докладчик: А. Смаль.

Тема: Мини-курс: 'Логические основы теории сложности доказательств'. Лекция 2.

Abstract

На первой лекции были рассмотрены две системы доказательств: Генценовская система доказательств для пропозициональной логики TeX Embedding failed! и секвенциальная система доказательств для логики первого порядка TeX Embedding failed!. Для обеих систем были сформулированы теоремы корректности и полноты, в том числе и для закреплённых (anchored) доказательств. Кроме этого были формулированы теоремы компактности для пропозициональной логики и логики предикатов.

Вторая лекция начнётся с определения арифметики Пеано и некоторых её подсистем.Далее будут обсуждаться полиномиально ограниченные теории и теорема Париха (Parikh). В заключение лекции будут рассмотрены некоторые расширения подсистемы TeX Embedding failed! арифметики Пеано.