Explain Logics for Non-Monotonic Reasoning

Non-monotonic reasoning is reasoning where adding new information can retract earlier conclusions. This contrasts with monotonic logics (where adding premises cannot invalidate previously derived conclusions). Non-monotonic logics are therefore designed to model common patterns like “defaults” (typically true unless contradicted), “exceptions,” and “reasoning under incomplete information.” 2

A useful way to structure “logics for non-monotonic reasoning” is to categorize them by the mechanism they use to choose which conclusions survive information changes:

• Circumscription: minimizes certain predicates to represent “what is not known to be true.”
• Default logic: applies defaults of the form “if prerequisites hold and it’s consistent to do so, conclude conclusion.”
• Autoepistemic logic: reasons about which statements are believed/consistent with the agent’s own beliefs.
• Stable model semantics / Answer Set Programming (ASP): gives semantics to logic programs by selecting “stable” models representing self-consistent sets of beliefs.

Key keyword: non-monotonicity; keyword: defaults; keyword: circumscription; keyword: defaults (in default logic); keyword: stable models.

Footnotes

1. Stanford Encyclopedia of Philosophy, “Nonmonotonic Logic” - https://plato.stanford.edu/entries/logic-nonmonotonic/ - Background definition and landscape of non-monotonic logic. ↩

2. Stanford Encyclopedia of Philosophy, “KLM and Rational Monotonicity” (related nonmonotonic consequence postulates within nonmonotonic logic discussions) - https://plato.stanford.edu/entries/logic-nonmonotonic/ - Discussion of postulates and rational behavior of non-monotonic consequence. ↩

3. Stanford Encyclopedia of Philosophy, “Circumscription” (within the nonmonotonic logic context) - https://plato.stanford.edu/entries/circumscription/ - Formal approach based on minimization. ↩

4. Stanford Encyclopedia of Philosophy, “Default Logic” - https://plato.stanford.edu/entries/logic-default/ - Overview of prerequisites/justifications and extension semantics. ↩

5. Stanford Encyclopedia of Philosophy, “Autoepistemic Logic” - https://plato.stanford.edu/entries/logic-autoepistemic/ - Belief/self-reference and fixed-point style semantics. ↩

6. Wikipedia, “Stable model semantics” - https://en.wikipedia.org/wiki/Stable_model_semantics - Definition via reduct and stable models; basis of ASP. ↩

1) Formal goal: capturing “inference with retraction”

In monotonic systems, we have the property:

• If $\\Gamma \\vdash \\varphi$, then for any $\\Delta$, $\\Gamma, \\Delta \\vdash \\varphi$.

In a non-monotonic logic, this implication fails: there can exist $\\Gamma,\\Delta$ such that $\\Gamma \\vdash \\varphi$ but $\\Gamma,\\Delta \\not\\vdash \\varphi$ (or equivalently, $\\varphi$ is no longer warranted). 2

A common formalization is to view a non-monotonic logic as defining a consequence relation $\\mathrel{\\vDash_{NM}}$ where “warranted conclusions” depend on the full knowledge state.

[callout tip]{type="tip"} title: "Pro Tip" content: "When studying a non-monotonic logic, always ask: what model/criterion selects which conclusions survive? The selection criterion is the logic’s core idea." type: "tip"

Footnotes

1. Stanford Encyclopedia of Philosophy, “Nonmonotonic Logic” - https://plato.stanford.edu/entries/logic-nonmonotonic/ - Background definition and landscape of non-monotonic logic. ↩

2. Stanford Encyclopedia of Philosophy, “KLM and Rational Monotonicity” (related nonmonotonic consequence postulates within nonmonotonic logic discussions) - https://plato.stanford.edu/entries/logic-nonmonotonic/ - Discussion of postulates and rational behavior of non-monotonic consequence. ↩

2) Circumscription logic: “minimize what you can”

Core idea

Circumscription introduces a way to represent defaults by minimizing “abnormality” or other predicates. Intuitively, we assume that certain properties are as false as possible unless forced to be true.

A typical pattern:

• Let $P$ be a “normal” predicate.
• Let $Ab$ indicate exceptions.
• If an exception is not derivable, minimize $Ab$ so that “exceptions are as rare as possible,” yielding default conclusions.

This approach is formally described by the circumscription scheme, which orders models by which predicates are “smaller” (under inclusion) while keeping other predicates fixed.

How minimization yields non-monotonicity

When new facts force $Ab$ to be true (or force a larger extension for minimized predicates), previously minimized choices may be invalid, causing previously derived default conclusions to be retracted—exactly the non-monotonic behavior desired.

keyword: circumscription; keyword: abnormality (Ab); keyword: minimization ordering; keyword: circumscribed model; keyword: retraction.

Footnotes

1. Stanford Encyclopedia of Philosophy, “Circumscription” (within the nonmonotonic logic context) - https://plato.stanford.edu/entries/circumscription/ - Formal approach based on minimization. ↩ ↩²

3) Default logic: explicit defaults with consistency conditions

Syntax (high level)

Default logic uses defaults of the form:

• $\\frac{\\text{Prerequisite} : \\text{Justification}}{\\text{Conclusion}}$

with the semantics that a default can be applied if:

1. its prerequisite holds, and
2. the justification is consistent with what is assumed to be derivable, and
3. the conclusion is then added.

Extension semantics

Default logic produces sets of conclusions called extensions (in effect, “possible stable belief sets” consistent with applying defaults). The key is that different choices about which defaults to apply (when justifications create conflicts) can yield multiple extensions.

[callout warning]{type="warning"} title: "Warning: extensions may be multiple or require careful attention" content: "In default logic, the same knowledge base can have several extensions; reasoning is often defined either skeptically (in all extensions) or credulously (in some extensions)." type: "warning"

Why it is non-monotonic

If new information invalidates a justification’s consistency, a default that used to apply may no longer be allowed, so its conclusion must be dropped. That is non-monotonicity by construction.

keyword: default; keyword: extension; keyword: skeptical reasoning; keyword: credulous reasoning; keyword: consistency of justification.

Footnotes

1. Stanford Encyclopedia of Philosophy, “Default Logic” - https://plato.stanford.edu/entries/logic-default/ - Overview of prerequisites/justifications and extension semantics. ↩ ↩² ↩³

4) Autoepistemic logic: self-consistency of beliefs

Autoepistemic logic introduces modal reasoning about what the agent knows/believes/accepts, allowing defaults like “if it is consistent that $\\varphi$, then assume $\\varphi$.”

In this style, non-monotonicity arises because conclusions depend on what is consistent with the agent’s own theory of beliefs, which changes when new axioms are added.

Mechanism

Roughly:

• the logic reasons with formulas that refer to the agent’s belief state (often via operators capturing “$\\varphi$ is believed” or “$\\varphi$ is consistent with what I believe”),
• and it uses fixed-point / stability ideas so that beliefs are mutually consistent.

This yields a controlled form of “defaults-as-assumptions” grounded in introspective consistency.

keyword: autoepistemic logic; keyword: belief modality; keyword: introspective consistency; keyword: equilibrium-like semantics; keyword: retraction.

Footnotes

1. Stanford Encyclopedia of Philosophy, “Autoepistemic Logic” - https://plato.stanford.edu/entries/logic-autoepistemic/ - Belief/self-reference and fixed-point style semantics. ↩ ↩²

5) Stable model semantics / ASP: logic programs as non-monotonic theories

Stable models (high level)

Stable model semantics assigns meaning to logic programs (rules) by selecting models that are “stable” under a reduct transformation. The transformation removes negation-as-failure based on which atoms are assumed true, and then stable models are those that coincide with the minimal model of the transformed positive program.

This framework captures default-like negation:

• “If not provable, assume false” (negation-as-failure), but does so with formal semantics.

Non-monotonicity from self-consistency

Because stability depends on which atoms are assumed true, adding facts/rules can change the reduct and therefore change the stable models. Conclusions supported by one stable model may disappear under another stable model set after new information—hence non-monotonic behavior.

[callout tip]{type="tip"} title: "Pro Tip" content: "Think of a stable model as a complete ‘world view’ consistent with the program; non-monotonic inference then follows the chosen world views." type: "tip"

keyword: stable model semantics; keyword: ASP; keyword: negation-as-failure; keyword: reduct; keyword: least model.

Footnotes

1. Wikipedia, “Stable model semantics” - https://en.wikipedia.org/wiki/Stable_model_semantics - Definition via reduct and stable models; basis of ASP. ↩ ↩²

6) Proof-theoretic vs model-theoretic viewpoints

Different non-monotonic logics can be understood as:

• Model-theoretic: define which models are admissible (e.g., circumscribed models, stable models). 2
• Proof/derivation-theoretic: define inference procedures that depend on consistency or justified assumptions (e.g., default application subject to consistency).

A unifying perspective:

• Non-monotonicity is often implemented by constraints on admissibility (minimization, stability, consistency of justifications/beliefs), not merely by weakening monotonic inference rules.

keyword: admissible models; keyword: admissibility constraints; keyword: consistency-dependent inference; keyword: selection operator; keyword: context sensitivity.

Footnotes

1. Stanford Encyclopedia of Philosophy, “Circumscription” (within the nonmonotonic logic context) - https://plato.stanford.edu/entries/circumscription/ - Formal approach based on minimization. ↩

2. Wikipedia, “Stable model semantics” - https://en.wikipedia.org/wiki/Stable_model_semantics - Definition via reduct and stable models; basis of ASP. ↩

3. Stanford Encyclopedia of Philosophy, “Default Logic” - https://plato.stanford.edu/entries/logic-default/ - Overview of prerequisites/justifications and extension semantics. ↩

7) Relationship to rational/non-monotonic consequence postulates

Beyond specific formalisms, non-monotonic reasoning has been studied abstractly through postulates (axioms about desirable behavior of a non-monotonic consequence relation). These postulates characterize classes of consequence relations satisfying properties like relevance to premises, cautiousness, and “rational” behavior (e.g., variants of rational monotonicity).

Even if you do not commit to a particular syntax, these postulates tell you what kinds of non-monotonic inferences are “well-behaved,” guiding comparisons between formalisms.

keyword: rational postulates; keyword: KLM framework; keyword: monotonicity-like rationality; keyword: rational entailment; keyword: non-monotonic consequence.

Footnotes

1. Stanford Encyclopedia of Philosophy, “KLM and Rational Monotonicity” (related nonmonotonic consequence postulates within nonmonotonic logic discussions) - https://plato.stanford.edu/entries/logic-nonmonotonic/ - Discussion of postulates and rational behavior of non-monotonic consequence. ↩

8) Quick comparison of major non-monotonic logics

Footnotes

1. Stanford Encyclopedia of Philosophy, “Circumscription” (within the nonmonotonic logic context) - https://plato.stanford.edu/entries/circumscription/ - Formal approach based on minimization. ↩

2. Stanford Encyclopedia of Philosophy, “Default Logic” - https://plato.stanford.edu/entries/logic-default/ - Overview of prerequisites/justifications and extension semantics. ↩

3. Stanford Encyclopedia of Philosophy, “Autoepistemic Logic” - https://plato.stanford.edu/entries/logic-autoepistemic/ - Belief/self-reference and fixed-point style semantics. ↩

4. Wikipedia, “Stable model semantics” - https://en.wikipedia.org/wiki/Stable_model_semantics - Definition via reduct and stable models; basis of ASP. ↩