Abstract
In nonmonotonic reasoning, adding new information can lead to the retraction of previously held conclusions. While this flexibility is essential for modeling common-sense reasoning, it often introduces unintended side effects where formalisms produce "excessively strong" or counter-intuitive results. Vladimir Lifschitz introduces the concept of restricted monotonicity as a formal property to evaluate and validate nonmonotonic logic systems. By distinguishing between parameters and assertions, this property ensures that refining a domain description with more specific assumptions does not inadvertently invalidate existing knowledge.
Introduction
In classical logic, reasoning is monotonic: the set of conclusions drawn from a set of axioms only grows as more axioms are added. However, human reasoning is inherently nonmonotonic. We often make default assumptions—such as "birds fly"—which we must retract upon learning specific exceptions, like the fact that a particular bird is a penguin.
While nonmonotonicity is a requirement for artificial intelligence, early formalisms for action and change often suffered from "over-minimization." In these systems, the logic might jump to a conclusion not because it is supported by evidence, but because the internal mechanics of the logic (such as minimizing predicates) force a specific, often arbitrary, model of the world. Lifschitz addresses this by proposing a sanity check: if we are simply adding more specific details about a problem's parameters, we should not lose the assertions we have already justified.
The Framework of Restricted Monotonicity
Lifschitz defines a declarative formalism through three components:
- Sentences ($S$): The underlying language.
- Postulates ($P$): The axioms or rules provided to the system.
- Consequence Operator ($Cn$): The mapping that determines conclusions from postulates.
The core innovation is the division of the language into parameters and assertions. Parameters are additional postulates that narrow down the possible states of a domain (e.g., initial conditions in a story), while assertions are the conclusions of interest.
A theory satisfies restricted monotonicity if, whenever we add more parameters to a set of postulates, the set of resulting assertions either grows or remains the same. This ensures that adding information about the "input" of a problem does not cause the system to retract "outputs" that were already logically sound.
Application to AI Formalisms
The paper evaluates three major AI formalisms against this criterion:
1. Circumscription
Circumscription is a method of nonmonotonic reasoning that "minimizes" the extension of certain predicates, such as an "abnormality" predicate ($Ab$). Lifschitz demonstrates that circumscription can fail the restricted monotonicity test if the parameters contain symbols that are being "varied" or "circumscribed." He proves that if parameters are kept separate from these varied symbols, the theory remains restrictedly monotone, explaining why certain circumscription policies produce "ghost" conclusions while others remain robust.
2. Extended Logic Programs
Using the framework of "negation as failure," logic programs are a staple of AI knowledge representation. Lifschitz introduces a technical condition called a signing—a specific way of partitioning atoms within a program. He proves that if a program can be signed relative to its parameters, it will behave monotonically, providing a clear guideline for developers to avoid unintended retractions.
3. Language $\mathcal{A}$
Language $\mathcal{A}$ is a high-level language designed specifically for describing actions and their effects. Lifschitz provides a formal proof that every domain description in Language $\mathcal{A}$ inherently satisfies restricted monotonicity regarding its value propositions (initial conditions). This result validates the design of $\mathcal{A}$, showing why it successfully avoids the pitfalls found in lower-level temporal logics.
Key Insights: The Failure of "Minimizing Change"
A significant insight of the paper is the critique of the "minimize change" policy in early temporal logics. In some systems, if an action is known to make a fact $F$ false, the logic might conclude that $F$ was initially false simply to minimize the total number of changes occurring in the timeline. This violates restricted monotonicity; if we were to later add the parameter that $F$ was initially true, the entire model of the past would shift. Lifschitz’s property identifies these flaws as a failure to distinguish between auxiliary mechanics and observable assertions.
Conclusion and Future Work
Restricted monotonicity serves as a vital diagnostic tool for the development of nonmonotonic logics. While Lifschitz acknowledges that not all nonmonotonic reasoning must be restrictedly monotone (as some problems are not "parametric" by nature), the property is essential for theories of action and change.
Future research in the field continues to use these principles to ensure that as knowledge bases grow in complexity, they do not repeat the "over-minimization" mistakes of the past. The challenge remains in identifying the optimal boundary between parameters and general postulates in increasingly large and complex AI systems.
Summary updated