Аннотация:
Классическая импликация не является релевантной: поскольку в классической логике верен закон $A \rightarrow ( B \rightarrow A)$, истинное утверждение $A$ следует из любого другого утверждения $B$. Этот закон соответствует структурному правилу ослабления, согласно которому можно произвольным образом усиливать посылку импликации или ослаблять её заключение. Релевантная логика $\mathrm{R}$ — это субструктурная логика классического типа без правила ослабления, но с правилом дистрибутивности. Оказывается, что задача доказуемости в этой логике неразрешима: к ней можно свести задачу равенства в полугруппах [Urquhart 1984]. С другой стороны, $\mathrm{R}$ без дистрибутивности — в литературе такая логика ещё обозначается через $\mathrm{CFL}_{ec}$ — оказывается разрешимой, что следует из так называемого «трюка Крипке». При этом сложность доказуемости в $\mathrm{CFL}_{ec}$ является Аккерман-полной задачей; если же ограничиться импликативным фрагментом $\mathrm{R}$, сложность падает до $2 \text{-} \mathsf{EXPTIME}$. В доказательстве последних двух результатов используются алгоритмические задачи для разновидностей счётчиковых машин с «ненадёжными вычислениями».
Будет дан обзор всех этих результатов. Дополнительная литература:
- A. Urquhart. The undecidability of entailment and relevant implication. Journal of Symbolic Logic 49(4), 1059–1073, 1984.
- A. Urquhart. The complexity of decision procedures in relevance logic II. Journal of Symbolic Logic 64(4), 1774–1802, 1999.
- S. Schmitz. Implicational Relevance Logic is 2-EXPTIME-complete. Journal of Symbolic Logic 81(2), 641–661, 2016.
|
