И.А.Горбунов//Минимальная вполне-определённая логика

Дата и время: 24.04.2026 в 16:20 Докладчики: И.А.Горбунов (ТвГУ, ВШЭ) и М.Н.Рыбаков (МФТИ, ТвГУ, ВШЭ) Тема: Минимальная вполне-определённая логика Аннотация: Понятие вполне-определённой логики (well-determined logic) было введено Рышардом Вуйцицким: это логика, обладающая слабым дедуктивным свойством (т.е. для неё выполняется слабая теорема о дедукции) и свойством конъюнкции. Таковыми являются, например, все суперинтуиционистские логики. Содержательно, вполне-определённые логики позволяют выражать логическое следование в них. Благодаря устройству таких логик, для их задания можно не требовать семантики с сильной полнотой, достаточно иметь слабую полную семантику, т.е. полную семантику для множества их тавтологий. Множество тавтологий вполне-определённой логики Р.Вуйцицкий назвал дедуктивным множеством, и затем нашёл критерий дедуктивности. Нами был получен эффективный критерий дедуктивности. На его основе была найдена наименьшая вполне-определённая логика W, о которой мы и расскажем. Мы покажем, что логика W не обладает дедуктивным свойством, а также опишем её в виде исчисления. Также будет предложена семантика, относительно которой W корректна и полна. Кроме того, мы представим результаты о финитной аппроксимируемости и разрешимости логики W. Отметим, что множество тавтологий логики W полиномиально разрешимо.