Abstract
Blocked clause elimination (BCE) is a powerful preprocessing technique in propositional logic that simplifies formulas by removing redundant clauses. Lifting BCE to first-order logic (FOL) is challenging due to the complexities of variables, unification, and equality. This paper introduces a generalization of BCE for FOL, provides a polynomial-time algorithm for its detection, and demonstrates its effectiveness through implementation in the Vampire theorem prover. Experimental results on the TPTP library show significant clause reduction and improved performance, particularly on satisfiable problems.
Introduction
Modern automated theorem provers (ATPs) rely heavily on preprocessing to simplify formulas before beginning the computationally intensive proof search. In the context of propositional logic (SAT solving), Blocked-Clause Elimination (BCE) has emerged as a highly successful technique. A clause is considered "blocked" if its resolution with any other clause on a specific literal always results in a tautology. Since blocked clauses are logically redundant, they can be safely removed without affecting the satisfiability of the formula.
Despite its success in SAT, BCE has historically been difficult to apply to First-Order Logic (FOL). The transition from propositional to first-order logic introduces variables and the equality predicate, both of which complicate the identification of redundancy. This paper addresses these theoretical hurdles, providing a robust framework for BCE in FOL.
The Challenge of First-Order Logic
In propositional logic, checking if a clause is blocked is straightforward: one simply checks all possible resolvents. In FOL, however, literals contain variables that can be instantiated in infinitely many ways through unification. A naive translation of BCE fails because multiple literals might unify at the ground level, which can break the mathematical guarantee of redundancy. Furthermore, the equality predicate introduces semantic equivalences (e.g., $a=b$) that standard syntactic unification cannot identify.
Generalizing Blocked Clauses
To overcome these challenges, the authors propose two distinct definitions for blocked clauses in FOL:
1. FOL Without Equality: L-resolvents
To handle variables correctly, the authors introduce the concept of L-resolvents. Instead of checking standard binary resolvents, the algorithm checks a candidate clause against all literals in a partner clause that can unify with the blocking literal simultaneously. If all such L-resolvents are tautologies, the clause is considered blocked and can be removed.
2. FOL With Equality: Flattening
To account for the equality predicate, the authors utilize a technique called flattening. For instance, a literal $P(a)$ is transformed into $x \neq a \lor P(x)$. By flattening literals before resolution, the algorithm can recognize terms that are semantically equal even if they do not syntactically unify. These "flat L-resolvents" allow the detection of equality-blocked clauses.
Implementation and Complexity
Checking all possible subsets of unifiable literals could potentially lead to exponential time complexity. To ensure the technique is practical for real-world theorem proving, the authors developed a polynomial-time algorithm. This algorithm utilizes unification closures (and congruence closures for equality) to efficiently verify blocked status. The technique was implemented as a preprocessing component within the Vampire theorem prover.
Experimental Evaluation
The authors evaluated the implementation using 15,942 first-order benchmark formulas from the TPTP (Thousands of Problems for Theorem Provers) library (v6.4.0). The results highlight the prevalence and impact of blocked clauses:
- Clause Reduction: BCE eliminated 11.72% of the approximately 300 million clauses across the benchmark suite.
- Prevalence: At least one blocked clause was found in 59% of the problems tested.
- Direct Solutions: BCE alone solved 113 satisfiable problems during the preprocessing phase by reducing the formulas to an empty set.
- Prover Enhancement: When integrated with provers like Vampire, E, and CVC4, BCE significantly boosted performance on satisfiable instances. Notably, CVC4 solved 68 additional satisfiable problems that were previously unsolvable without BCE.
Discussion and Limitations
While BCE is a powerful tool, its impact is not uniform. The authors observed that while it helps solve more problems overall, it occasionally hinders the search for unsatisfiable instances. This is likely due to the "fragile" nature of heuristic search spaces; a redundant clause might occasionally serve as a helpful "stepping stone" for a prover's specific search strategy. Additionally, for performance reasons, the current implementation uses an approximation for equality checks rather than a full recursive congruence closure.
Beyond simple elimination, BCE acts as a "master" simplifier, naturally simulating other established techniques such as Pure Predicate Elimination (PPE) and Unused Definition Elimination (UDE) at the CNF level.
Conclusion
This work successfully bridges the gap between propositional and first-order blocked clause elimination. By providing a sound theoretical basis and an efficient algorithm, the authors have added a valuable tool to the automated reasoning toolkit. Future research directions include "dynamic BCE," where clauses are eliminated during the proof search rather than just at the start, and "blocked-clause addition," which explores whether adding specific redundant clauses can actually guide provers toward solutions more quickly.
Summary updated