RUS  ENG
Полная версия
ЖУРНАЛЫ // Алгебра и логика // Архив

Алгебра и логика, 1985, том 24, номер 2, страницы 195–204 (Mi al1900)

Об одном суперинтуиционистском исчислении высказываний

Д. П. Скворцов


Аннотация: Анализируются суперинтуиционистские исчисления высказываний $\widetilde{\Sigma}(\Pi,V_0)$, построенные С. В. Поповым (РЖМат, 1982, 10А50). Каждое из них задается конечным списком аксиом, который определяется системой продукций Поста $\Pi$ и словом $V_0$ в конечном алфавите $\sigma$. Устанавливается равнообъемность всех этих исчислений. Рассматриваются также пропозициональные формулы $U^*(\Pi, V_0, V, \Theta)$, где $V$ — произвольное слово в алфавите $\sigma$, а $\Theta$ — набор номеров продукций системы $\Pi$ (эти формулы построены в цитируемой статье, где утверждается, что проблема выводимости $V$ из $V_0$ в $\Pi$ сводится к проблеме выводимости $U^*(\Pi, V_0, V, \Theta)$ в исчислении $\widetilde{\Sigma}(\Pi,V_0)$, откуда выводится его неразрешимость). Устанавливается, что все формулы $U^*(\Pi, V_0, V, \Theta)$ выводимы в $\widetilde{\Sigma}(\Pi,V_0)$. Поэтому вопрос о разрешимости исчисления $\widetilde{\Sigma}(\Pi,V_0)$ остается открытым.

УДК: 517.12

Поступило: 28.12.1984



Реферативные базы данных:


© МИАН, 2024