On Polynomially Equivalence of Minimal Frege Systems
Abstract
In this paper is shown that any two minimal Frege systems polynomially simulate each other. This result is the extension of the similar result about polynomially equivalence of intuitionistic Frege system. The latter is proved by G. Mints and A. Kojevnikov [1].
References
G. Mints, A. Kojevnikov, Intuitionistic Frege systems are polinomially equivalent, Записки научных семинаров ПОМИ, 316 (2004), 129-145.
S. Buss, P. Pudlak, On the computational content of intuitionistic propositional proofs, Annals of Pure and Applied Logic 109, Nos. 1-2 (2001), 49-64.
S.A. Cook, A.R. Reckhow, The relative efficiency of propositional proof systems, The Journal of Symbolic Logic 44, No. 1 (1979), 36-50.
A. Goerdt, Complexity of the intuitionistic sequent calculus, Theoretische Informatik, TCK Chemnitz (2005), 3-13.
R. Harrop, Concerning formulas of the types A!B_C,A!(Ex)B(x) in intuitionistic formal systems, The Journal of Symbolic Logic 25, No 1 (1960), 27-32.
H. Friedman, One Hundred and Two Problems in Mathematics Logic, The Journal of Symbolic Logic 40, No.2 (1975), 113-129.
R. Iemhoff, On the admissible rules of intuitionistic propositional logic, The Journal of Symbolic Logic 66, No. 1 (2001), 231-243.
S.C. Kleene, Introduction to metamathematics, D. Van Nostrand company, INC, 1952.
Ս. Սայադյան, Ինտուիցիոնիստական ասույթային հաշվի որոշ համակարգերի համեմատում, ԵՊՀ Գիտական տեղեկագիր, 2, 2005, 25-30.
Downloads
Published
How to Cite
Issue
Section
License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
