Logic Morphisms as a Framework for Backward Transfer of Lemmas and Strategies in Some Modal and Epistemic Logics

Ricardo Caferra, Stéphane Demri, Michel HermentAAAI 1991

Introduction

Automated theorem proving has long relied on classical logic due to the availability of highly optimized solvers. However, many complex domains—such as those involving knowledge, necessity, or temporal dynamics—are more naturally expressed in non-classical logics like Modal Logic S4 or Epistemic Logic. While translating these "Source Logics" (SL) into a classical "Target Logic" (TL) is a standard technique, the resulting proofs often become unintelligible technical artifacts. This paper presents a framework for "backward translation," allowing researchers to map classical proof steps and strategies back into the original source logic, preserving domain-specific intuition and lemmas.

Methodology: Logic Morphisms and OSPL

The authors employ Logic Morphisms—formal functions that map one logical system to another—to bridge the gap between SL and TL. A key innovation is the use of Order-Sorted Predicate Logic (OSPL) as the target. OSPL is particularly effective because its "sort" (type) system can naturally represent the "worlds" or "contexts" inherent in modal logic.

To maintain the relationship between worlds, the framework utilizes context terms to represent paths in the modal structure as syntactic terms in the classical logic. The core contribution is the definition of a partial inverse morphism ($\phi$). This mapping identifies intermediate lemmas in the classical proof and attempts to find their equivalents in the source logic.

A proof trace in the source modal logic, illustrating the use of modal operators like necessity (box) and possibility (diamond).

Strategy Transfer and Proof Reconstruction

A proof in the target logic is more than just a conclusion; it is a "trace" of the search strategy employed. By backward-translating this trace, the framework effectively translates the problem-solving strategy itself. This allows for the validation of heuristics, such as "unit resolution," across different logical systems.

The authors demonstrate this through the Wise Man Puzzle, a classic epistemic logic benchmark. When solved in the classical target logic, the proof can be reconstructed in a readable modal format. This process significantly prunes the search space, reducing the number of relevant axioms from 26 down to 6.

Extracted figure from page 5 of Logic Morphisms as a Framework for Backward Transfer of Lemmas and Strategies in Some Modal and Epistemic Logics

Key Results and Theoretical Foundations

The framework's validity is grounded in specific theoretical conditions (Theorems 1 and 2) that ensure the soundness of the partial inverse mapping. Key achievements include:

  • Interpretability: Proofs are presented in the original language of the problem, making them accessible to human experts.
  • Strategy Validation: The framework successfully replicates specialized modal resolution results using a generalized approach.
  • Formal Conjecture: The authors propose that a backward translation always exists for these proofs, providing a formal proof for "simple formulas."

Limitations and Future Directions

While promising, the current framework faces challenges in extending to more complex systems like Linear Temporal Logic (LTL) or First-Order Modal Logic, which require more sophisticated morphisms. Additionally, while the theoretical foundation for "simple formulas" is established, the general completeness conjecture remains an open problem. Future work will focus on fully automating the selection of the most "natural" source-logic lemmas when multiple valid translations exist.

Summary updated

BibTeX
@inproceedings{caferra1991logic,
  author = {Ricardo Caferra and Stéphane Demri and Michel Herment},
  title = {{Logic Morphisms as a Framework for Backward Transfer of Lemmas and Strategies in Some Modal and Epistemic Logics}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1991},
}
Figure