Blocked Clauses in First-Order Logic

Benjamin Kiesl, Martin Suda, Martina Seidl, Hans Tompits, Armin Biere

Introduction

In the domain of automated theorem proving, the efficiency of a solver often depends heavily on the quality of the input formula. Preprocessing—the phase where a formula is simplified before the main search begins—is a critical component of modern solvers. In the context of Boolean Satisfiability (SAT), Blocked Clause Elimination (BCE) has emerged as one of the most potent simplification techniques. A clause is considered "blocked" if all potential resolutions involving it result in tautologies, rendering the clause redundant for determining satisfiability.

While BCE is well-understood in propositional logic, lifting this technique to the more expressive realm of First-Order Logic (FOL) presents significant theoretical and algorithmic challenges. FOL introduces variables, quantifiers, and the equality predicate, which complicate the syntactic checks used in SAT. This paper, originally presented at LPAR-21, details the first successful extension of BCE to FOL and its implementation in the Vampire theorem prover.

Methodology: Lifting BCE to First-Order Logic

The core challenge in extending BCE to FOL lies in the concept of resolution. In propositional logic, resolution is straightforward. In FOL, however, resolution requires unification—finding a substitution of variables that makes two literals identical.

Blocked Clauses without Equality

The authors define "blocked clauses" in FOL using the concept of $L$-resolvents. A clause $C$ is blocked on a literal $L \in C$ if all possible $L$-resolvents of $C$ are valid (i.e., they are tautologies). Unlike the propositional case, where one only checks a single resolution partner, the FOL definition must account for all clauses in the formula that could potentially unify with $L$. The authors prove that removing such clauses preserves satisfiability, providing a formal basis for redundancy.

Equality-Blocked Clauses

The presence of the equality predicate ($\approx$) adds further complexity, as it introduces implicit logical connections between terms. To address this, the authors utilize a technique called "flattening." Flattening transforms complex terms into a series of variable-based equality constraints (e.g., replacing $P(f(a))$ with $x \approx f(a) \lor P(x)$). By applying BCE to these flattened formulas, the prover can identify redundancies that are otherwise obscured by the properties of identity.

Algorithmic Efficiency

For a preprocessing technique to be viable, it must be computationally efficient. The authors provide a polynomial-time algorithm to detect blocked clauses. They demonstrate that instead of checking every possible resolution—which could be computationally explosive—it is sufficient to check a quadratically-bounded subset of resolutions.

Experimental Evaluation

The proposed techniques were evaluated using the TPTP (Thousands of Problems for Theorem Provers) library, version 6.4.0. The dataset comprised 15,942 first-order benchmarks, including both Conjunctive Normal Form (CNF) and general first-order formulas. Approximately 73% of these problems involved equality.

The researchers implemented BCE as a preprocessing module within the Vampire theorem prover. They also tested its impact as a standalone preprocessor for other leading provers, including E and CVC4.

Key Results and Insights

The empirical results underscore the effectiveness of BCE in FOL:

  • Significant Pruning: BCE successfully removed 11.72% of all clauses across the TPTP library, substantially reducing the search space for the provers.
  • Instant Solutions: Remarkably, 113 satisfiable formulas were solved instantly by the preprocessor alone, as the entire set of clauses was reduced to an empty set.
  • Prover Enhancement: The addition of BCE led to a measurable increase in the number of problems solved by other provers. Most notably, CVC4 solved an additional 105 problems when BCE was enabled.
  • Satisfiability Performance: The gains were particularly significant for satisfiable instances. Finding models is traditionally more difficult for FOL provers than finding proofs of unsatisfiability; BCE helps bridge this gap.

Beyond performance metrics, the paper offers several theoretical insights. The authors show that BCE is a "super-technique" that encompasses and extends existing methods like Pure-Predicate Elimination (PPE) and Unused-Definition Elimination (UDE). They also observe the "fragility" of the search space: because theorem provers rely on complex heuristics, removing a redundant clause can occasionally lead the prover away from a successful path, though the overall impact remains overwhelmingly positive.

Conclusion

The extension of Blocked Clause Elimination to First-Order Logic represents a significant advancement in automated reasoning. By providing a formal framework for identifying redundancy in the presence of unification and equality, the authors have equipped FOL provers with a powerful new tool. Future work includes exploring "inprocessing" and investigating how BCE interacts with other simplification techniques like variable elimination.

Summary updated

BibTeX
@inproceedings{kiesl2017blocked,
  author = {Benjamin Kiesl and Martin Suda and Martina Seidl and Hans Tompits and Armin Biere},
  title = {{Blocked Clauses in First-Order Logic}},
  booktitle = {Lpar},
  year = {2017},
  doi = {10.29007/c3wq},
}
Figure