Mathematical Logic and Discrete Mathematics at PDMI

Пятница, 18 апреля, комната 106. Начало в 17:30.

Докладчик: А. Кожевников.

Тема: Нижние экспоненциальные оценки для модальных логик.

Abstract

(доклад по статье P. Hrubes)

В докладе будет доказана теорема о монотонной интерполяции для PSPACE-полных модальных систем Фреге и следующих из нее экспоненциальных оценок на длину вывода формул вида $$ A([]p) -> []B, $$ где $[]$ обозначает модальность ``всегда'', А --- монотонная формула, зависящая от переменных $p_1,...,p_n$, $A([]p)$ получается из $A$ подстановкой $p_i := []p_i$. Если останется время, будет рассказано доказательство теоремы о монотонной интерполяции для интуиционистких систем Фреге.

Слайды доклада можно (будет) скачать здесь: http://logic.pdmi.ras.ru/~arist/talks/modal.pdf