World Library  
Flag as Inappropriate
Email this Article

Non-monotonic logic

Article Id: WHEBN0000341086
Reproduction Date:

Title: Non-monotonic logic  
Author: World Heritage Encyclopedia
Language: English
Subject: Logic programming, Default logic, Defeasible logic, Non-classical logic, Artificial intelligence
Collection: Belief Revision, Formal Epistemology, Logic, Non-Classical Logic, Reasoning
Publisher: World Heritage Encyclopedia

Non-monotonic logic

A non-monotonic logic is a formal logic whose consequence relation is not monotonic. Most studied formal logics have a monotonic consequence relation, meaning that adding a formula to a theory never produces a reduction of its set of consequences. Intuitively, monotonicity indicates that learning a new piece of knowledge cannot reduce the set of what is known. A monotonic logic cannot handle various reasoning tasks such as reasoning by default (consequences may be derived only because of lack of evidence of the contrary), abductive reasoning (consequences are only deduced as most likely explanations), some important approaches to reasoning about knowledge (the ignorance of a consequence must be retracted when the consequence becomes known), and similarly, belief revision (new knowledge may contradict old beliefs).


  • Abductive reasoning 1
  • Reasoning about knowledge 2
  • Belief revision 3
  • Proof-theoretic versus model-theoretic formalizations of non-monotonic logics 4
  • See also 5
  • References 6
  • External links 7

Abductive reasoning

Abductive reasoning is the process of deriving the most likely explanations of the known facts. An abductive logic should not be monotonic because the most likely explanations are not necessarily correct. For example, the most likely explanation for seeing wet grass is that it rained; however, this explanation has to be retracted when learning that the real cause of the grass being wet was a sprinkler. Since the old explanation (it rained) is retracted because of the addition of a piece of knowledge (a sprinkler was active), any logic that models explanations is non-monotonic.

Reasoning about knowledge

If a logic includes formulae that mean that something is not known, this logic should not be monotonic. Indeed, learning something that was previously not known leads to the removal of the formula specifying that this piece of knowledge is not known. This second change (a removal caused by an addition) violates the condition of monotonicity. A logic for reasoning about knowledge is the autoepistemic logic.

Belief revision

Belief revision is the process of changing beliefs to accommodate a new belief that might be inconsistent with the old ones. In the assumption that the new belief is correct, some of the old ones have to be retracted in order to maintain consistency. This retraction in response to an addition of a new belief makes any logic for belief revision to be non-monotonic. The belief revision approach is alternative to paraconsistent logics, which tolerate inconsistency rather than attempting to remove it.

Proof-theoretic versus model-theoretic formalizations of non-monotonic logics

Proof-theoretic formalization of a non-monotonic logic begins with adoption of certain non-monotonic rules of inference, and then prescribes contexts in which these non-monotonic rules may be applied in admissible deductions. This typically is accomplished by means of fixed-point equations that relate the sets of premises and the sets of their non-monotonic conclusions. Defaults logics and autoepistemic logic are the most common examples of non-monotonic logics that have been formalized that way.[1]

Model-theoretic formalization of a non-monotonic logic begins with restriction of the semantics of a suitable monotonic logic to some special models, for instance, to minimal models, and then derives the set of non-monotonic rules of inference, possibly with some restrictions in which contexts these rules may be applied, so that the resulting deductive system is sound and complete with respect to the restricted semantics. Unlike some proof-theoretic formalizations that suffered from well-known paradoxes and were often hard to evaluate with respect of their consistency with the intuitions they were supposed to capture, model-theoretic formalizations were paradox-free and left little, if any, room for confusion about what non-monotonic patterns of reasoning did they cover. Examples of proof-theoretic formalizations of non-monotonic reasoning, which revealed some undesirable or paradoxical properties or did not capture the desired intuitive comprehensions, that have been successfully (consistent with respective intuitive comprehensions a with no paradoxical properties, that is) formalized by model-theoretic means include first-order circumscription, closed-world assumption, and autoepistemic logic.[1]

See also


  • N. Bidoit and R. Hull (1989) "Minimalism, justification and non-monotonicity in deductive databases," Journal of Computer and System Sciences 38: 290-325.
  • G. Brewka (1991). Nonmonotonic Reasoning: Logical Foundations of Commonsense. Cambridge University Press.
  • G. Brewka, J. Dix, K. Konolige (1997). Nonmonotonic Reasoning - An Overview. CSLI publications, Stanford.
  • M. Cadoli and M. Schaerf (1993) "A survey of complexity results for non-monotonic logics" Journal of Logic Programming 17: 127-60.
  • F. M. Donini, M. Lenzerini, D. Nardi, F. Pirri, and M. Schaerf (1990) "Nonmonotonic reasoning," Artificial Intelligence Review 4: 163-210.
  • M. L. Ginsberg, ed. (1987) Readings in Nonmonotonic Reasoning. Los Altos CA: Morgan Kaufmann.
  • Horty, J. F., 2001, "Nonmonotonic Logic," in Goble, Lou, ed., The Blackwell Guide to Philosophical Logic. Blackwell.
  • W. Lukaszewicz (1990) Non-Monotonic Reasoning. Ellis-Horwood, Chichester, West Sussex, England.
  • C.G. Lundberg (2000) "Made sense and remembered sense: Sensemaking through abduction," Journal of Economic Psychology: 21(6), 691-709.
  • D. Makinson (2005) Bridges from Classical to Nonmonotonic Logic, College Publications.
  • W. Marek and M. Truszczynski (1993) Nonmonotonic Logics: Context-Dependent Reasoning. Springer Verlag.
  • A. Nait Abdallah (1995) The Logic of Partial Information. Springer Verlag.
  1. ^ a b Suchenek, Marek A. (2011), "Notes on Nonmonotonic Autoepistemic Propositional Logic", Zeszyty Naukowe (Warsaw School of Computer Science) (6): 74–93 .

External links

This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.

Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.