|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ИНХС РАН |
||
Undecidability of the problem of recognizing axiomatizations for propositional calculi with implicationстатья Научно-популярная статья
Статья опубликована в высокорейтинговом журнале
Информация о цитировании статьи получена из
Web of Science,
Scopus
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 28 октября 2016 г.
- Автор: Bokov Grigoriy V.
- Журнал: Logic Journal of the IGPL
- Том: 23
- Номер: 2
- Год издания: 2015
- Издательство: Oxford University Press
- Местоположение издательства: United Kingdom
- Первая страница: 341
- Последняя страница: 353
- DOI: 10.1093/jigpal/jzu047
- Аннотация: In this article, we consider propositional calculi, which are finitely axiomatizable extensions of intuitionistic implicational propositional calculus together with the rules of modus ponens and substitution. We give a proof of undecidability of the following problem for these calculi: whether a given finite set of propositional formulas constitutes an adequate axiom system for a fixed propositional calculus. Moreover, we prove the same for the following restriction of this problem: whether a given finite set of theorems of a fixed propositional calculus derives all theorems of this calculus. The proof of these results is based on a reduction of the undecidable halting problem for the tag systems introduced by Post.
- Добавил в систему: Боков Григорий Владимирович