Orthologic with Axioms

Simon Guilloud, Viktor Kuncak

TL;DR

This paper introduces "orthologic with axioms," a logical system that extends orthologic (a weaker, more predictable version of classical logic) by allowing custom axioms. This extension enables more precise reasoning and leads to a polynomial-time algorithm for proving theorems, making it a powerful tool for verification and programming language analysis.

What Problem Does This Paper Address?

Classical logic, while powerful, can be computationally expensive, especially in areas like program verification and automated reasoning. This is due to its coNP-hardness, meaning that checking if a formula is valid can take a very long time. Orthologic offers a potential solution by being a "weaker" but more predictable logic based on ortholattices. While orthologic is sound with respect to classical logic, it's not always complete, meaning it can't prove all classically valid formulas. The challenge this paper addresses is how to make orthologic more expressive and practical by allowing it to incorporate specific knowledge or constraints through axioms, without sacrificing its efficiency. This is crucial for applications where predictability and polynomial-time complexity are more important than absolute completeness.

Methods

The core contribution is the development of a proof system for orthologic that explicitly handles arbitrary non-logical axioms. This system is a sequent calculus, a common framework for formal proofs. Key techniques include:

  • Generalized Cut Elimination: The authors prove a form of cut elimination for their system. Unlike classical logic, where cut elimination removes all cuts, here it's restricted to cuts involving axioms or formulas derived from axioms. This is crucial for maintaining polynomial-time complexity.
  • Backward Proof Search: Based on the cut elimination property and a subformula property, they design a polynomial-time algorithm for proof search. This algorithm explores possible proofs in a structured way, guided by the axioms and the structure of orthologic.
  • Axiom Integration: The system allows arbitrary formulas to be treated as axioms. This is a significant departure from standard orthologic and is key to increasing its expressive power.
  • Connection to Classical Logic: The paper demonstrates how orthologic with axioms can exactly solve certain classes of problems that are typically handled by classical logic, such as 2CNF satisfiability and Horn clauses. This is achieved by carefully encoding these problems into the orthologic framework.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Axioms as a Bridge: Adding axioms to orthologic acts as a bridge, allowing it to capture specific knowledge and prove more classically valid formulas without losing its efficiency advantage. This is a powerful way to tailor a general-purpose logic to specific problem domains.
  • Predictability Over Absolute Completeness: The paper highlights a trade-off: orthologic prioritizes predictable, polynomial-time reasoning over the absolute completeness of classical logic. This is a valuable approach for applications where performance and reliability are paramount.
  • Subformula Property is Key: The generalized cut elimination leads to a subformula property, meaning that all formulas appearing in a proof are subformulas of the original sequent or axioms. This property is fundamental for designing efficient proof search algorithms.
  • Orthologic as a Generalization: The work positions orthologic with axioms as a potential generalization of Datalog and other logic programming paradigms, offering a sound and complete framework for reasoning with negation and disjunction.

Key Results

  • Polynomial-Time Proof Search: The paper presents a cubic-time algorithm (O(n³)) for proof search in orthologic with axioms, which can be further optimized to O(n²) for specific cases (e.g., singleton axioms). This is a significant improvement over the coNP-completeness of classical logic.
  • Exact Solvability for Classical Problems: Orthologic with axioms is shown to be complete for several classes of classical problems, including 2CNF satisfiability, Horn clauses, and Datalog programs. This means that if a problem is solvable in classical logic, it is also solvable by this orthologic system.
  • Resolution Width Connection: The paper establishes a connection between orthologic proofs and classical resolution proofs, showing that OL proofs can be simulated by resolution proofs of width 5.

Limitations and Future Work

  • Completeness vs. Efficiency: While orthologic with axioms is more expressive than standard orthologic, it's still not as complete as classical logic in all cases. The paper acknowledges that the system cannot emulate all instances of classical propositional logic axioms.
  • Predicate Logic Extension: The paper explores extensions to effectively propositional logic, which is a fragment of predicate logic. However, a full extension to arbitrary predicate logic remains an area for future work.
  • Practical Implementation: While the theoretical framework is strong, further research into practical implementations and benchmarks on real-world verification problems would be valuable.
  • Datalog Generalization: The paper lays the groundwork for using orthologic to generalize Datalog. Further exploration into the expressiveness and applications of this generalization is suggested.

Summary updated

BibTeX
@article{guilloud2024orthologic,
  author = {Simon Guilloud and Viktor Kuncak},
  title = {{Orthologic with Axioms}},
  journal = {Proc. ACM Program. Lang.},
  year = {2024},
  doi = {10.1145/3632881},
}
Figure