Hostname: page-component-586b7cd67f-g8jcs Total loading time: 0 Render date: 2024-11-22T14:55:32.308Z Has data issue: false hasContentIssue false
  • English
  • Français

Default non-monotonic logic

Published online by Cambridge University Press:  07 July 2009

Peter Mott
Peter Mott
Affiliation:
Department of Philosophy, University of Lancaster, Bailrigg, Lancaster
Get access Rights & Permissions [Opens in a new window]

Abstract

This paper is a review of certain non-monotonic logics, which I call default non-monotonic logics. These are logics which exploit failure to prove. How each logic uses this basic idea is explained, and examples given. The emphasis is on leading ideas explained through examples: technical detail is avoided. Four non-monotonic logics are discussed: Reiter's default logic, McCarthy's circumscription, McDermott's modal non-monotonic logic, and Clarks's completed database. The first two are treated in some detail. The recent Hanks-McDermott criticism of non-monotonic logic is discussed, and some conclusions drawn about the prospects for non-monotonic logic. Recommendations for further reading are given.

Type
Research Article
Information
The Knowledge Engineering Review , Volume 3 , Issue 4 , December 1988 , pp. 265 - 284
Copyright
Copyright © Cambridge University Press 1988

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Barendregt, H 1981. Lambda Calculus, North Holland, Amsterdam.Google Scholar
Barwise, J and Etchmendy, J, 1987. Truth and the Liar, Oxford.Google Scholar
Barwise, J and Perry, J, 1983. Situations and Attitudes, MIT Press.Google Scholar
Bossu, G and Siegal, P, 1985. “Saturation, non-monotonic reasoning and the closed world assumption”, Artificial Intelligence (25) 13–64.CrossRefGoogle Scholar
Boolos, G and Jeffrey, R, 1982. Computability & Logic, Cambridge.Google Scholar
Blair, H A, 1982. “The recursion-theorectic complexity of the semantics of predicate logic as a programming language,” Information and Control (54) 25–47.CrossRefGoogle Scholar
Bridge, J, 1977. Beginning model theory, Oxford Logic Guides, Oxford.Google Scholar
Bundy, A, 1983. The Computer Modelling of Mathematical Reasoning, Academic Press, London.Google Scholar
Chang, C C and Keisler, H J, 1976. Model Theory, North-Holland.Google Scholar
Clark, K L, 1978. “Negation as failure,” In: Gallaire & Minker op cit 293.CrossRefGoogle Scholar
Cohen, P, 1987. “The control of reasoning under uncertainty: a discussion of some programs,” The Knowledge Engineering Review (2) 6–25.Google Scholar
Davis, M, 1980. “The mathematics of non-monotonic reasoning,” Artificial Intelligence (13) 73–80.CrossRefGoogle Scholar
Etherington, D, Mercer, R and Reiter, R, 1985. “On the adequacy of predicate circumscription for closed world reasoning,” Computational Intelligence (1) (1985) 11–15.CrossRefGoogle Scholar
Fitting, M, 1985. “A Kripke-Kleene semantics for logic programs,” Journal of Logic Programming (4) 295–312.CrossRefGoogle Scholar
Fitting, M, 1986. “Notes on the mathematical aspects of Kripke's theory of truth,” Notre Dame Journal of Formal Logic (27) 75–88.Google Scholar
Flannagan, T, 1986. “The consistency of negation as failure,” Journal of Logic Programming (3) 93–115.CrossRefGoogle Scholar
Gabbay, D, 1982. “Intuitionistic bases for non-monotonic logic,” In: Proc. Conference on Automated Deduction Springer Lecture Notes in Computer Science (6) 260–273.CrossRefGoogle Scholar
Gallaire, H and Minker, J, (Ed.), 1978. Logic and Databases, Plenum Press, New York.Google Scholar
Gibbins, P, 1988. Logic with Prolog (Oxford).Google Scholar
Hanks, S and McDermott, D, 1987. “Nonmonotonic logic and temporal projection,” Artificial Intelligence (33) 379–412.CrossRefGoogle Scholar
Hilpinen, R, (ed.), 1981. New Studies in Deontic Logic, North Holland, Amsterdam.CrossRefGoogle Scholar
Hughes, G E and Cresswell, M, 1968. An Introduction to Modal Logic, Methuen, London.Google Scholar
Jaffar, J, Lassez, J-L and Lloyd, J W, 1983. “Completeness of the negation as failure rule,” Proceedings of the 8th IJCAI, Karlsruhe, 500–506.Google Scholar
Konolige, K, 1988. “On the relation between default and autoepistemic logic,” Artificial Intelligence (35) 343–382.CrossRefGoogle Scholar
Kunen, K, 1987. “Negation in logic programming,” Journal of Logic Programming (4) 289–308.CrossRefGoogle Scholar
Kyburg, H, 1970. Probability and Inductive Logic, Macmillan, London.Google Scholar
Lifschitz, V, 1985a. “Closed world data bases and circumscription,” Artificial Intelligence (27) 229–335.CrossRefGoogle Scholar
Lifschitz, V, 1985b. “Pointwise circumscription: preliminary report,” Proc. IJCAI-85, Los Angeles, Ca., 406–10.Google Scholar
Lifschitz, V, 1986. “On the satisfiability of circumscription,” Artificial Intelligence (28) 17–28.CrossRefGoogle Scholar
Lloyd, J W, 1984. Foundations Of Logic Programming, Springer-Verlag, Berlin.CrossRefGoogle Scholar
McCarthy, J, 1980. “Circumscription—a form of non-monotonic reasoning,” Artificial Intelligence (13) 27–39.CrossRefGoogle Scholar
McCarthy, J, 1986. “Applications of circumscription to formalising common-sense knowledge,” Artificial Intelligence (28) 89–116.CrossRefGoogle Scholar
McDermott, D V and Doyle, J, 1980. “Non-monotonic logic I,” Artificial Intelligence (13) 41–72.CrossRefGoogle Scholar
McDermot, D V, 1983. “Non-monotonic logic II,” JACM (29) 33–57.Google Scholar
McDermott, D V, 1982. “A temporal logic for reasoning about processes and plans,” Cognitive Sci. (6) 101–155.Google Scholar
Mendelson, E, 1987. Introduction to Mathematical Logic (3rd Edition), Wadsworth, California.CrossRefGoogle Scholar
Minsky, M, 1975. “A framework for representing knowledge,” Winston, P (Ed.), The Psychology of Computer Vision McGraw Hill, New York.Google Scholar
Mill, J S, 1843. A System Of Logic.Google Scholar
Moore, R C, 1985. “Semantic considerations on non-monotonic logic,” Artificial Intelligence (25) 75–94.CrossRefGoogle Scholar
Mott, P L, 1987. “A theorem on the consistency of circumscription,” Artificial Intelligence (31) 87–98.CrossRefGoogle Scholar
Nute, D, 1988. “LDR: a logic for defeasible reasoning,” ACMC Research Report 01–0013, University of Georgia.Google Scholar
Perlis, D and Minker, J, 1986. “Completeness results for circumscription,” Artificial Intelligence (28) 29–42.CrossRefGoogle Scholar
Popper, K R, 1972. Objective Knowledge, OUP, London.Google Scholar
Raphael, B, 1971. “The frame problem in problem solving systems,” In: Findler, N V & Meltzer, B (Eds.), AI and Heuristic Programming, Edinburgh U P, Edinburgh.Google Scholar
Reiter, R, 1980a. “A logic for default reasoning,” Artificial Intelligence (13) 81–132.CrossRefGoogle Scholar
Reiter, R, 1980b. “Equality and domain closure in first order data bases,” JACM (27) 235–249.CrossRefGoogle Scholar
Reiter, R, 1978. “On closed world data bases,” In: Gallaire & Minker, op cit 55–77.CrossRefGoogle Scholar
Reiter, R, 1978b. “Deductive question answering on relational databases,” In: Gallaire and Minker, op cit 149–177.CrossRefGoogle Scholar
Reiter, R and Crisculo, G. 1983. “Some representational issues in default reasoning,” Int. J. of Computat. Maths (9) 1–13.Google Scholar
Rescher, N and Urquhart, A, 1971. Temporal Logic, Springer Verlag, Berlin.CrossRefGoogle Scholar
Robbin, J W, 1969. Mathematical Logic, Benjamin, New York.Google Scholar
Schlipf, J, 1987a. “Decidability and definability with circumscription,” Annals of Pure and Applied Logic (35) 173–191.CrossRefGoogle Scholar
Schlipf, J, 1987b. “When is closed world reasoning tractable?” Department of Computer Science, University of Cincinati, Ohio 45221–0008, USA.Google Scholar
Shepherdson, J, 1984. “Negation as failure: a comparison of Clark's completed database and Reiter's closed world assumption,” Journal of Logic Programming (1) 51–79.CrossRefGoogle Scholar
Shepherdson, J, 1985. “Negation as failure II,” Journal of Logic Programming (2) 185–202.CrossRefGoogle Scholar
Shortliffe, E, 1976. Computer-Based Medical Consultations: MYCIN, Elsevier, New York.Google Scholar
Smets, Ph, Mamdani, E H, Dubois, D and Prade, H, 1988. Non-Standard Logics for Automated Reasoning, Academic Press, London.Google Scholar
Swinburne, R (Ed), 1974. The Justification of Induction, Oxford.Google Scholar
Tarski, A, 1944. “The semantic conception of truth” Philosophy & Phenomenological Research 4 341–376.CrossRefGoogle Scholar
Tarski, A, 1969a. Logic, Semantics, Metamathematics, Woodger, J H, (Ed.), Oxford.Google Scholar
Tarski, A, 1969b. “Truth and proof,” Scientific American 194 (6).Google Scholar
Turner, R, 1984. Logics for Artificial Intelligence, Ellis Horwood, New York.Google Scholar
Van Benthem, J, 1983. The Logic of Time, Reidel, Dordrecht.CrossRefGoogle Scholar
Van Dalen, D, 1985. Logic and Structure, Springer, Berlin.Google Scholar
Van Gelder, A, Ross, K and Schlipf, J S, 1988. “Unfounded sets and well-founded semantics for general logic programs,” 7th ACM Principles of Database Systems.CrossRefGoogle Scholar
Wojcik, M, 1987. “Methods of automatic reasoning using non-monotonic logics—examples of implementation”, Polish Academy of Sciences, ICS Report 610, Warsaw.Google Scholar