Geodesic
On non-monotonous properties of some classical and nonclassical propositional proof systems
Proceedings of the Yerevan State University. Physical and mathematical sciences, Tome 54 (2020) no. 3, pp. 127-136.

Voir la notice de l'article provenant de la source Math-Net.Ru

We investigate the relations between the proof lines of non-minimal tautologies and its minimal tautologies for the Frege systems, the sequent systems with cut rule and the systems of natural deductions of classical and nonclassical logics. We show that for these systems there are sequences of tautologies $\psi_n$, every one of which has unique minimal tautologies $\varphi_n$ such that for each $n$ the minimal proof lines of $\varphi_n$ are an order more than the minimal proof lines of $\psi_n$.
Keywords: minimal tautology, Frege system, sequent system, natural deduction system, proof lines, proof sizes, monotonous and strongly monotonous system. 
@article{UZERU_2020_54_3_a0,
     author = {A. A. Chubaryan and A. A. Hambardzumyan},
     title = {On non-monotonous properties of some classical and nonclassical propositional proof systems},
     journal = {Proceedings of the Yerevan State University. Physical and mathematical sciences},
     pages = {127--136},
     publisher = {mathdoc},
     volume = {54},
     number = {3},
     year = {2020},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/UZERU_2020_54_3_a0/}
}
TY  - JOUR
AU  - A. A. Chubaryan
AU  - A. A. Hambardzumyan
TI  - On non-monotonous properties of some classical and nonclassical propositional proof systems
JO  - Proceedings of the Yerevan State University. Physical and mathematical sciences
PY  - 2020
SP  - 127
EP  - 136
VL  - 54
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/UZERU_2020_54_3_a0/
LA  - en
ID  - UZERU_2020_54_3_a0
ER  - 
%0 Journal Article
%A A. A. Chubaryan
%A A. A. Hambardzumyan
%T On non-monotonous properties of some classical and nonclassical propositional proof systems
%J Proceedings of the Yerevan State University. Physical and mathematical sciences
%D 2020
%P 127-136
%V 54
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/UZERU_2020_54_3_a0/
%G en
%F UZERU_2020_54_3_a0
A. A. Chubaryan; A. A. Hambardzumyan. On non-monotonous properties of some classical and nonclassical propositional proof systems. Proceedings of the Yerevan State University. Physical and mathematical sciences, Tome 54 (2020) no. 3, pp. 127-136. http://geodesic.mathdoc.fr/item/UZERU_2020_54_3_a0/

[1] A. S. Anikeev, “On Some Classification of Provable Propositional Formulas”, Matem. Zametki, 2 (1972), 165–174 | MR

[2] A. Chubaryan, A. Karabakhtsyan, G. Petrosyan, “Some Properties of Several Proof Systems for Intuitionistic, Johansson's and Monotone Propositional Logics”, JASR, 2 (2018), 61–72

[3] G. M. Zohrabyan, S. M. Sayadyan, A. A. Chubaryan, “Investigation of Monotonocity of Some Propositional System of Classical and Nonclassical Logics”, Reports of NAS RA, 119:1 (2019), 33–39 | MR

[4] A. A. Chubaryan, S. S. Sayadyan, G. M. Zohrabyan, “On Properties of Monotonocity and Strongly Monotonocity of Propositional Resolution Systems of Classical and Nonclassical Logics”, Sciences of Europe. Physics and Mathematics, 2:35 (2019), 74–79 (in Russian) | MR

[5] A. A. Hambardzumyan, H. A. Gasparyan, S. A. Hovhannisyan, A. A. Chubaryan, “On the Number of Minimal Tautologies and Properties of Their Proofs in Some Systems of Classical and Nonclassical Logics”, Mathematical Problems of Computer Science, 52:2 (2019), 70 pp. | MR

[6] A. A. Chubaryan, A. A. Hambardzumyan, H. A. Gasparyan, S. A Hovhannisyan, “On Some Properties of Minimal Tautologies of Classical and Nonclassical Logics”, Reports of NAS RA, 120:1 (2020), 4–5 (in Russian) | MR

[7] A. A. Hambardzumyan, “Investigation of Monotonous Properties for Frege Systems”, Mathematical Problems of Computer Science, 53:7 (2020), 70 pp. | MR

[8] S. A. Cook, R. A. Reckhow, “The Relative Efficiency of Propositional Proof Systems”, J. Symbolic Logic, 44 (1979), 36–50 | DOI | MR | Zbl

[9] S. C. Kleene, Introduction to Mathematics, D. Van Nostrand Company, Inc., New York, 1952, 348 pp. | MR

[10] A.A. Chubaryan, H.R. Bolibekyan, “On the sequential calculus of weak arithmetics”, Doklady NAN Armenii, 102:3 (2002), 214–218 (in Russian) | MR

[11] G. Mints, A. Kozhevnikov, “Intuitionistic Frege Systems are Polynomially Equivalent”, Zapiski Nauchnykh Seminarov POMI, 316 (2004), 129–146 | MR | Zbl

[12] S. Sayadyan, A. Chubaryan, “On Polynomially Equivalence of Minimal Frege Systems”, Mathematical Problems of Computer Science, 27 (20207), 141–144

[13] R. Harrop, “Concerning formulas of the types $A\to B\vee C$, $A\to\exists xB(x)$”, J. Symbolic Logic, 25 (1960), 27–32 | DOI | MR | Zbl

[14] S. Sayadyan, “On the Comparison of Some Propositional Proof Systems of Intuitionistic Logic”, YSU, Scientific Notes, 2 (2005), 25–30 (in Armenian) | Zbl

[15] A. A. Chubaryan, H. A. Tamazyan, A. S. Tshitoyan, “Some Improvement of Lower Bounds for Steps and Sizes of Proofs in Frege Systems”, Sciences of Europe, 1:37 (2019), 39–44 | MR