View source for Non-monotonic logic

{{Short description|Formal logic whose entailment relation is not monotonic}}
{{more footnotes needed|date=June 2008}}
A '''non-monotonic logic''' is a [[formal logic]] whose [[entailment]] relation is not [[Monotonicity of entailment|monotonic]]. In other words, non-monotonic logics are devised to capture and represent [[defeasible reasoning|defeasible inferences]], i.e., a kind of inference in which reasoners draw tentative conclusions, enabling reasoners to retract their conclusion(s) based on further evidence.<ref>{{cite web|last1=Strasser|first1=Christian|last2=Antonelli|first2=G. Aldo|title=Non-Monotonic Logic|url=http://plato.stanford.edu/entries/logic-nonmonotonic/|website=plato.stanford.edu/index.html|publisher=Stanford Encyclopedia of Philosophy|access-date=19 March 2015}}</ref>
Most studied formal logics have a monotonic entailment relation, meaning that adding a formula to the hypotheses never produces a pruning of its set of conclusions. Intuitively, monotonicity indicates that learning a new piece of knowledge cannot reduce the set of what is known. Monotonic logics cannot handle various reasoning tasks such as [[Default logic|reasoning by default]] (conclusions may be derived only because of lack of evidence of the contrary), [[abductive reasoning]] (conclusions are only deduced as most likely explanations), some important approaches  to reasoning about knowledge (the ignorance of a conclusion must be retracted when the conclusion becomes known), and similarly, [[belief revision]] (new  knowledge may contradict old beliefs).

==Abductive reasoning==

[[Abductive reasoning]] is the process of deriving a sufficient explanation of the known facts. An abductive logic should not be monotonic because the likely explanations are not necessarily correct. For example, the 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 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 theory|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. [[Default logic]] and [[autoepistemic logic]] are the most common examples of non-monotonic logics that have been formalized that way.<ref name="Suchenek">{{citation
 | last1 = Suchenek | first1 = Marek A.
 | title = Notes on Nonmonotonic Autoepistemic Propositional Logic
 | pages = 74–93
 | publisher = Warsaw School of Computer Science
 | journal = Zeszyty Naukowe
 | issue = 6
 | year = 2011
 | url = http://zeszyty-naukowe.wwsi.edu.pl/zeszyty/zeszyt6/NotesonNonmonotonicAutoepistemicPropositionalLogic.pdf}}.</ref>

[[model theory|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,<ref>{{citation |first1=Marek A. |last1=Suchenek |title=Applications of Lyndon Homomorphism Theorems to the theory of minimal models. |journal=International Journal of Foundations of Computer Science |issue= 1|pages=49–59 |date=1990 |volume=01 |doi=10.1142/S0129054190000059 |publisher=World Scientific}}</ref><ref>{{citation |first1=Michael |last1=Gelfond |first2=Halina |last2=Przymusinska |first3=Teodor |last3=Przymusinski |title=On the relationship between CWA, minimal model, and minimal herbrand model semantics |journal=International Journal of Intelligent Systems  |publisher=Wiley |volume= 5 |issue= 5|pages=549–564 |date=1990 |doi=10.1002/int.4550050507  |doi-access=free }}</ref> and then derives a set of non-monotonic [[rules of inference]], possibly with some restrictions on which contexts these rules may be applied in, so that the resulting deductive system is [[Soundness|sound]] and [[Completeness (logic)|complete]] with respect to the restricted [[semantics]].<ref name="Suchenek2">{{citation
 | last1 = Suchenek | first1 = Marek A.
 | title = First-order syntactic characterizations of minimal entailment, domain-minimal entailment, and Herbrand entailment
 | pages = 237–263
 | publisher = Kluwer Academic Publishers / Springer
 | journal =  [[Journal of Automated Reasoning]]
 | issue = 2
 | year = 1993
 | volume = 10
 | doi = 10.1007/BF00881837
 | url = https://www.deepdyve.com/lp/springer-journals/first-order-syntactic-characterizations-of-minimal-entailment-domain-f1OOm5TaaM| url-access = subscription
 }}.</ref> 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 they covered. 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 and with no paradoxical properties, that is) formalized by model-theoretic means include [[Circumscription (logic)|first-order circumscription]], [[closed-world assumption]],<ref name="Suchenek2" /> and [[autoepistemic logic]].<ref name="Suchenek" />

==See also==
{{Portal|Philosophy}}

* [[Logic programming]]
* [[Negation as failure]]
* [[Stable model semantics]]
* [[Rational consequence relation]]

==Notes==
{{reflist}}

==References==
*{{cite journal |first1=N. |last1=Bidoit |first2=R. |last2=Hull |title=Minimalism, justification and non-monotonicity in deductive databases |journal=[[Journal of Computer and System Sciences]] |volume=38 |issue= 2|pages=290–325 |date=1989 |doi= 10.1016/0022-0000(89)90004-4|doi-access=free }}
*{{cite book |first=G. |last=Brewka  |title=Nonmonotonic Reasoning: Logical Foundations of Commonsense |publisher=Cambridge University Press |date=1991 |isbn=978-0-521-38394-3 |url={{GBurl|S41BSy8Xk44C}}}}
*{{cite book |first1=G. |last1=Brewka |first2=J. |last2=Dix |first3=K. |last3=Konolige |title=Nonmonotonic Reasoning — An Overview |publisher=CSLI publications |location=Stanford |volume=73 |series=CSLI Lecture Notes  |date=1997 |isbn=9781881526834 |pages= |url=http://www.informatik.uni-leipzig.de/~brewka/papers/nonmonbook.ps}}
*{{cite journal |first1=M. |last1=Cadoli |first2=M. |last2=Schaerf |title=A survey of complexity results for non-monotonic logics |journal=[[Journal of Logic Programming]] |volume=17 |issue= 2–4|pages=127–60 |date=1993 |doi= 10.1016/0743-1066(93)90029-G|doi-access=free }}
*{{cite journal |first1=F.M. |last1=Donini |first2=M. |last2=Lenzerini |first3=D. |last3=Nardi |first4=F. |last4=Pirri |first5=M. |last5=Schaerf |title=Nonmonotonic reasoning |journal=Artificial Intelligence Review |volume=4 |issue= 3|pages=163–210 |date=1990 |doi=10.1007/BF00140676 |s2cid=23575942 |url=}}
*{{cite book |author1-link=Dov Gabbay |first=D.M. |last=Gabbay  |chapter=Theoretical foundations for non-monotonic reasoning in expert systems |chapter-url=https://link.springer.com/chapter/10.1007/978-3-642-82453-1_15 |doi=10.1007/978-3-642-82453-1_15 |editor-last=Apt |editor-first=K.R. |title= Logics and Models of Concurrent Systems |publisher=Springer |location=NATO ASI Series, Series F: Computer and Systems Sciences |volume=13 |date=1985 |isbn=978-3-642-82453-1 |pages=439–457 |url=}}
*{{cite book |editor-first=M.L. |editor-last=Ginsberg |title=Readings in Nonmonotonic Reasoning |publisher=Morgan Kaufmann |date=1987 |isbn=978-0-934613-45-3 }}
*{{cite book |first=J.F. |last=Horty |chapter=Nonmonotonic Logic |chapter-url= |editor-first=Lou |editor-last=Goble |title=The Blackwell Guide to Philosophical Logic |publisher=Wiley |date=2001 |isbn=978-0-631-20692-7 |pages= |url=}}
*{{cite book |first=W. |last=Łukaszewicz |title=Non-Monotonic Reasoning |publisher=Ellis-Horwood |date=1990 |isbn=978-0-13-624446-2 |pages= |url=}}
*{{cite journal |first=C.G. |last=Lundberg |title=Made sense and remembered sense: Sensemaking through abduction |journal=Journal of Economic Psychology |volume=21 |issue=6 |pages=691–709 |date=2000 |doi= 10.1016/S0167-4870(00)00027-1|s2cid=11723465 |url=https://pdfs.semanticscholar.org/cce4/b4fa69ed4c7cf997f1fbf38542c247bb19ea.pdf |archive-url=https://web.archive.org/web/20170907080541/https://pdfs.semanticscholar.org/cce4/b4fa69ed4c7cf997f1fbf38542c247bb19ea.pdf |archive-date=2017-09-07 }}
*{{cite book |first=D. |last=Makinson |title=Bridges from Classical to Nonmonotonic Logic |publisher=College Publications |date=2005 |isbn=9781904987000 |pages= |url=https://www.researchgate.net/publication/262934388}}
*{{cite book |first1=W. |last1=Marek |first2=M. |last2=Truszczynski |title=Nonmonotonic Logics: Context-Dependent Reasoning |publisher=Springer |date=1993 |isbn=978-3-662-02906-0 |url={{GBurl|W-apCAAAQBAJ}}}}
*{{cite book |first=A. Nait |last=Abdallah |title=The Logic of Partial Information |publisher=Springer |date=1995 |isbn=978-3-642-78160-5 |url={{GBurl|1QarCAAAQBAJ}}}}
*{{cite journal |first1=Marek A. |last1=Suchenek |title=First-order syntactic characterizations of minimal entailment, domain-minimal entailment, and Herbrand entailment |journal=Journal of Automated Reasoning|publisher=Kluwer Academic Publishers / Springer |issue= 2|pages=237–263 |date=1993 |volume=10 |doi=10.1007/BF00881837  |url=https://www.deepdyve.com/lp/springer-journals/first-order-syntactic-characterizations-of-minimal-entailment-domain-f1OOm5TaaM|url-access=subscription }}

==External links==
* {{cite SEP |url-id=logic-nonmonotonic |title=Non-monotonic logic |last=Antonelli |first=G. Aldo}}
* {{PhilPapers|category|nonmonotonic-logic}}
* {{InPho|idea|1208}}

{{Non-classical logic}}

[[Category:Belief revision]]
[[Category:Epistemic logic]]
[[Category:Non-classical logic]]
[[Category:Reasoning]]