Open AccessOn the Numbers of Minimal Tautologies and Properties of Their Proofs in Classical and Nonclassical Logic
Author(s) -
Arsen A Ambartsumyan,
Hayk Gasparyan,
Sarkis A. Hovhannisyan,
Anahit Chubaryan
Publication year - 2019
Publication title -
mathematical problems of computer science
Language(s) - English
Resource type - Journals
eISSN - 2738-2788
pISSN - 2579-2784
DOI - 10.51408/1963-0046
Subject(s) - tautology (logic) , mathematics , intuitionistic logic , monotone polygon , sequent calculus , discrete mathematics , mathematical proof , intermediate logic , computer science , linear logic , theoretical computer science , propositional variable , geometry , description logic
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.