On lengths of proofs in non-classical logics

0337052 - MÚ 2010 RIV NL eng J - Journal Article
Hrubeš, Pavel
On lengths of proofs in non-classical logics.
[O délkách důkazů v neklasických logikách.]
Annals of Pure and Applied Logic. Roč. 157, 2-3 (2009), s. 194-205. ISSN 0168-0072. E-ISSN 1873-2461
Institutional research plan: CEZ:AV0Z10190503
Keywords : length of proof * propositional logic * modal logic * intuitionistic logic
Subject RIV: BA - General Mathematics
Impact factor: 0.667, year: 2009

We give proofs of the effective monotone interpolation property for the system of modal logic K. and others, and the system IL of intuitionistic propositional logic. Hence we obtain exponential lower bounds on the number of proof-lines in those systems.

Dokážeme vlastnost efektivní monotonní interpolace pro systémy modálních logik K a dalších a pro systém IL pro intuicionistickou logiku. Odtud dostaneme exponenciální dolní odhady na délku důkazů v těchto systémech.
Permanent Link: http://hdl.handle.net/11104/0181141