ON NON-MONOTONOUS PROPERTIES OF SOME CLASSICAL AND NONCLASSICAL PROPOSITIONAL PROOF SYSTEMS

Anahit A. Chubaryan; Arsen A. Hambardzumyan

doi:10.46991/PYSU:A/2020.54.3.127

ON NON-MONOTONOUS PROPERTIES OF SOME CLASSICAL AND NONCLASSICAL PROPOSITIONAL PROOF SYSTEMS

Authors

Anahit A. Chubaryan Chair of Discrete Mathematics and Theoretical Informatics, YSU, Armenia
Arsen A. Hambardzumyan Chair of Discrete Mathematics and Theoretical Informatics, YSU, Armenia

DOI:

https://doi.org/10.46991/PYSU:A/2020.54.3.127

Keywords:

minimal tautology, Frege system, sequent system, natural deduction system, proof lines, proof sizes, monotonous and strongly monotonous system

Abstract

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 ψ_n, every one of which has unique minimal tautologies φ_n such that for each n the minimal proof lines of φ_n are an order more than the minimal proof lines of ψ_n.

Downloads

Published

2020-12-15

How to Cite

Chubaryan, A. A., & Hambardzumyan, A. A. (2020). ON NON-MONOTONOUS PROPERTIES OF SOME CLASSICAL AND NONCLASSICAL PROPOSITIONAL PROOF SYSTEMS. Proceedings of the YSU A: Physical and Mathematical Sciences, 54(3 (253), 127–136. https://doi.org/10.46991/PYSU:A/2020.54.3.127