On the Numbers of Minimal Tautologies and Properties of Their Proofs in Classical and Nonclassical Logic
DOI:
https://doi.org/10.51408/1963-0046Keywords:
минимальная тавтология, секвенциальные системы без правила сечения пропозициональных логик, количество шагов выводов; монотонность системы, строгая монотонность системыAbstract
It is proved in this paper that the number of minimal tautologies for any given logic tautology of size п can be an exponential function in п, and it is also proved that for every tautology of the given logic there is some minimal tautology such that the number of its sequential form proof steps is equal to minimal steps in the proof of sequential form for the given tautology in cut-free sequent systems for classical, intuitionistic, Joganssons and monotone logics.
References
S. Cook, R. Reckhow, “The relative efficiency of propositional proofs systems”, Journal of Symbolic Logic, vol. 44, pp. 36-50, 1979.
A. Chubaryan, G. Petrosyan, “Frege systems are no monotonous”, Evolutio, Естественные науки, Вып. 3, 12-14, 2016.
A. Chubaryan, A. Khamisyan, G. Petrosyan, On Some Systems For Two Versions Of Many-Valued Logics and its Properties, Lambert Academic Publishing (LAP), 2017.
С. М. Саядян,.А. A. Чубарян, O свойстве немонотонности некоторых систем выводов классического исчисления высказываний, ДНАН РА, Т. 118. No 1, 20- 25, 2018.
Г. М. Зограбян, С. М. Саядян и А. А. Чубарян, Исследование свойства монотонности некоторых пропозициональных систем выводов классической и неклассических логик, ДНАН РА, т.119, №1, сс. 33-39, 2019.
А. А. Чубарян, С. М. Саядян и Г. М. Зограбян, О свойствах монотонности и строгой монотонности пропозициональных систем резолюций классической и неклассических логик, Sciences of Europe, Physics and Mathematics, vol 2, no. 35, pp. 74-79, 2019.
A. Chubaryan, A. Karabakhtsyan and G. Petrosyan, “On some properties of several proof systems for non classical propositional logics”, Вестник РАУ, no. 1, pp. 5-17, 2018.
S.C.Kleene, Introduction to Metamathemics, D.VanNostrand Company, INC,1952.
А. Чубарян и О.Болибекян, “О секвенциальных системах слабых арифметик”, ДНАН Армении, Прикладная математика, 102, т. 3, 214-218, 2002.
A. Atserias, N. Galesi and R. Gavalda, “Monotone proofs of the pigeon hole principle”, Mathematical Logic Quarterly, vol. 47, no. 4, pp. 461-474, 2001.
Downloads
Published
How to Cite
Issue
Section
License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
