Disjunction-free disjunction property
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F23%3A00604291" target="_blank" >RIV/67985840:_____/23:00604291 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
Disjunction-free disjunction property
Original language description
Frege proof systems (often called Hilbert-style systems outside proof complexity) are among the simplest and most natural proof systems for classical and nonclassical propositional logics, they are polynomially equivalent to sequent calculi and natural deduction systems, which further testifies to their robustness and fundamental status. Although it is commonly assumed for all classical propositional proof systems that some tautologies require exponentially large proofs, this has been proven so far only for relatively weak proof systems, unrestricted Frege systems are far beyond the reach of current lower bound techniques.
Czech name
—
Czech description
—
Classification
Type
O - Miscellaneous
CEP classification
—
OECD FORD branch
10101 - Pure mathematics
Result continuities
Project
<a href="/en/project/GA23-04825S" target="_blank" >GA23-04825S: Logic and unsatisfiability</a><br>
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Others
Publication year
2023
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů