On the expressive power of implication in classical propositional logic

DOI10.1093/JIGPAL/JZAF095MaRDI QIDQ7256559zbMATH OpenFDO

Authors Aleksy Schubert, Paweł Urzyczyn, Konrad Zdanowski

Publication date 2 June 2026

Published in Logic Journal of the IGPL (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1093/JIGPAL/JZAF095

zbMATH Keywords

classical propositional logicfocused proof systemsprovabilitySAT

Mathematics Subject Classification ID

Mathematical logic and foundations (03-XX) Computer science (68-XX)

Cites work

• A note on the computational complexity of the pure classical implication calculus
• A Survey of the Proof-Theoretic Foundations of Logic Programming
• A treatise on universal algebra. Vol. I.
• An algorithm for the class of pure implicational formulas
• Complete problems for deterministic polynomial time
• Conceptual notation.
• scientific article; zbMATH DE number 5838699 (Why is no real title available?)
• scientific article; zbMATH DE number 5595162 (Why is no real title available?)
• scientific article; zbMATH DE number 3489106 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1950433 (Why is no real title available?)
• scientific article; zbMATH DE number 949290 (Why is no real title available?)
• scientific article; zbMATH DE number 3198011 (Why is no real title available?)
• Investigations into the sentential calculus
• Linear-time algorithms for testing the satisfiability of propositional horn formulae
• Logic Programming with Focusing Proofs in Linear Logic
• The complexity of the falsifiability problem for pure implicational formulas
• The complexity of theorem-proving procedures
• Uniform proofs as a foundation for logic programming

This page was built for publication: On the expressive power of implication in classical propositional logic

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7256559)