Non-Monotonic Reasoning

A defeasible conclusion is a provisional inference that is accepted as true based on available evidence but can be overturned when new, conflicting information arrives. This is the core mechanism of non-monotonicity.

• Example: From 'Tweety is a bird,' we defeasibly conclude 'Tweety can fly.' If we later learn 'Tweety is a penguin,' the original conclusion is retracted.
• This contrasts with monotonic logic (e.g., classical first-order logic), where adding premises can only increase the set of provable conclusions, never decrease it.

Default rules encode typical, commonsense knowledge with exceptions. They have the form: 'In the absence of information to the contrary, assume X.'

• Structure: P : Q / R means 'If P is true, and it is consistent to assume Q, then conclude R.'
• Function: These rules allow a system to 'jump to conclusions' based on what is normally true, enabling efficient reasoning without complete knowledge.
• Critical Property: The system must track the justifications for conclusions derived from defaults so they can be invalidated if an exception (¬Q) is later discovered.

Belief revision is the formal process of integrating new information into an existing knowledge base (KB) in a minimal and consistent way when the new information contradicts old beliefs.

• Key Principle: When a contradiction arises, the system must decide which old beliefs to retract to restore consistency, prioritizing more certain or fundamental beliefs.
• AGM Postulates: A foundational set of rationality postulates (Alchourrón, Gärdenfors, Makinson) that define the properties of a rational belief revision operator.
• Application: This is not just deleting facts; it involves managing the entire web of logical dependencies to ensure the revised KB remains coherent.

The Closed World Assumption (CWA) is a powerful non-monotonic rule that states: 'If a fact cannot be proven from the knowledge base, assume it is false.'

• Contrast with OWA: This differs from the Open World Assumption of standard logic, where a lack of proof means 'unknown.'
• Use Case: It is fundamental to database querying and logic programming (e.g., Prolog). Querying for a fact not in the database returns false, not unknown.
• Non-Monotonicity: Adding new facts to the KB can change a previous 'false' conclusion to 'true,' demonstrating non-monotonic behavior.

Circumscription is a formal, model-theoretic approach to non-monotonic reasoning introduced by John McCarthy. It minimizes the extension of specified predicates, effectively assuming things are as 'normal' as possible.

• Minimization: It selects models of the KB where the set of objects satisfying certain predicates (e.g., Abnormal(x)) is minimal. We assume no abnormal instances unless forced by the KB.
• Result: This automatically implements default rules about 'typical' cases. For example, by minimizing Abnormal(x), we assume birds fly unless explicitly stated as abnormal.
• Formalism: It provides a precise second-order logic formula that captures the intended models of a non-monotonic theory.

Non-monotonic systems often reason by constructing and comparing arguments for and against conclusions. A conclusion is accepted only if its supporting arguments defeat all competing counter-arguments.

• Argument: A logical proof for a claim that may rely on defeasible premises (defaults).
• Defeat: An argument A defeats argument B if A undermines a premise of B or presents a direct contradiction.
• Dialectical Process: The system maintains a dynamic 'argumentation framework' where the status of claims (IN, OUT, UNDECIDED) changes as new arguments are introduced.
• Link to AI: This provides a robust, game-theoretic semantics for non-monotonic logics and is closely related to computational models of debate and legal reasoning.

Default reasoning is a specific, common form of non-monotonic logic where conclusions are drawn based on typical, rule-like assumptions that hold "by default" in the absence of specific contradictory information. It formalizes commonsense rules such as "birds typically fly." A system using default reasoning would conclude that a specific bird, Tweety, can fly, unless it later learns Tweety is a penguin. This is implemented through default rules with prerequisites, justifications, and consequents. Its computational frameworks, like Reiter's Default Logic, provide a formal system for managing these defeasible inferences.

Autoepistemic Logic is a non-monotonic logic designed to model an agent's beliefs about its own knowledge and ignorance. Introduced by Robert C. Moore, it extends classical logic with a modal operator L (interpreted as "is believed"). Its non-monotonicity arises from introspective reasoning: if something is not believed to be true (¬Lp), the agent can conclude it is false. This allows the system to make assumptions based on a lack of belief. For example, an agent can conclude it has no appointment at 2 PM because it does not believe it has one, but must retract that if new information arrives. It is crucial for modeling closed-world assumptions in knowledge bases.

Circumscription is a non-monotonic logic formalism, introduced by John McCarthy, that implements a formalized version of Occam's razor. It works by minimizing the extent of predicates—that is, it assumes that the only objects that satisfy a predicate are those that are forced to by the known facts. For example, in a knowledge base stating Block(A) and Block(B), circumscription would minimize the Block predicate to mean only A and B are blocks, unless explicitly stated otherwise. When new information is added (e.g., Block(C)), the minimized extension expands. This technique is used for commonsense reasoning in artificial intelligence, particularly for reasoning about actions and persistence (the frame problem).

Defeasible Logic is a rule-based non-monotonic logic that distinguishes between strict rules (which always hold), defeasible rules (which typically hold), and defeaters (which block conclusions). Its inference mechanism is designed to resolve conflicts between competing rules through a superiority relation. A conclusion is defeasibly provable if it is supported by a rule whose antecedent is proven, and all opposing rules are either not applicable or defeated by a superior rule. This provides a computationally tractable and direct method for handling conflicting information, making it popular in areas like legal reasoning, contract law modeling, and semantic web rule languages.

Belief Revision is the study of how a rational agent should change its set of beliefs (a belief set or knowledge base) when incorporating new information that may be inconsistent with existing beliefs. Governed by the AGM postulates (Alchourrón, Gärdenfors, and Makinson), it provides formal constraints for operations like expansion (adding consistent info), contraction (removing a belief), and revision (adding potentially conflicting info while maintaining consistency). While non-monotonic reasoning focuses on deriving defeasible conclusions, belief revision focuses on managing the core knowledge base itself after new evidence arrives. The two fields are deeply connected, as revision operations often rely on non-monotonic inference to determine what to retract.

Answer Set Programming (ASP) is a declarative programming paradigm and knowledge representation language based on the stable model semantics of logic programming. It is inherently non-monotonic due to its use of negation as failure. In ASP, a problem is encoded as a logic program whose answer sets (stable models) correspond to solutions. Adding new facts or rules can fundamentally change the set of answer sets, removing previous solutions—a non-monotonic effect. ASP is used for solving complex combinatorial search problems, planning, and knowledge-intensive reasoning where defaults and exceptions are naturally expressed, such as in product configuration or policy reasoning.