|
Записки научных семинаров ЛОМИ, 1979, том 88, страницы 197–208
(Mi znsl3114)
|
|
|
|
Эта публикация цитируется в 2 научных статьях (всего в 2 статьях)
Сохранение эквивалентности выводов при редукции глубины формул
С. В. Соловьев
Аннотация:
В работе рассматриваются выводы в $(\&\supset)$ – фрагменте интуиционистского исчисления высказываний.
Как известно, замена любого вхождения формулы $\Phi[F]$ в секвенцию $S$ на вхождение формулы $\Phi[p]$, где $p$ – новая пропозициональная переменная, с одновременным добавлением в антецедент формулы $F\supset p$ или $p\supset F$ в зависимости от знака вхождения $F$ в $S$, оставляет выводимость неизменной.
Приводится доказательство того, что естественное продолжение этого преобразования на выводы сохраняет отношение эквивалентности выводов, т.е. преобразованные выводы эквивалентны тогда и только тогда, когда эквивалентны исходные. (Выводы считаются эквивалентными, если совпадают некоторые их нормальные формы или, что то же, эквивалентны их дедуктивные термы.)
Показано, что итерацией этого преобразования каждый вывод произвольной секвенции $S$ может быть преобразован в вывод секвенции $S'$, зависящей только от $S$, сукцедент которой – переменная, а в антецедент входят только формулы вида $a$, $a\&b$, $a\supset b$, $(a\supset b)\supset c$, $a\&b\supset c$, $a\supset(b\&c)$, где $a,b,c$ – переменные. При этом, если $S$ уравновешена, то $S'$ тоже уравновешена. (Секвенция называется уравновешенной, если каждая переменная входит в нее не более двух раз).
Известное соответствие между некоторыми понятиями теории категорий и понятиями теории доказательств позволяет утверждать, что построен унивалентный функтор, отображающий свободную декартово замкнутую категорию в себя. Библ. – 5 назв.
Образец цитирования:
С. В. Соловьев, “Сохранение эквивалентности выводов при редукции глубины формул”, Исследования по конструктивной математике и математической логике. VIII, Зап. научн. сем. ЛОМИ, 88, Изд-во «Наука», Ленинград. отд., Л., 1979, 197–208; J. Soviet Math., 20:4 (1982), 2370–2376
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/znsl3114 https://www.mathnet.ru/rus/znsl/v88/p197
|
Статистика просмотров: |
Страница аннотации: | 133 | PDF полного текста: | 63 |
|