An ASP Approach to Generate Minimal Countermodels in Intuitionistic Propositional Logic

Camillo FiorentiniIJCAI 2019 · DOI

TL;DR

This paper presents a novel approach using Answer Set Programming (ASP) to automatically generate minimal countermodels for formulas in Intuitionistic Propositional Logic (IPL). By formalizing the problem of finding minimal countermodels as an ASP program, the authors provide a declarative and modular method that can be extended to other intermediate logics.

What Problem Does This Paper Address?

When a formula is not provable in Intuitionistic Propositional Logic (IPL), it means there exists a finite Kripke model that falsifies it. These falsifying models, called countermodels, are valuable for understanding why a formula fails, aiding in debugging and error analysis, similar to how failing test cases help in software development. However, existing methods often produce large, complex countermodels. The challenge this paper addresses is the generation of minimal countermodels, specifically minimizing the number of "worlds" in the Kripke model. This minimality is crucial for making countermodels easily understandable and useful as "certificates" of non-validity. While minimality has been studied for classical logics, it's less explored for intuitionistic logic, where countermodels can be more intricate.

Methods

The core of the paper's contribution lies in its novel ASP-based approach. Instead of directly generating Kripke models, the authors first define a notion of "p-worlds," which are specific subsets of the subformulas of the goal formula. These p-worlds are designed to satisfy certain closure properties that mimic the behavior of worlds in a Kripke model.

The ASP program is then constructed in two parts:

  1. Goal(G): This part encodes the specific formula G for which a countermodel is sought. It translates the formula's subformulas into ASP atoms.
  2. Gen: This is the main generator component. It uses ASP's declarative nature to search for a complete G-saturated set of p-worlds. A G-saturated set ensures that for any formula A → B not "forced" in a world W, there exists another world Z in the set that witnesses this failure. The ASP program leverages built-in arithmetic and bitwise operations for efficient representation of sets and their relationships.

The ASP solver (clingo) then finds answer sets of this program, which correspond to complete G-saturated sets. The minimality of the countermodel is achieved by instructing the ASP solver to minimize the number of worlds in the generated model. This approach is modular, allowing for extensions to other intermediate logics by simply adding ASP constraints for their specific frame conditions.

Datasets

Not discussed in the paper. The paper focuses on generating countermodels for arbitrary formulas in IPL and does not rely on pre-existing datasets for training or evaluation. However, it does present experimental results on standard benchmarks like Nishimura formulas and formulas from the Intuitionistic Logic Theorem Proving (ILTP) Library.

Key Insights and Ideas

  • ASP as a Declarative Model Generator: The paper demonstrates the power of ASP not just for reasoning but for generating structured models (Kripke models) in a declarative and modular fashion.
  • "P-worlds" as Building Blocks: The introduction of "p-worlds" (subsets of subformulas with closure properties) significantly prunes the search space compared to considering all possible subsets of subformulas. This is a key optimization.
  • G-Saturation for Countermodel Properties: The concept of G-saturation formalizes the necessary conditions for a set of p-worlds to constitute a valid countermodel, ensuring that the required witnesses for falsifying implications are present.
  • Modularity for Intermediate Logics: The ASP framework's inherent modularity allows for straightforward extension to other intermediate logics by adding specific frame condition constraints, a significant advantage over traditional prover extensions.
  • Minimality via ASP Optimization: Leveraging ASP's built-in minimization capabilities directly addresses the core problem of generating minimal countermodels, rather than relying on post-processing or complex search strategies.

Key Results

  • The paper presents an ASP program that successfully generates minimal countermodels for formulas in Intuitionistic Propositional Logic.
  • Experimental results on Nishimura formulas and ILTP Library benchmarks show that the number of p-worlds considered is significantly smaller than the total number of subformula subsets, making the approach feasible.
  • The generated countermodels are proven to be minimal in terms of the number of worlds.
  • The ASP approach is shown to be modular and extensible to other intermediate logics, such as Gödel-Dummett logic, by adding specific frame condition constraints. For example, adding a "linear frame" constraint allows for countermodels in GD logic.

Limitations and Future Work

  • Scalability: While the approach is efficient for many formulas, the paper notes that for "bigger instances" (larger or more complex formulas), computation might not terminate within reasonable time limits (e.g., 60 seconds).
  • Generalization to Other Logics: While the framework is modular, the paper defers an in-depth classification of frame conditions expressible in ASP for future work.
  • Other Notions of Minimality: The authors plan to investigate other notions of minimality beyond the number of worlds, as discussed in related literature.
  • Multi-modal and Temporal Logics: Future work includes extending the approach to handle multi-modal and temporal logics.

Summary updated

BibTeX
@inproceedings{fiorentini2019asp,
  author = {Camillo Fiorentini},
  title = {{An ASP Approach to Generate Minimal Countermodels in Intuitionistic Propositional Logic}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.24963/ijcai.2019/232},
}

Loading related content...

Figure