Compact Propositional Encodings of First-Order Theories

Deepak Ramachandran, Eyal Amir

Introduction

First-Order Logic (FOL) provides a powerful framework for expressing complex relationships, but its semi-decidable nature makes automated reasoning a significant challenge. A common strategy to leverage the efficiency of modern SAT solvers is propositionalization—the process of translating FOL theories into propositional logic. However, traditional "naive" methods often suffer from exponential size explosion. This paper introduces a novel partitioned propositionalization technique that produces compact encodings for specific decidable fragments of FOL, namely the Monadic and Ramsey classes.

The Challenge of Naive Propositionalization

Standard propositionalization techniques, dating back to the 1960s, typically involve grounding every predicate against every constant in a finite domain. While conceptually simple, this approach has two primary drawbacks: it requires a pre-defined domain and leads to a massive increase in the number of variables and clauses.

Table comparing FOL Theory to Naive Propositionalization, illustrating the expansion of quantifiers into large propositional formulas.

As shown in the table above, even simple existential or universal quantifiers result in complex propositional structures when grounded. For large domains, this "naive" approach quickly becomes computationally intractable due to the sheer volume of generated propositional variables.

Partitioned Propositionalization

The authors propose a "divide and conquer" strategy that exploits the internal structure of FOL theories. Their method follows three main steps:

  1. Partitioning: Axioms are grouped into a tree structure. Communication between partitions is restricted to shared symbols (the intersection language), following the principles of Craig’s Interpolation Theorem.
  2. Localized Translation:
  3. Monadic Class: For predicates with arity 1, the authors use special propositional symbols (e.g., $E_{\langle P,Q \rangle}$) to represent existential statements like $\exists x[P(x) \land Q(x)]$. Consistency axioms are added to ensure these symbols behave logically.
  4. Ramsey Class: Partitions are propositionalized relative only to constants appearing in their local scope or ancestors in the partition tree, significantly reducing the grounding space.
  5. Integration: These localized translations are combined into a single, equisatisfiable propositional theory.

Experimental Results

The proposed method was evaluated using the Pigeonhole Problem, a classic benchmark for automated reasoning. The results demonstrate that partitioned propositionalization scales far better than naive methods.

Performance graphs showing #Pigeons vs. Time and #Pigeons vs. #Vars for Ramsey, Monadic, and Naive encodings.

For the Ramsey class, the encoding size grew at a rate of $O(p \log p)$, while the Monadic class achieved linear growth $O(p)$. In contrast, the naive method exhibited $O(p^2)$ growth. Using the Zchaff SAT solver, the authors observed orders-of-magnitude speedups in running time. As illustrated in the performance graphs, these compact encodings prevented the memory exhaustion common in standard grounding techniques and allowed for the resolution of problems previously considered out of reach.

Conclusion and Future Work

By leveraging the structural properties of FOL theories, the authors have developed a method for generating compact propositional encodings that bypass the limitations of naive grounding. While currently focused on the Monadic and Ramsey classes, this approach provides a foundation for extending efficient propositionalization to broader fragments of First-Order Logic. Future research may explore automated partitioning strategies and the integration of these techniques into general-purpose theorem provers.

Summary updated

BibTeX
@inproceedings{ramachandran2005compact,
  author = {Deepak Ramachandran and Eyal Amir},
  title = {{Compact Propositional Encodings of First-Order Theories}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2005},
}
Figure