Abstract
The SEt Reasoning Facility (SERF) integrates mechanisms for propagating membership propositions, deriving relations between sets, and reasoning about closure and cardinality into an efficient utility package for reasoning about sets. Assertions about relations between sets are compiled into a constraint network defined entirely in terms of union, complement, and emptiness constraints. The constraint network supports multiple modes of inference, such as local propagation of membership propositions and graph search for set relations using a transitivity table. SERF permits closure assertions of the form "all members of set S are known" and utilizes this capability to permit selective applications of closed-world assumptions. Cardinality constraints are handled by a general quantity reasoner. An example from geologic interpretation illustrates the value of mutually constraining sources of information in a typical application of reasoning about sets in commonsense problem-solving.
Introduction
In the late 1980s, AI researchers identified that "commonsense" reasoning—the logic used to understand everyday scenarios—relies heavily on set operations. For example, if we know all green blocks are in a room and none are on a table, we can infer the table contains no green blocks. However, general-purpose theorem provers were often too slow for these tasks. The SEt Reasoning Facility (SERF) was developed to address this by providing a computationally efficient framework that integrates membership, cardinality, and ordinal relations.
Methodology
SERF represents sets as nodes in a constraint network, utilizing a Truth Maintenance System (TMS) to track dependencies and handle changes in knowledge dynamically. If a fact is retracted, the system automatically "un-derives" all consequences of that fact, ensuring the knowledge base remains consistent during dynamic changes.
Primitive Operations
To maintain efficiency, SERF compiles all complex set operations (such as intersection and difference) into two fundamental primitives: union and complement. This simplification allows the system to reason about any set expression through a uniform network structure. For instance, an intersection can be represented as the complement of the union of complements.
Propagation and Path Search
Inference in SERF occurs through two primary modes:
- Local Propagation: Membership facts (e.g., $x \in A$) propagate through the network. If $A \subseteq B$ and $x \in A$, the system immediately infers $x \in B$.
- Path Search: For broader relations, such as determining if $A \subseteq D$, the system performs a breadth-first search across the relational network. It uses a transitivity table to compose relations along paths, allowing it to derive new ordinal relationships between sets that are not directly connected.
Closure and Cardinality
SERF handles the "Closed World Assumption" by allowing sets to be "closed" (asserting all members are known). It manages cardinality through a "Quantity Lattice," which reasons about the number of elements without requiring explicit identification of every member. To handle the addition of new members to a closed set, SERF uses an "Exactly N" assertion; if a new member is found, the old assertion is retracted and replaced with "Exactly N+1," maintaining logical consistency via the TMS.
Key Insights
- Vividness over Completeness: SERF prioritizes "vivid" reasoning—fast, local inference—over mathematical completeness. This trade-off is essential for real-time commonsense applications where a quick, though potentially incomplete, answer is better than a slow, exhaustive one.
- Mutual Constraint: A core principle of SERF is that membership information and ordinal relations (like subsets) mutually constrain each other. This allows the system to detect contradictions or infer new facts from multiple sources of information simultaneously.
Applications and Results
The system was evaluated on qualitative examples:
- Geologic Interpretation: SERF successfully modeled how rock formations change due to erosion and deposition. For instance, if erosion ($TE$) is a subset of the initial surface ($S_1$), and $S_2$ is the new surface, SERF could correctly identify when $S_2$ was a proper superset of the newly exposed rocks.
- Utility Reasoning Program (URP): In preference modeling, SERF's ability to constrain set members significantly reduced the combinatorial search space required to find valid assignments for variables.
Conclusion
While SERF is intentionally incomplete, its local propagation and efficient path search make it a powerful utility for practical AI applications. Future work aims to integrate more sophisticated quantity reasoners to handle complex numerical constraints on set sizes more robustly, further bridging the gap between symbolic set reasoning and numerical analysis.
Summary updated