Undecidable problems for propositional calculi with implicationстатьяНаучно-популярная статья
Информация о цитировании статьи получена из
Web of Science,
Scopus
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 8 февраля 2017 г.
Аннотация:In this article, we deal with propositional calculi over a signature containing the classical implication → with the rules of modus ponens and substitution. For these calculi, we consider several decision problems such as recognition of derivations, extensions, completeness and axiomatizations. The main result of this article is that the problem of recognizing extensions is undecidable for every propositional calculus, and the problems of recognizing axiomatizations and completeness are undecidable for propositional calculi containing the axiom x→(y→x). As a corollary, for all formulas A, the problem of derivability of A is undecidable.