Copyright © 1999 Massachusetts Institute of Technology
Nonmonotonic logics are used to formalize plausible reasoning. They allow more general reasoning than standard logics, which deal with universal statements. For example, standard logics can easily represent the argument:
| All men are mortal |
| Socrates is a man |
| Therefore, Socrates is mortal |
| ((∀ x)(Man(x) ==> Mortal(x)); Man(Socrates) |
| Mortal(Socrates) |
but cannot represent reasoning such as:
| Birds typically fly |
| Tweety is a bird |
| Therefore, Tweety (presumably) flies |
Such arguments are characteristic of commonsense reasoning, where default rules and the absence of complete information are prevalent.
The most salient feature of nonmonotonic reasoning is that the conclusion of a nonmonotonic argument may not be correct. For example, if Tweety is a penguin, it is incorrect to conclude that Tweety flies. Nonmonotonic reasoning often requires jumping to a conclusion and subsequently retracting that conclusion as further information becomes available. Thus, as the set of assumptions grows, the set of conclusions (theorems) may shrink. This reasoning is called nonmonotonic in contrast to standard logic, which is monotonic: as one's set of assumptions grows, one's set of theorems grows as well. (Formally, a system is monotonic if for any two theories A and B, whenever A is a subset of B, the theorems of A are a subset of the theorems of B.)
All systems of nonmonotonic reasoning are fundamentally concerned with the issue of consistency: ensuring that conclusions drawn are consistent with one another and with the assumptions.
Default Logic (Reiter 1980) introduces a default rule, an inference rule consisting of an assumption, an appeal to the consistency of some formula, and a conclusion. For example, the rule Birds typically fly could be written as
| Bird(x):Fly(x) |
| Fly(x) |
which reads: if x is a bird, and it is consistent that x flies, then conclude that x flies.
Default rules must be applied with care, since conflicting default rules could cause inconsistency if used together. For example, the default Quakers are usually pacifists conflicts with the default Republicans are usually nonpacifists in the case of Richard Nixon, who was both a Quaker and a Republican. Applying the first default yields the conclusion that Nixon was a pacifist; applying the second default yields the conclusion that Nixon was a nonpacifist; applying both yields inconsistency. One generates extensions of a default theory by applying as many default rules as possible. Multiple extensions, or their equivalent, arise in all nonmonotonic logics. The existence of multiple extensions may be seen as a feature or a problem. On the one hand, they allow the expression of reasonable but conflicting arguments within one system, and thus model well commonsense reasoning and discourse. However, conflicting defaults may give rise to unexpected extensions, corresponding to arguments that seem odd or unreasonable. An example of problematic multiple extensions is the Yale shooting problem, discussed below.
Autoepistemic Logic (Moore 1985) formalizes nonmonotonicity using sentences of a MODAL LOGIC of belief with belief operator L. Autoepistemic Logic focuses on stable sets of sentences (Stalnaker 1980) -- sets of sentences that can be viewed as the beliefs of a rational agent -- and the stable expansions of a premise set. Properties of stable sets include consistency and a version of negative introspection: if a sentence P does not belong to a belief set, then the sentence ¬ L P belongs to the belief set. This corresponds to the principle that if an agent does not believe a particular fact, he believes that he does not believe it. To formalize the Tweety example, one represents the rule that birds typically fly as an appeal to an agent's beliefs:
L(Bird(x)) ∧ ¬ L (¬ Fly(x)) ==> Fly(x)
If I believe that x is a bird and I don't believe that x cannot fly, then (I will conclude that) x flies. Any stable expansion of the premise set consisting of this premise and the premise that Tweety is a bird will contain the conclusion that Tweety flies.
Circumscription (McCarthy 1980, 1986) seeks to formalize nonmonotonic reasoning within classical logic by circumscribing, or limiting the extension of, certain predicates. The logic limits the objects in a particular class to those that must be in the class. For example, consider the theory containing assumptions that typical birds fly, atypical (usually called abnormal) birds do not fly, penguins are atypical, Opus is a penguin, and Tweety is a bird. Opus must be in the class of atypical, nonflying birds, but there is no reason for Tweety to be in that class; thus we conclude that Tweety can fly. The circumscription of a theory is achieved by adding a second-order axiom (or, in a first-order theory, an axiom schema), limiting the extension of certain predicates, to a set of axioms.
The systems above describe different ways of determining the nonmonotonic consequences of a set of assumptions. Entailment Relations (Kraus, Lehmann, and Magidor 1990) generalize these approaches by considering a nonmonotonic entailment operator |~, where P |~ Q means that Q is a nonmonotonic consequence of P, and by formulating general principles characterizing the behavior of |~. These principles specify how |~ relates to the standard entailment operator |- of classical logic, and how meta-statements referring to the entailment operator can be combined.
Belief Revision (Alchourron, Gardenfors, and Makinson 1985) studies nonmonotonic reasoning from the dynamic point of view, focusing on how old beliefs are retracted as new beliefs are added to a knowledge base. There are four interconnected operators of interest: contraction, withdrawal, expansion, and revision. In general, revising a knowledge base follows the principle of minimal change: one conserves as much information as possible.
Nonmonotonic reasoning systems are useful only if they can be successfully integrated with other theories of commonsense reasoning. Attempts at integration are often surprisingly difficult. For example, the Yale shooting problem (Hanks and McDermott 1987) showed that integrating nonmonotonic reasoning with TEMPORAL REASONING was complicated by the multiple extension problem. The Yale shooting problem consists of determining what happens to a turkey when we know that
Two extensions arise, only one of which is expected. In the expected extension, D1 is applied, the gun remains loaded at 3:00, and the turkey dies. In the unexpected extension, D2 is applied and the turkey is therefore alive after 3:00. This entails that the gun mysteriously becomes unloaded between 1:00 and 3:00. The problem of formalizing a system of temporal reasoning so that these unexpected extensions do not arise has become a central topic in nonmonotonic research. In nonmonotonic temporal reasoning, it has resulted in the development of theories of CAUSATION and EXPLANATION (Morgenstern 1996 and Shanahan 1997 give summaries and analyses).
Integrating nonmonotonic logics with MULTIAGENT SYSTEMS is also difficult. The major problem is modeling nested nonmonotonic reasoning: agents must reason about other agents' nonmonotonic reasoning processes. Most nonmonotonic formalisms are not expressive enough to model such reasoning. Moreover, nested nonmonotonic reasoning requires that agents know what other agents do not believe, a difficult requirement to satisfy (Morgenstern and Guerreiro 1993).
In general, integration may require extending both the nonmonotonic formalism and the particular theory of commonsense reasoning.
Applications of nonmonotonic systems are scarce. Implementors run into several difficulties. First, most nonmonotonic logics explicitly refer to the notion of consistency of a set of sentences. Determining consistency is in general undecidable for first-order theories; thus predicate nonmonotonic logic is undecidable. Determining inconsistency is decidable but intractable for propositional logic; thus performing propositional nonmonotonic reasoning takes exponential time. This precludes the development of general efficient nonmonotonic reasoning systems (Selman and Levesque 1993).
However, efficient systems have been developed for limited cases. LOGIC PROGRAMMING, the technique of programming using a set of logical sentences in clausal form, uses a nonmonotonic technique known as "negation as failure": a literal, consisting of an atomic formula preceded by a nonclassical negation operator, is considered true if the atomic formula cannot be proven. Although logic programs cannot express all types of nonmonotonic reasoning, they can be very efficient (Gottlob 1992). Likewise, inheritance with exceptions is an efficient, although limited, form of nonmonotonic reasoning (Horty, Thomason, and Touretzky 1990; Stein 1992). These limited cases handle many common types of nonmonotonic reasoning.
Due to its efficiency, logic programming has been used for many applications, ranging from railway control to medical diagnosis (Proceedings of the Conference on Practical Applications of Prolog 1996, 1997), although few applications exploit logic programming's nonmonotonic reasoning abilities. Aside from logic programming, nonmonotonic logic is still rarely used in the commercial world. This may be because the nonmonotonic reasoning community and the commercial world focus on different problems, and because there are few industrial-strength nonmonotonic tools (Morgenstern 1998).
There are similarities between nonmonotonic logics and other areas of research that seek to formalize reasoning under UNCERTAINTY, such as FUZZY LOGIC and PROBABILISTIC REASONING (especially BAYESIAN NETWORKS). These fields are united in their attempt to represent and reason with incomplete knowledge. The character of nonmonotonic reasoning is different in that it uses a qualitative rather than a quantitative approach to uncertainty. Attempts to investigate the connections between these areas include the work of Goldszmidt and Pearl (1992, 1996).
Alchourron, C. E., P. Gardenfors, and D. Makinson. (1985). On the logic of theory change: Partial meet functions for contraction and revision. Journal of Symbolic Logic 50:510-530.
Goldszmidt, M., and J. Pearl. (1992). Rank-based systems: A simple approach to belief revision, belief update, and reasoning about evidence and actions. Third International Conference on Principles of Knowledge Representation and Reasoning: (KR-92). San Mateo, CA: Morgan Kaufmann, pp. 661-672.
Goldszmidt, M., and J. Pearl. (1996). Qualitative probabilities for default reasoning, belief revision, and causal modeling. Artificial Intelligence, 84:57-112.
Gottlob, G. (1992). Complexity results for nonmonotonic logics. Journal of Logic and Computation 2(3):397-425.
Hanks, S., and D. McDermott. (1987). Nonmonotonic logic and temporal projection. Artificial Intelligence 33(3):379-412.
Horty, J., R. Thomason, and D. Touretzky. (1990). A skeptical theory of inheritance in nonmonotonic semantic networks. Artificial Intelligence 42:311-349.
Kraus, S., D. Lehmann, and M. Magidor. (1990). Nonmonotonic reasoning, preferential models, and cumulative logics. Artificial Intelligence 44:167-207.
McCarthy, J. (1980). Circumscription -- a form of nonmonotonic reasoning. Artificial Intelligence 13:27-39.
McCarthy, J. (1986). Applications of circumscription to formalizing common-sense knowledge. Artificial Intelligence 28:86-116.
Moore, R. (1985). Semantical considerations on nonmonotonic logic. Artificial Intelligence 25(1):75-94.
Morgenstern, L. (1996). The problem with solutions to the frame problem. In K. Ford and Z. Pylyshyn, Eds., The Robot's Dilemma Revisited. Norwood: Ablex, pp. 99-133.
Morgenstern, L. (1998). Inheritance comes of age: Applying nonmonotonic techniques to problems in industry. Artificial Intelligence (103): 237-271. Shorter version in Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence (IJCAI-97). Los Altos: Morgan Kaufmann, pp. 1613 - 1621.
Morgenstern, L., and R. Guerreiro. (1993). Epistemic logics for multiple agent nonmonotonic reasoning I. Proceedings of the Second Symposium on Logical Formalizations of Commonsense Reasoning (CS-93). Austin, TX, pp. 147-156.
Reiter, R. (1980). A logic for default reasoning. Artificial Intelligence 13:81-132.
Selman, B., and H. Levesque. (1993). The complexity of path-based defeasible inheritance. Artificial Intelligence 62(2):303-340.
Shanahan, M. (1997). Solving the Frame Problem. Cambridge, MA: MIT Press.
Stalnaker, R. (1980). A note on nonmonotonic modal logic. Ithaca, NY: Department of Philosophy, Cornell University.
Stein, L. (1992). Resolving ambiguity in nonmonotonic inheritance hierarchies. Artificial Intelligence 55:259-310.
Antoniou, G. (1997). Nonmonotonic Reasoning. Cambridge, MA: MIT Press.
Besnard, P. (1989). An Introduction to Default Logics. Berlin: Springer.
Brewka, G. (1991). Nonmonotonic Reasoning: Logical Foundations of Commonsense. Cambridge: Cambridge University Press.
Dix, J., U. Furbach, and A. Nerode, Eds. (1997). Logic Programming and Nonmonotonic Reasoning. Berlin: Springer.
Etherington, D. (1988). Reasoning with Incomplete Information. London: Pitman.
Gabbay, D., C. J. Hogger, and J. A. Robinson, Eds. (1994). Handbook of Logic in Artificial Intelligence and Logic Programming, vol. 3: Nonmonotonic Reasoning and Uncertain Reasoning. Oxford: Clarendon Press.
Gardenfors, P. (1988). Knowledge in Flux: Modeling the Dynamics of Epistemic States. Cambridge, MA: MIT Press.
Gardenfors, P., Ed. (1992). Belief Revision. Cambridge: Cambridge University Press.
Geffner, H. (1992). Default Reasoning: Causal and Conditional Theories. Cambridge: MIT Press.
Genesereth, M., and N. Nilsson. (1987). Foundations of Artificial Intelligence. San Mateo: Morgan Kaufmann.
Ginsberg, M., Ed. (1987). Readings in Nonmonotonic Reasoning. San Mateo: Morgan Kaufmann.
Konolige, K. (1988). On the relation between default and autoepistemic logic. Artificial Intelligence 35:343-382.
Lloyd, J. (1987). Foundations of Logic Programming. 2nd ed. Springer.
Marek, W., and M. Truszcyznski. (1993). Nonmonotonic Logic. Springer.
McDermott, D. (1982). Non-monotonic logic II: Non-monotonic modal theories. Journal of the Association for Computing Machinery 29:33-57.
McDermott, D., and J. Doyle (1980). Non-monotonic logic I. Artificial Intelligence 25:41-72.
Pearl, J. (1990). Probabilistic semantics for nonmonotonic reasoning: A survey. In G. Shafer and J. Pearl, Eds., Readings in Uncertain Reasoning. San Mateo: Morgan Kaufmann, pp. 699-710.
Poole, D. (1988). A logical framework for default reasoning. Artificial Intelligence 36:27-47.
Shoham, Y. (1988). Reasoning about Change: Time and Causation from the Standpoint of Artificial Intelligence. Cambridge, MA: MIT Press.
Williams, M. (1995). Iterated theory base change: A computational model. Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence (IJCAI-95). Los Altos: Morgan Kaufmann, pp. 1541-1547.
Copyright © 1999 Massachusetts Institute of Technology