Non-Monotonic Reasoning

A formal system introduced by Raymond Reiter for reasoning with default rules. A default rule has the form P: J / C, meaning: if prerequisite P is believed, and justification J is consistent with our beliefs, then we can conclude C. This allows conclusions to be drawn in the absence of contradictory information. A key concept is an extension, which is a maximal set of beliefs that can be derived by applying all applicable defaults. Different extensions represent different coherent sets of default assumptions, modeling ambiguity in commonsense situations.

A modal logic for reasoning about an agent's own beliefs and knowledge, formalized by Robert C. Moore. It extends propositional logic with a modal operator L, where Lp is interpreted as "I believe p" or "p is known." It allows an agent to draw conclusions based on the absence of knowledge. For example, ¬Lp → q means "if I don't believe p, then conclude q." The semantics are defined via stable expansions, which are sets of beliefs that are internally justified and closed under the agent's own reasoning about its beliefs.

A formalism introduced by John McCarthy that minimizes the extension of certain predicates to handle exceptions. The core idea is to prefer models where the set of objects satisfying an "abnormality" predicate (e.g., Ab(x)) is as small as possible. This allows rules to be written as defaults (e.g., "Birds fly") with explicit exceptions (e.g., "Penguins are abnormal birds"). Circumscription minimizes abnormality, allowing the conclusion that a typical bird flies unless proven otherwise. It is a form of model preference semantics for non-monotonic logic.

A practical subsystem that records dependencies between beliefs (nodes) and their justifications. When new information contradicts an existing belief, the TMS performs belief revision by retracting the dependent conclusion and finding a new consistent set of beliefs. There are two primary types:

• Justification-based TMS (JTMS): Uses network of nodes and justifications; detects contradictions.
• Assumption-based TMS (ATMS): Labels beliefs with the sets of assumptions (environment) under which they hold. This enables efficient switching between contexts without re-derivation, which is critical for implementing non-monotonic reasoners.

A fundamental rule of thumb in database systems and logic programming where any fact not explicitly known to be true is assumed to be false. Formally, for a set of facts KB, we assume ¬P for every ground atom P not entailed by KB. This is inherently non-monotonic: adding P to KB forces the retraction of ¬P. It is the default mode for systems like Prolog and SQL databases. The opposite is the Open-World Assumption (OWA), used in Semantic Web reasoning, where a lack of information implies unknown, not false.

A modern, declarative programming paradigm based on the stable model semantics of logic programming. ASP programs consist of rules that may include negation as failure (not), allowing default reasoning. A solver computes answer sets (stable models), which are sets of atoms representing self-consistent beliefs. Key features enabling non-monotonicity:

• Default negation: a :- b, not c. means "a if b and it's not provable that c."
• Choice rules: {a; b; c} 1. allows modeling alternatives.
• Constraints: :- a, b. rules out any answer set containing both a and b. ASP is widely used for knowledge-intensive search and configuration problems.

Non-monotonic reasoning enables systems to manage default business rules that hold unless an exception is triggered. For example, a shipping system might assume 'all packages are delivered via ground transport' by default. If a package is marked as 'perishable' or 'international,' the system retracts the default conclusion and applies an air freight rule instead. This mirrors human operational reasoning where standard procedures are followed until a special case requires a different action.

Regulatory frameworks and internal policies often contain defeasible rules—rules that can be overridden by more specific regulations. A non-monotonic engine can model this hierarchy. For instance, a base rule might state 'employee data cannot be shared.' A more specific policy for the HR department could allow sharing with payroll providers, defeating the general rule in a controlled context. As regulations change (e.g., new GDPR amendments), the system can integrate new rules that invalidate prior compliant states, ensuring continuous auditability.

In technical support or medical diagnostics, reasoning is inherently provisional. A system might start with a default assumption (e.g., 'the network is up') and suggest common fixes. If those actions fail, new evidence is added (e.g., 'ping fails to gateway'), forcing the system to retract the initial assumption and explore deeper network layer issues. This mimics expert troubleshooting, where conclusions are iteratively refined—not simply accumulated—as new test results arrive.

Fraud detection models often work with beliefs about normal behavior that must be updated. A transaction might be initially flagged as suspicious based on amount and location (a default rule). However, if the system later retrieves context that the customer is on a verified business trip, it must withdraw the fraud alert. Non-monotonic reasoning maintains a justification trail for each alert, allowing investigators to see why a suspicion was raised and why it was later dismissed, which is critical for audit trails and reducing false positives.

Supply chain planners operate with default expectations about supplier reliability, shipping routes, and lead times. A non-monotonic system can model these as assumptions. When a disruption occurs (e.g., a port closure), this new fact invalidates the planned routes. The system must then re-plan based on the new world state, possibly retracting many derived conclusions about delivery dates and inventory levels. This capability is key for autonomous supply chain agents that must dynamically replan in real-time without human intervention.

Legal contracts are rife with conditional clauses and exceptions. A non-monotonic reasoner can parse a contract's logic: a standard clause may grant certain rights, but a subsequent 'provided that' or 'except as noted in Section 5.2' clause creates an exception that overrides it. By formally modeling this defeasible structure, AI systems can more accurately assess contractual obligations, liabilities, and the impact of amendments, where adding a new clause can fundamentally change the interpretation of existing ones.

A Truth Maintenance System (TMS) is a critical subsystem that enables non-monotonic reasoning by recording the logical justifications for each derived conclusion. When new, contradictory information is added, the TMS efficiently identifies and retracts all dependent beliefs, maintaining a consistent set of inferences. This mechanism is what allows systems to 'change their mind' and is foundational for implementing belief revision and assumption-based reasoning.

Default Logic is a formal, non-monotonic framework introduced by Raymond Reiter to model commonsense reasoning with defaults. It extends classical logic with default rules of the form: 'If A is true, and it is consistent to assume B, then conclude C.'

• Example Rule: 'If something is a bird, and it is consistent that it can fly, then infer it can fly.'
• This allows conclusions based on typical cases (e.g., birds fly) that can be overridden by exceptions (e.g., penguins, ostriches). It provides a precise mathematical model for the defeasible inferences central to non-monotonic reasoning.

These are fundamental assumptions that dictate how systems handle unknown information, directly influencing reasoning monotonicity.

• Closed-World Assumption (CWA): Any fact not explicitly known to be true is assumed false. This is the default in traditional databases and many rule-based systems (e.g., SQL, Prolog). It is inherently non-monotonic—adding a new fact (e.g., 'Ostrich(BigBird)') can invalidate a previous assumption (e.g., '¬CanFly(BigBird)').

• Open-World Assumption (OWA): The lack of knowledge about a fact does not imply it is false; its truth value is simply unknown. This is central to Semantic Web standards (RDF, OWL) and description logic. Reasoning under OWA is typically monotonic.

Abductive Reasoning is the process of inferring the most likely explanation for a set of observations. Often termed 'inference to the best explanation,' it is inherently hypothetical and defeasible.

• Process: Given an observation O and a theory T, find a hypothesis H such that T + H logically entails O, and H is the simplest/most plausible account.
• Example: A doctor observes symptoms (fever, cough) and abduces a likely diagnosis (influenza), which may be retracted if a new test (negative for flu) arrives. This cycle of hypothesize-test-retract aligns closely with non-monotonic belief update patterns.

Defeasible Logic is a rule-based non-monotonic formalism designed to handle conflicting information through explicit defeat mechanisms. It distinguishes between strict rules (always apply), defeasible rules (typically apply), and defeaters (block other rules).

• Key Mechanism: Rules have a superiority relation to resolve conflicts. If Rule A and Rule B conflict, and A is superior to B, then A defeats B.
• Use Case: Ideal for modeling legal reasoning, regulations, and policies where rules have exceptions and precedence (e.g., 'Company policy applies, unless a union contract specifies otherwise').

Autoepistemic Logic, developed by Robert Moore, is a non-monotonic logic for reasoning about an agent's own knowledge and beliefs. It extends classical logic with a modal operator L (interpreted as 'I believe' or 'I know').

• Core Idea: An agent can draw conclusions based on the absence of belief. For example, 'If I do not believe I have a sister, then I conclude I am an only child.'
• This introspective capability allows agents to model commonsense introspection and stabilize their beliefs in a fixed point, making it powerful for modeling rational but resource-bounded agents.