How many times do we need an assumption to prove a tautology in minimal logic? Examples on the compression power of classical reasoning

DOI10.1016/j.entcs.2015.06.004zbMath1352.03067OpenAlexW1409123408WikidataQ113317782 ScholiaQ113317782MaRDI QIDQ2520659

Edward Hermann Haeusler

Publication date: 16 December 2016

Full work available at URL: https://doi.org/10.1016/j.entcs.2015.06.004

zbMATH Keywords

proof theorynatural deductionminimal propositional logicpropositional logic complexity

Mathematics Subject Classification ID

Mechanization of proofs and logical operations (03B35) Classical propositional logic (03B05) Complexity of proofs (03F20)

Related Items (1)

A unified procedure for provability and counter-model generation in minimal implicational logic

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A new normalization strategy for the implicational fragment of classical propositional logic
• The intractability of resolution
• Proof theory. 2nd ed
• Intuitionistic propositional logic is polynomial-space complete
• Eigenvariables, bracketing and the decidability of positive minimal predicate logic
• On cut elimination in the presence of perice rule
• The Computational Complexity of Provability in Systems of Modal Propositional Logic
• Lower bounds to the size of constant-depth propositional proofs
• The complexity of theorem-proving procedures

This page was built for publication: How many times do we need an assumption to prove a tautology in minimal logic? Examples on the compression power of classical reasoning