Abstract
Automated reasoning in complex domains often requires abstraction to manage combinatorially intractable search spaces. However, mapping specific predicates to general ones can introduce logical contradictions, known as the "false proof" problem. This paper introduces "restricted predicate mappings," a formal approach to abstraction that guarantees the consistency of the abstract theory. By filtering clauses based on their derivability in the original domain, this method ensures that every abstract theorem corresponds to a valid specialization in the original space.
Introduction: The Challenge of Logic-Based Abstraction
In the field of AI and automated theorem proving, the complexity of real-world domains often leads to search spaces that are too large to explore efficiently. Abstraction serves as a primary strategy to mitigate this, mapping a complex problem into a simpler "abstract" space where a solution can be found more easily.
However, a major hurdle is the "false proof" problem. If an original theory contains disjointness rules—for example, stating that "Bottles" and "Glasses" are distinct categories—an abstraction that merges them into a single "Container" predicate may inherit these rules, leading to a logical contradiction where a "Container" is asserted to be disjoint from itself. Such inconsistencies render the abstract space useless for guiding search.
Methodology: Restricted Predicate Mappings
Josh D. Tenenberg proposes a solution through "restricted predicate mappings." This involves two steps:
- Predicate Mapping ($f$): A many-to-one mapping where multiple predicate symbols from the original language ($L_1$) are mapped to a single symbol in the abstract language ($L_2$).
- Restricted Mapping ($g$): A syntactic filter that determines which clauses are included in the abstract theory. A clause is included only if it is a positive clause (no negated literals) or if every specialization of that clause is derivable from the original theory.
This filtering process effectively removes the axioms that distinguish the predicates being merged, thereby eliminating the source of potential inconsistencies.
Key Insights and Semantic Intuition
The paper's primary contribution is the formal proof that consistency is preserved. Tenenberg provides a semantic bridge by defining the meaning of an abstract predicate as the union of the extensions of its constituent predicates.
This construction ensures two vital properties:
- The Consistency Guarantee: If the original theory is consistent, a valid model always exists for the abstract theory.
- Downward-Solution Property: Unlike many abstraction techniques that only focus on the "upward" path (finding a solution in the abstract space), this method ensures that every theorem found in the abstract space has a valid, corresponding specialization in the original space.
Results and Practical Implications
The restricted mapping successfully resolves the false proof problem, allowing for intuitive inferences (e.g., if both bottles and glasses are "breakable," the abstract theory correctly maintains that "containers are breakable") without risking logical collapse.
However, the author acknowledges a practical limitation: determining if a clause should be included in the abstract theory is an undecidable problem in first-order logic. To address this, Tenenberg suggests using heuristic bounding—limiting the depth of the proof search. While this may result in a "weaker" abstract theory with fewer theorems, it maintains the essential guarantee of consistency.
Conclusion
By providing a formal framework for consistency-preserving abstraction, Tenenberg's work addresses a critical bottleneck in automated reasoning. The restricted predicate mapping allows for the creation of simplified models that remain logically sound, providing a reliable foundation for hierarchical problem-solving in complex domains.
Summary updated