Compact Propositional Encodings of First-Order Theories

Abstract

A propositionalization of a theory in First-Order Logic (FOL) is a set of propositional sentences that is satisfiable iff the original theory is satisfiable. We cannot translate arbitrary FOL theories to propositional logic because FOL is only semi-decidable. However, when possible, it is often advantageous to do so because we can use optimized, efficient SAT solvers (e.g. [Moskewicz et al., 2001]) to solve the resulting SAT problem. Propositionalization is used frequently in Planning [Kautz and Selman, 1996], Relational Data Mining [Krogel et al., 2003], and Formal Verification [Kropf, 1999]. Current propositional encodings (naive prop.), based on [Gilmore, 1960], result in prohibitively large propositional encodings even for moderate applications and assume a known finite domain for the theory. However despite their drawbacks, they are the most efficient solutions known so far. Examples of naive prop. are given in Table 1. We briefly describe a novel, systematic approach to translating two important subsets of FOL into propositional logic. Our approach leverages structure in the FOL formulation to provide significantly more compact propositional encodings without requiring a finite fixed domain. Specifically, we present algorithms for translating two important decidable subsets of FOL: (1) function-free monadic, and (2) the Bernays-Schoenfinkel-Ramsey class (see [Borger et al., 1996]) in which all existential quantifiers must occur before all universal ones (all arity is allowed for predicates, with equality, but no functions). These subsets cover important problems in AI and computer science, such as expressive planning, data mining, constraint satisfaction, propositional modal logic, and quantified boolean formulae (QBF). Our algorithms generate propositional encodings of these subsets of FOL as follows. They start by grouping axiom sets into a tree of partitions following the approach of [Amir and McIlraith, 2004]. Then, they translate each partition separately using only a restricted set of constants that depend on