Preserving Consistency Across Abstraction Mappings

Josh D. Tenenberg

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.

A set of first-order logic axioms representing a domain of kitchen objects, illustrating the complexity and potential for disjointness in original theories.

Methodology: Restricted Predicate Mappings

Josh D. Tenenberg proposes a solution through "restricted predicate mappings." This involves two steps:

  1. 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$).
  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.

Equation (5) defining the semantic mapping: the extension of an abstract predicate is the union of the extensions of its specializations.

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

BibTeX
@inproceedings{tenenberg1987preserving,
  author = {Josh D. Tenenberg},
  title = {{Preserving Consistency Across Abstraction Mappings}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1987},
}
Figure