Introduction
In the field of artificial intelligence, non-monotonic reasoning describes the ability of a system to revise its conclusions in the face of new, potentially contradictory evidence. A classic example is the assumption that a bird can fly until it is identified as an ostrich. In the 1980s, John McCarthy’s "circumscription" emerged as a primary method for formalizing this process by minimizing the extent of "abnormality" predicates. However, traditional circumscription faced a significant structural limitation: the "policy" governing which predicates to minimize and which to vary was defined externally to the logic itself. This metamathematical approach prevented AI systems from reasoning about their own default assumptions.
In this preliminary report, Vladimir Lifschitz introduces Circumscriptive Theories, a framework that internalizes these reasoning policies directly into the logical language through the use of policy axioms.
The Problem: Externalized Policies
To implement circumscription effectively, a human designer traditionally had to specify a policy—a set of instructions determining which predicates were minimized and which functions or predicates were allowed to vary during that minimization. Because these instructions existed outside the formal logic, the system's reasoning strategy was effectively hard-coded. This lack of introspection made it difficult for systems to handle complex, dynamic environments where the rules for prioritizing information might need to change based on context.
Lifschitz addresses this by asking whether a circumscription policy can be described using the same axioms used to describe the world, thereby unifying the domain knowledge and the reasoning strategy into a single theory.
The Circumscriptive Framework
The core innovation of Lifschitz’s framework is the introduction of new constants into the logical language that represent the policy itself:
- Policy Axioms ($V_{PC}$): The framework introduces propositional constants, denoted as $V_{PC}$, which are interpreted as: "Constant $C$ is allowed to vary while predicate $P$ is being minimized."
- Second-Order Semantics: The semantics of these theories are defined using second-order predicate logic. For every predicate $P$, the framework constructs a formula ($Min_P$) that mathematically defines the condition of minimality based on the $V_{PC}$ constants present in the axioms.
- Pointwise Minimality: The framework adopts a "pointwise" approach to minimality. This involves examining the impossibility of changing a predicate's value from true to false at a specific point without violating the underlying axioms.
By treating these $V_{PC}$ terms as standard parts of the knowledge base, the reasoning policy becomes a set of facts that the system can manipulate, derive, or even revise.
Key Insights and Modular Reasoning
By bringing the policy into the logic, several advanced reasoning capabilities become possible:
Reasoning About Priorities
Systems can now utilize axioms to deduce their own priorities. For example, an axiom could state that if a specific source is deemed reliable, the system should prioritize its data over another source ($Source1\_Reliable \supset V[ab1 : ab2]$). This allows for dynamic priority shifts based on evidence rather than static, pre-defined hierarchies.
Modular Abnormality
In earlier iterations of circumscription, the set of varying predicates was often global and rigid. Lifschitz’s framework allows each "abnormality" predicate to maintain its own specific list of variables. This modularity makes it significantly easier to build and scale complex formalizations incrementally.
Safety of Pure Policy Axioms
The paper introduces "pure" policy axioms—those containing only $V_{PC}$ symbols. Lifschitz demonstrates that adding these to a theory is "safe" (Proposition 3), meaning they can lead to new non-monotonic conclusions without causing the system to lose existing theorems derived from the base logic.
Results and Theoretical Contributions
The report successfully establishes a model-theoretic definition of a circumscriptive theory, where models are defined by their minimality relative to specific preorders. Lifschitz demonstrates the expressive power of this framework by showing how it handles prioritized circumscription—where certain defaults are weighted more heavily than others—simply through the addition of appropriate axioms.
Furthermore, the paper introduces the concept of "generating sets." These are finite sets of first-order formulas that can represent complex second-order minimizations, providing a potential pathway toward making these theories more computationally tractable.
Limitations and Future Research
As a preliminary report, the paper acknowledges several areas for further development:
- Computational Complexity: The reliance on second-order logic poses challenges for decidability. While generating sets offer a partial solution, the general problem of efficient computation remains open.
- Scope: Much of the current discussion is restricted to "propositional" policies. Future work is expected to expand the formalism to more complex predicate versions and provide full proofs for the theorems presented.
- Implementation: Moving from the theoretical framework to a practical AI implementation requires further research into how these policy axioms interact with existing automated theorem provers.
Summary updated