Non-Monotonic Reasoning: Reasoning with Incomplete Information

Introduction

Classical logic is monotonic: adding new information never invalidates previous conclusions. However, real-world reasoning is often non-monotonic: new information can invalidate previous conclusions. Non-monotonic reasoning provides formal frameworks for reasoning with incomplete information, defaults, and exceptions. This article explores non-monotonic reasoning techniques and applications.

Monotonic vs Non-Monotonic

Monotonic Reasoning

Property: If Γ ⊨ φ, then Γ ∪ {ψ} ⊨ φ

Meaning: Adding premises doesn’t invalidate conclusions

Example:

Γ = {All birds fly, Tweety is a bird}
Γ ⊨ Tweety flies

Γ' = Γ ∪ {Tweety is a penguin}
Γ' ⊨ Tweety flies (still true)

Non-Monotonic Reasoning

Property: Γ ⊨ φ but Γ ∪ {ψ} ⊭ φ

Meaning: Adding premises can invalidate conclusions

Example:

Γ = {Typically birds fly, Tweety is a bird}
Γ ⊨ Tweety flies (by default)

Γ' = Γ ∪ {Tweety is a penguin}
Γ' ⊭ Tweety flies (exception to default)

Default Logic

Definition

Default Rule: (φ : ψ) / χ

Meaning: If φ is true and ψ is consistent, conclude χ

Example:

(Bird(x) : Flies(x)) / Flies(x)
"If x is a bird and it's consistent that x flies, conclude x flies"

Semantics

Extension: Maximal set of conclusions consistent with defaults

Process:

1. Start with facts
2. Apply defaults that are applicable
3. Add conclusions
4. Repeat until fixed point

Example

Facts: Bird(tweety), Penguin(tweety)
Defaults:
  (Bird(x) : Flies(x)) / Flies(x)
  (Penguin(x) : ¬Flies(x)) / ¬Flies(x)

Process:
1. Bird(tweety) is true, Flies(tweety) is consistent → Flies(tweety)
2. Penguin(tweety) is true, ¬Flies(tweety) is consistent → ¬Flies(tweety)
3. Conflict: Both Flies(tweety) and ¬Flies(tweety)
4. Multiple extensions (non-deterministic)

Circumscription

Idea

Principle: Minimize extension of predicates

Meaning: Assume only what’s necessary

Example:

Facts: Bird(tweety)
Circumscription: Minimize Flies
Result: Tweety doesn't fly (unless stated)

Formal Definition

Circumscription: Minimize predicate P in formula φ

Process:

1. Find minimal models of φ
2. In minimal models, P has smallest extension

Closed World Assumption (CWA)

Definition

CWA: What’s not known to be true is false

Meaning: Assume complete knowledge

Example:

Facts: Parent(tom, bob)
CWA: ¬Parent(tom, ann) (not stated, so false)

Limitations

Problem: Doesn’t handle incomplete information well Solution: Use open world assumption for incomplete domains

Abductive Reasoning

Definition

Abduction: Infer best explanation for observations

Process:

1. Observe facts
2. Generate hypotheses explaining facts
3. Select best hypothesis

Example:

Observation: Grass is wet
Hypotheses: It rained, sprinkler was on, someone watered
Best: It rained (most likely)

Belief Revision

Problem

Challenge: How to update beliefs when new information arrives?

Approach: Belief revision theory

AGM Postulates

Postulates for rational belief revision:

1. Closure: Revised beliefs are closed under logical consequence
2. Success: New information is in revised beliefs
3. Preservation: Old beliefs retained if consistent
4. Consistency: Revised beliefs are consistent
5. Extensionality: Revision depends only on logical content

Practical Applications

Diagnosis

Application: Diagnose faults from symptoms Approach: Abductive reasoning to find best explanation

Planning

Application: Generate plans achieving goals Approach: Non-monotonic reasoning with defaults

Knowledge Representation

Application: Represent incomplete knowledge Approach: Defaults, circumscription, CWA

Glossary

Abduction: Inferring best explanation Belief Revision: Updating beliefs with new information Circumscription: Minimizing predicate extension Closed World Assumption: What’s not known is false Default Logic: Logic with default rules Default Rule: Rule with exceptions Extension: Set of conclusions from defaults Monotonic: Adding premises doesn’t invalidate conclusions Non-Monotonic: Adding premises can invalidate conclusions Open World Assumption: What’s not known is unknown

Practice Problems

Problem 1: Formalize “Typically birds fly, but penguins don’t” in default logic.

Solution:

(Bird(x) : Flies(x)) / Flies(x)
(Penguin(x) : ¬Flies(x)) / ¬Flies(x)

Problem 2: Explain why classical logic is monotonic.

Solution: In classical logic, if Γ ⊨ φ, then φ is true in all models of Γ. Adding new premises Γ ∪ {ψ} only restricts the models (to those satisfying ψ), so φ remains true in all models of Γ ∪ {ψ}.

Problem 3: Describe how belief revision handles conflicting information.

Solution: Belief revision uses AGM postulates to rationally update beliefs. When new information conflicts with old beliefs, the revision process minimally changes beliefs to accommodate the new information while maintaining consistency.

Related Resources

• Non-Monotonic Reasoning: https://en.wikipedia.org/wiki/Non-monotonic_logic
• Default Logic: https://en.wikipedia.org/wiki/Default_logic
• Circumscription: https://en.wikipedia.org/wiki/Circumscription_(logic)
• Closed World Assumption: https://en.wikipedia.org/wiki/Closed-world_assumption
• Belief Revision: https://en.wikipedia.org/wiki/Belief_revision
• Abductive Reasoning: https://en.wikipedia.org/wiki/Abductive_reasoning
• Formal Logic: https://plato.stanford.edu/entries/logic-classical/
• Knowledge Representation: https://en.wikipedia.org/wiki/Knowledge_representation_and_reasoning
• Reasoning: https://en.wikipedia.org/wiki/Reasoning
• Artificial Intelligence: https://en.wikipedia.org/wiki/Artificial_intelligence
• Automated Reasoning: https://en.wikipedia.org/wiki/Automated_reasoning
• Formal Methods: https://plato.stanford.edu/entries/formal-methods/
• Logic Programming: https://en.wikipedia.org/wiki/Logic_programming
• Ontologies: https://en.wikipedia.org/wiki/Ontology_(information_science)
• Semantic Web: https://en.wikipedia.org/wiki/Semantic_Web

Conclusion

Non-monotonic reasoning provides essential tools for reasoning with incomplete information, defaults, and exceptions. By extending classical logic with default rules, circumscription, and belief revision, non-monotonic reasoning enables more realistic reasoning about the world.

Understanding non-monotonic reasoning is essential for anyone working with knowledge representation, AI systems, or reasoning about incomplete information. The combination of classical logic with non-monotonic extensions creates powerful reasoning systems.