#матлог #учёба #спецсеминар

Семинар «Вероятностные и субструктурные логические системы» (www.mathnet.ru/conf2533) под руководством С.Л. Кузнецова (homepage.mi-ras.ru/~sk/) и С.О. Сперанского (homepage.mi-ras.ru/~speranski/).

27 ноября и 4 декабря 2025 г. состоятся два доклада Т.Г. Пшеницына «Сложность релевантной логики и её разновидностей».

Время: 16:00
Место: МИАН, ауд. 530 + Контур.Толк
Для получения ссылки зарегистрируйтесь на странице семинара: https://www.mathnet.ru/conf2533
(ссылка единая для всех заседаний в этом семестре).

Аннотация:
Классическая импликация не является релевантной, поскольку в классической логике верен закон A→(B→A): истинное утверждение A следует из любого другого утверждения B. Этот закон соответствует структурному правилу ослабления, согласно которому можно произвольным образом усиливать посылку импликации или ослаблять ее заключение. Релевантная логика R — это субструктурная логика классического типа без правила ослабления, но с правилом дистрибутивности. Оказывается, что задача доказуемости в этой логике неразрешима: к ней можно свести задачу равенства в полугруппах (Уркхарт, 1984). С другой стороны, R без дистрибутивности — в литературе такая логика ещё обозначается через CFL_{ec} — оказывается разрешимой, что следует из так называемого "трюка Крипке". При этом сложность доказуемости в CFL_{ec} является Аккерман-полной задачей; если же ограничиться импликативным фрагментом R, сложность падает до 2-EXPTIME. В доказательстве последних двух результатов используются алгоритмические задачи для разновидностей счетчиковых машин с "ненадёжными вычислениями".

В докладах будет дан обзор всех этих результатов.

Литература:
[1] Urquhart, A. (1984). The Undecidability of Entailment and Relevant Implication. The Journal of Symbolic Logic, 49(4), 1059–1073.
[2] Urquhart, A. (1999). The Complexity of Decision Procedures in Relevance Logic II. The Journal of Symbolic Logic, 64(4), 1774–1802.
[3] Schmitz, S. (2016). Implicational Relevance Logic is 2-EXPTIME-complete. The Journal of Symbolic Logic, 81(2), 641–661.

➰ ВК