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