Winter 2012 Edition
The term “non-monotonic logic” covers a family of formal frameworksdevised to capture and representdefeasible inference, i.e.,that kind of inference of everyday life in which reasoners drawconclusions tentatively, reserving the right to retract them in thelight of further information. Such inferences are called“non-monotonic” because the set of conclusions warranted on the basisof a given knowledge base, given as a set of premises, does notincrease (in fact, it can shrink) with the size of the knowledge baseitself. This is in contrast to standard logical frameworks (e.g.,classical first-order) logic, whose inferences, being deductivelyvalid, can never be “undone” by new information.
Classical first-order logic (henceforth: FOL) is monotonic: if asentence φ can be inferred in FOL from a set Γ of premises,then it can also be inferred from any set Δ of premisesextending Γ. In other words, FOL provides a relation ⊨ oflogical consequence betweensets of premises and single sentences with the property that if Γ ⊨ φ and Γ ⊆ Δthen Δ ⊨ φ. This followsimmediately from the nature of the relation ⊨, for Γ ⊨φ holds precisely when φ is true on every interpretation onwhich all sentences in Γ are true (see the entry onclassical logic for details on therelation ⊨).
Consider the formal properties of a consequence relation from anabstract point of view. Let
be any relation between sets of premises and single sentences. Thefollowing properties are all satisfied by the consequence relation⊨ of FOL:
φ. φ; φ and Γ, φ ψ then Γ ψ; φ and Γ ⊆ Δ then Δ φ.Supraclassicality just requires that be an extension of ⊨, i.e., that if φ follows from Γ in FOL,then it must also follow according to. (The relation ⊨ is trivially supraclassical).
The most straightforward of the remaining conditions is reflexivity,which requires that all sentences in Γ be inferable fromΓ. This translates to the requirement that if φ belongs tothe set Γ, then φ is a consequence of Γ. Reflexivityis a rather minimal requirement on a relation of logical consequence:It is hard to imagine in what sense a relation that fails to satisfyreflexivity, can still be considered aconsequencerelation.
Cut, a form of transitivity, is another crucial feature ofconsequence relations. Cut is a conservativity principle: if φ is aconsequence of Γ, then ψ is a consequence of Γ togetherwith φ only if it is already a consequence of Γ alone. Inother words, adjoining to Γ something which is already aconsequence of Γ does not lead to anyincrease ininferential power.
Cut is best regarded as a condition on the “length” of a proof(where “length” is to be understood in some intuitive sense related tothe complexity of the argument supporting a given conclusion). Whenviewed in these terms, Cut amounts to the requirement that the lengthof the proof does not affect the degree to which the assumptionssupport the conclusion. Where φ is already a consequence ofΓ, if ψ can be inferred from Γ together with φ,then ψ can also be obtained via a longer “proof” that proceedsindirectly by first inferring φ directly from Γ.
In contrast, in many forms of probabilistic reasoning the degree to which thepremises support the conclusion is inversely correlated to the lengthof the proof. For this reason, many forms of probabilistic reasoningfail to satisfy Cut. To see this, we adapt a well-knowncounter-example: letAx abbreviate “x is aPennsylvania Dutch”,Bx abbreviate “x is a nativespeaker of German”, andCx abbreviate “x was born inGermany”. Further, let Γ comprise the statements “MostAs areBs,” “MostBs areCs,” andAx. Then Γ supportsBx, and Γ togetherwithBx supportsCx, but Γ by itself does notsupportCx. (Here statements of the form “MostAs areBs” can be interpreted probabilistically, as saying that theconditional probability ofB givenA is, say, greaterthat 50%.) To the extent that Cut is a necessary feature of awell-behaved consequence relation, examples of inductive reasoning suchas the one just given cast some doubt on the possibility of coming upwith a well-behaved relation of probabilistic consequence.
For our purposes, Monotony is the central property. Monotony statesthat if φ is a consequence of Γ then it is also a consequenceof any set containing Γ (as a subset). The import of monotony isthat one cannot pre-empt conclusions by adding new premises. However,there are many inferences typical of everyday (as opposed tomathematical or formal) reasoning, that do not satisfy monotony. Theseare cases in which we reach our conclusionsdefeasibly (i.e.,tentatively), reserving the right to retract them in the light offurther information. Perhaps the clearest examples are derived fromlegal reasoning, in which defeasible assumptions abound. In thejudicial system, the principle ofpresumption of innocenceleads us to infer (defeasibly) from the fact thatx is tostand trial, the conclusion thatx is innocent; but clearlythe conclusion can be retracted in the light of new evidence.
Other examples are driven by typicality considerations. If beingaB is a typical trait ofA's, then from the factthatx is anA we infer the conclusionthatx is aB. But the conclusion is defeasible, inthatB-ness is not a necessary trait ofA's, butonly (perhaps) of 90% of them. For example, mammals, by and large,don't fly, so that lack of flight can be considered a typical trait ofmammals. Thus, when supplied with information thatx is amammal, we naturally infer thatx does not fly. But thisconclusion is defeasible, and can be undermined by the acquisition ofnew information, for example by the information thatx is abat. This inferential process can be further iterated. We can learn,for instance, thatx is a baby bat that (as such) does notyet know how to fly .
Defeasible reasoning, just like FOL, can follow complex patterns.However, such patterns are beyond reach for FOL, which is, by its verynature, monotonic. The challenge then is to provide for defeasiblereasoning what FOL provides for formal or mathematical reasoning, i.e.,an account that is bothmaterially adequate andformally precise.
It follows that monotony has to be abandoned, if we want to give aformal account of these patterns of defeasible reasoning. But then thequestion naturally arises of what formal properties of the consequencerelation are to replace monotony. Two such properties, given below,have been considered in the literature, where is an arbitrary consequence relation:
φ and Γ ψ, then Γ, φ ψ.¬ φ, and moreoverΓψ, then Γ,φ ψ.Both Cautious Monotony and the stronger principle of Rational Monotonyare special cases of Monotony, and are therefore not in the foregroundas long as we restrict ourselves to the classical consequence relation ⊨ of FOL.
Although superficially similar, these principles are in realityquite different. Cautious Monotony is the converse of Cut: it statesthat adding a consequence φ back into the premise-set Γ doesnot lead to anydecrease in inferential power. CautiousMonotony tells us that inference is a cumulative enterprise: we cankeep drawing consequences that can in turn be used as additionalpremises, without affecting the set of conclusions. Together with Cut,Cautious Monotony says that if φ is a consequence of Γ thenfor any proposition ψ, ψ is a consequence of Γ if andonly if it is a consequence of Γ together with φ. It has beenoften pointed out, most notably byGabbay (1985),that Reflexivity, Cut and Cautious Monotony are critical properties forany well-behaved non-monotonic consequence relation.
The status of Rational Monotony is much more problematic. As weobserved, Rational Monotony can be regarded as a strengthening ofCautious Monotony, and like the latter it is a special case ofMonotony. However, there are reasons to think that Rational Monotonymight not be a correct feature of a non-monotonic consequencerelation, and in fact there is a counter-example to Rational Monotony,which is due to Robert Stalnaker (seeStalnaker (1994)). Consider the three composers: Verdi,Bizet, and Satie, and suppose that we initially accept (correctly butdefeasibly) that Verdi is Italian, while Bizet and Satie are French. Weassume that these defeasible conclusions are built into whateverinferential mechanism implements the non-monotonic relation.
Suppose now that we are told by a reliable (but not infallible!)source of information that that Verdi and Bizet are compatriots. Thisleads us no longer to endorse either the proposition that Verdi is Italian(because he could be French), or that Bizet is French (because hecould be Italian); but we would still draw the defeasible consequencethat Satie is French, since nothing that we have learned conflicts withit. By letting I(v), F(b), and F(s)represent our initial beliefs about the composers' nationalities, andC(v,b) represent the proposition that Verdi and Bizetare compatriots, the situation could be represented as follows:
C(v,b)
Now consider the proposition C(v,s) that Verdi andSatie are compatriots. Before learning that C(v,b) wewould be inclined to reject the proposition C(v,s)because we endorse and I(v) and F(s), but afterlearning that Verdi and Bizet are compatriots, we can no longer endorseI(v), and therefore no longer reject C(v,s).Then the followingfails:
C(v,b)
However, if we added C(v,s) to our stock of beliefs,we would lose the inference to F(s): in the context ofC(v,b), the proposition C(v,s) isequivalent to the statement that all three composers have the samenationality. This leads us to suspend our assent to the propositionF(s). In other words, and contrary to Rational Monotony, thefollowing alsofails:
C(v,b), C(v,s)
The previous discussion gives a rather clear picture of the desirablefeatures of a non-monotonic consequence relation. Such a relationshould satisfy Supraclassicality, Reflexivity, Cut, and CautiousMonotony.
A separate issue from the formal properties of a non-monotonicconsequence relation, although one that is strictly intertwined withit, is the issue of howconflicts between potential defeasibleconclusions are to be handled.
There are two different kinds of conflicts that can arise within agiven non-monotonic framework: (i) conflicts between defeasibleconclusions and “hard facts,” some of which possibly newly learned; and(ii) conflicts between one potential defeasible conclusion and another(many formalisms, for instance, provide some form of defeasibleinference rules, and such rules might have conflicting conclusions).When a conflict (of either kind) arises, steps have to be taken topreserve or restore consistency.
All non-monotonic logics handle conflicts of the first kind in thesame way: indeed, it is the very essence of defeasible reasoning thatconclusions can be retracted when new facts are learned. But conflictsof the second kind can be handled in two different ways: one can drawinferences either in a “cautious” or “bold” fashion (also known as“skeptical” or, respectively, “credulous”). These two optionscorrespond to significantly different ways to construe a given body ofdefeasible knowledge, and yield different results as to what defeasibleconclusions are warranted on the basis of such a knowledge base.
The difference between these basic attitudes comes to this. In thepresence of potentially conflicting defeasible inferences (and in theabsence of further considerations such as specificity — see below),the credulous reasoner always commits to as many defeasible conclusionsas possible, subject to a consistency requirement, whereas theskeptical reasoner withholds assent from potentially conflicteddefeasible conclusions.
A famous example from the literature, the so-called “Nixon diamond,”will help make the distinction clear. Suppose our knowledge basecontains (defeasible) information to the effect that a givenindividual, Nixon, is both a Quaker and a Republican. Quakers, by andlarge, are pacifists, whereas Republicans, by and large, are not. Thequestion is what defeasible conclusions are warranted on the basis ofthis body of knowledge, and in particular whether we should infer thatNixon is a pacifist or that he is not pacifist. The following figureprovides a schematic representation of this state of affairs in theform a (defeasible) network:
The credulous reasoner has no reason to prefer either conclusion(“Nixon is a pacifist;” “Nixon is not a pacifist”) to the other one,but will definitely commit to one or the other. The skeptical reasonerrecognizes that this is a conflict not between hard facts anddefeasible inferences, but between two different defeasible inferences.Since the two possible inferences in some sense “cancel out,” theskeptical reasoner will refrain from drawing either one.
Defeasible inheritance networks can also be interpreted as providinga representation of that particular kind of inference referred to as“stereotypical.”Stereotypes can be viewed as generalizationsconcerning particular populations; while they might be sometimes usefulas such, their applicability to individual cases is problematic. Infact, the particular point of view according to which stereotypes applyto groups but not to individuals meshes particularly well with theskeptical approach to defeasible inheritance.
Consider again the Nixon Diamond above. Part of what it says is thatthere are stereotypes to the effect that Quakers are Pacifists andRepublicans are not. But of course the whole point of the skepticalinterpretation of the diagram is that one cannot reliably use suchinformation to reach conclusions about a particular individual.
The point can be presented quantitatively as well. Consider thefollowing Venn diagram, where the numbers represent the populationinhabiting a particular region:
The stereotypes are supported, from a probabilistic point of view.In fact, the probability ofP givenQ is 95/120, orabout 79%. Similarly, the probability ofnot-P givenR is about 79%. But of course the probability ofPgivenQandR is only 50%. It seems like noparticular conclusions can be drawn from the fact that a particularindividual is both a Quaker and a Republican.
Indeed, whereas many of the early formulations of defeasiblereasoning have been credulous, skepticism has gradually emerged as aviable alternative, which can, at times, be better behaved. Argumentshave been given in favor of both skeptical and credulous inference.Some have argued that credulity seems better to capture a certain classof intuitions, while others have objected that although a certaindegree of “jumping to conclusion” is by definition built into anynon-monotonic formalism, such jumping to conclusions needs to beregimented, and that skepticism provides precisely the requiredregimentation. (A further issue in the skeptical/credulous debate isthe question of whether so-called “floating conclusions” should beallowed; seeHorty (2002) for a review of theliterature and a substantial argument that they should not.)
One of the most significant developments both in logic and artificialintelligence is the emergence of a number of non-monotonic formalisms,which were devised expressly for the purpose of capturing defeasiblereasoning in a mathematically precise manner. The fact that patterns ofdefeasible reasoning have been accounted for in such a rigorous fashionhas wide-ranging consequences for our conceptual understanding ofargumentation and inference.
Pioneering work in the field of non-monotonic logics began with therealization that FOL is inadequate for the representation ofdefeasible reasoning. Such a realization was accompanied by the effortto reproduce the success of FOL in the representation of mathematical,or formal, reasoning. Among the pioneers of the field in the late1970's were (among others) J. McCarthy, D. McDermott & J. Doyle,and R. Reiter (seeGinsberg (1987) for a collection ofearly papers in the field andGabbay et al (1994)for a more recent collection of excellent survey papers). In 1980, theArtificial Intelligence Journal published an issue (vol. 13,1980) dedicated to these new formalisms, an event that has come to beregarded as the “coming of age” of non-monotonic logic.
If one of the goals of non-monotonic logic is to provide amaterially adequate account of defeasible reasoning, it is important torely on a rich supply of examples to guide and hone intuitions.Database theory was one of the earliest sources of such examples,especially as regards theclosed world assumption. Suppose atravel agent has access to a flight database, and needs to answer aclient's query about the best way to get from Oshkosh to Minsk. Theagents queries the database and, not surprisingly, responds that thereare no direct flights. How does the travel agent know?
It is quite clear that, in a strong sense of “know,” the travelagent does notknow that there are no such flights. What is atwork here is a tacit assumption that the database iscomplete,and that since the database does not list any direct flights betweenthe two cities, then there are none. A useful way to look at thisprocess is as a kind ofminimization, i.e., an attempt tominimize the extension of a given predicate (“flight-between,” in thiscase). Moreover, on pain of inconsistencies, such a minimization needsto take place not with respect to what the database explicitly containsbut with respect to what it implies.
The idea of minimization is at the basis of one of the earliestnon-monotonic formalisms, McCarthy'scircumscription.Circumscription makes explicit the intuition that, all other thingsbeing equal, extensions of certain predicates should beminimal. Again, consider principles such as “all normal birdsfly”. Implicit in this principle is the idea that the extension of theabnormality predicate should be minimal, and that specimens should notbe considered to be abnormal unless there is positive information tothat effect. McCarthy's idea was to represent this formally, usingsecond-order logic (SOL). In SOL, in contrast to FOL, one is allowed toexplicitly quantify over predicates, forming sentences such as∃P∀xPx (“there is a universalpredicate”) or ∀P(Pa ↔Pb) (“aandb are indiscernible”).
In circumscription, given predicatesP andQ, weabbreviate ∀x(Px →Qx) asP≤Q; similarly, we abbreviateP≤Q & ¬Q≤P asP<Q. IfA(P) is aformula containing occurrences of a predicateP, then thecircumscription ofP inA is the second-ordersentenceA*(P):
A(P) &¬∃Q[A(Q)&Q<P]A*(P) says thatP satisfiesA, andthat no smaller predicate does. LetPx be the predicate“x is abnormal,” and letA(P) be thesentence “All normal birds fly.” Then the sentence “Tweety is a bird,”together withA*(P) implies “Tweety flies,” for thecircumscription axiom forces the extension ofP to be empty,so that “Tweety is normal” is automatically true.
In terms of consequence relations, circumscription allows us todefine, for each predicateP, a non-monotonic relationA(P) φthat holds precisely whenA*(P) ⊨ φ. (This basic form of circumscription has beengeneralized, for, in practice, one needs to minimize the extension of apredicate, while allowing the extension of certain other predicates tovary.) From the point of view of applications, however, circumscriptionhas a major computational shortcoming, which is due to the nature ofthe second-order language in which circumscription is formulated. Theproblem is that SOL, contrary to FOL, lacks a complete inferenceprocedure: the price one pays for the greater expressive power ofsecond-order logic is that there are no complete axiomatizations, as wehave for FOL. It follows that there is no way to list, in an effectivemanner, all SOL validities, and hence to determine whetherA(P)φ.
Another non-monotonic formalism inspired by the intuition ofminimization of abnormalities isnon-monotonic inheritance.Whenever we have a taxonomically organized body of knowledge, wepresuppose that subclasses inherit properties from their superclasses:dogs have lungs because they are mammals, and mammals have lungs.However, there can be exceptions, which can interact in complex ways.To use an example already introduced, mammals, by and large, don't fly;since bats are mammals, in the absence of any information to thecontrary, we are justified in inferring that bats do not fly. But if thenwe learn that bats are exceptional mammals, in that they do fly, theconclusion that they don't fly is retracted, and the conclusion thatthey fly is drawn instead. Things can be more complicated still, for inturn, as we have seen, baby bats are exceptional bats, in that they donot fly (does that make them unexceptional mammals?). Here we havepotentially conflicting inferences. When we infer that Stellaluna,being a baby bat, does not fly, we are resolving all these potentialconflicts based on aspecificity principle: more specificinformation overrides more generic information.
Non-monotonic inheritance networks were developed for the purpose ofcapturing taxonomic examples such as the one above. Such networks arecollections of nodes and directed (“IS-A”) links representing taxonomicinformation. When exceptions are allowed, the network is interpreteddefeasibly. The following figure gives a network representingthis state of affair:
In such a network, links of the formA →Brepresent the fact that, typically and for the most part,A'sareB's, and that therefore information aboutA's ismore specific than information aboutB's. More specificinformation overrides more generic information. Research onnon-monotonic inheritance focuses on the different ways in which onecan make this idea precise.
The main issue in defeasible inheritance is to characterize the setof assertions that are supported by a given network. It is of coursenot enough to devise a representational formalism, one also needs tospecify how the formalism is to be interpreted. Such a characterizationis accomplished through the notion of anextension of a givennetwork. There are two competing characterizations of extension forthis kind of networks, one that follows the credulous strategy and onethat follows the skeptical one. Both proceed by first defining thedegree of a path through the network as the length of thelongest sequence of links connecting its endpoints; extensions are thenconstructed by considering paths in ascending order of their degrees.We are not going to review the details, since many of the same issuesarise in connection with default logic (which is treated to greaterlength below), butHorty (1994) provides anextensive survey. It is worth mentioning that since the notion ofdegree makes sense only in the case of acyclic networks, special issuesarise when networks contain cycles (seeAntonelli (1997),(2005) for a treatment of inheritanceon cyclic networks).
Although the language of non-monotonic networks is expressivelylimited by design (in that only links of the form “IS-A” — andtheir negations — can be represented in a natural fashion), suchnetworks provide an extremely useful setting in which to test and honeone's intuitions and methods for handling defeasible information. Suchintuitions and methods are then applied to more expressiveformalisms. Among the latter is Reiter'sDefault Logic,perhaps the most flexible among non-monotonic frameworks.
In Default Logic, the main representational tool is that of adefault rule, or simply adefault. A default is adefeasible inference rule of the form
γ : θ τ
(where γ, θ, τ are sentences in a given language,respectively called thepre-requisite,thejustification and theconclusion of the default). The interpretation of the defaultis that if γ is known, and there is no evidence that θmight be false, then τ can be inferred.
As is clear, application of the rule requires that a consistencycondition be satisfied. What makes meeting the condition complicated isthe fact that rules can interact in complex ways. In particular, it ispossible that application of some rule might cause the consistencycondition to fail for some, not necessarily distinct, rule. Forinstance, if θ is ¬τ then application of the rule is in asense self-defeating, in that application of the rule itself causes theconsistency condition to fail.
Reiter's default logic uses its own notion of anextensionto make precise the idea that the consistency condition has to be metboth before and after the rule is applied. Given a set Γ ofdefaults, an extension for Γ represents a set of inferences thatcan bereasonably andconsistently drawn usingdefaults from Γ. Such inferences are those that are warranted onthe basis of a maximal set of defaults whose consistency condition ismet both before and after their being triggered.
More in particular (and in typical circular fashion), an extensionfor Γ is a maximal subset Δ of Γ the conclusions ofwhose defaults both imply all the pre-requisites of defaults in Γand are consistent with all the justifications of defaults in Γ.This definition can be made both less mysterious and more precise asfollows. By adefault theory we mean a pair(W,Δ), where Δ is a (finite) set of defaults, andW is a set of sentences (a world description). The idea isthatW represents the strict or background information,whereas Δ specifies the defeasible information. Given a pair(T1,T2) of sets of sentences, adefault such as theabove istriggeredby (T1,T2) if and only ifT1 ⊨ γ and it's not the casethatT2⊨ ¬θ (i.e., θ isconsistent withT2). (Notice how this definition is built “on top”of ⊨: we could, conceivably, employa different consequence relation here, e.g., relevant, intuitionistic, etc..)
Finally we say that a set of sentencesE is anextension for a default theory (W,Δ) if andonly if
E =E0∪E1∪ ... ∪En∪... ,
where:E0 =W, and
En+1 =En∪ {τ : the default (γ : θ) / τ ∈ Δis triggered by (En,E) }.
It is important to notice the occurrence of the limitE in thedefinition ofEn+1: the condition above isnot a garden-variety recursive defintion, but a truly circularcharacterization of extensions.
This circularity can be made explicit by giving an equivalentdefinition of extension as solution of fixpoint equations. Given adefault theory, letS be an operator defined on sets ofsentences such that for any such setS,S(S) is the smallest set containingW, deductively closed (i.e., such that ifS(S) ⊨ φthen φ ∈S(S)), and such that if a default withconsequent τ is triggered by (S,S) thenτ∈S(S). Then one can show thatE is an extension for (W,Δ) if and only ifE is a fixed point ofS, i.e., ifS(E) =E.
For any given default theory, extensions need not exist, and evenwhen they exist, they need not be unique. Let us consider a couple ofexamples. Our first example is a default theory that has no extension:letW contain the sentence γ and let Δ comprise thesingle default
γ : θ ¬θ
IfE were an extension, then the default above would have tobe either triggered or not triggered by it, and either case isimpossible. For if the default were triggered, then the consistencycondition would fail, and if if were not triggered then the consistencycondition would hold, and hence the default would have to be triggeredby maximality of extensions.
Let us now consider an example of a default theory with multipleextensions. As before, letW contain the sentence γ, andsuppose Δ comprises the following two defaults
γ : θ ¬τ
and
γ : τ ¬θ
This theory has exactly two extensions, one in which the first defaultis triggered and one in which the second one is. It is easy to see thatat least one default has to be triggered in any extension, and that bothdefaults cannot be triggered by the same extension.
These examples are enough to bring out a number of features. First,it should be noted that neither one of the two characterizations ofextension for default logic (i.e., the fixpoint definition and thepseudo-iterative one) given above gives us a way to “construct”extension by means of anything resembling an iterative process.Essentially, one has to “guess” a set of sentencesE, and thenverify that it satisfies the definition of an extension.
Further, the fact that default theories can have zero, one, or moreextensions raises the issues of what inferences one is warranted indrawing from a given default theory. The problem can be presented asfollows: given a default theory (W,Δ), what sentencescan be regarded asdefeasible consequences of the theory? Atfirst sight, there are several options available.
One option is to take the union of the extensions of the theory, andconsider a sentence φ a consequence of a given default theory ifand only if φ belongs toany extension of the theory. Butthis option is immediately ruled out, in that it leads to endorsingcontradictory conclusion, as in the second example above. It is widelybelieved that any viable notionof defeasible consequence for defaultlogic must have the property that the set
{φ : (W,Δ)
must be consistent wheneverW is. Once this option is ruledout, only two alternatives are left:
The first alternative, known as the “credulous” or “bold” strategy,is to pick an extensionE for the theory, and say that φis a defeasible consequence if and only if φ ∈E. Thesecond alternative, known as the “skeptical” or “cautious” strategy, isto endorse a conclusion φ if and only if φ is contained inevery extension of the theory.
Neither the credulous or the skeptical strategy is completely satisfactory. Theproblem with the credulous strategy is that the choice ofE isarbitrary: with the notion of extension introduced by Reiter,extensions areorthogonal: of any two distinct extensions,neither one contains the other. Hence, there seems to be no principledway to pick an extension over any other one. This has led a number ofresearchers to endorse the skeptical strategy as a viable approach tothe problem of defeasible consequence. But as showed by Makinson,skeptical consequence, as based on Reiter's notion of extension, failsto be cautiously monotonic. To see this, consider the default theory(W, Δ), whereW is empty, and Δ comprisesthe following two defaults:
: θ θ
and
θ∨γ :¬θ ¬θ
This theory has only one extension, coinciding with the deductiveclosure of {θ}. Hence, if we define defeasible consequence byputting (W, Δ) φ if and only if φ belongs to everyextension of (W, Δ), we have (W, Δ) θ, as well as(W, Δ)θ∨γ (by the deductive closure of extensions).
Now consider the theory with Δ as before, but withWcontaining the sentence θ∨γ.This theory has two extensions: one the same as before, but alsoanother one coinciding with the deductive closure of {¬θ},and hence not containing θ. It follows that the intersection ofthe extensions no longer contains θ, so that ({ θ∨γ}, Δ) θ nowfails, against cautiousmonotony. (Notice that the same example establishes a counter-examplefor Cut for the credulous strategy, when we pick the extension of ({θ∨ γ}, Δ) thatcontains ¬θ.)
(The skeptical approach is also, conceivably, subject toconsiderations related tofloating conclusions, as we alreadymentioned. But missing these conclusion might indeed be a desirablefeature, as argued byHorty (2002)).It is clear that the issue of how to define a non-monotonicconsequence relation for default logic is intertwined with the way thatconflicts are handled. The problem of course is that in thiscase neither the skeptical nor the credulous strategy yield an adequaterelation of defeasible consequence.
InAntonelli (1999) a notion ofgeneral extension for default logic isintroduced, showing that this notion yields a well-behaved relation ofdefeasible consequence that satisfies all four requirements ofSupraclassicality, Reflexivity, Cut, and Cautious Monotony. (The sametreatment can be found inAntonelli (2005)). The idea can be explained ina particularly simple way in the case ofpre-requisite freedefault theories (called “categorical” inAntonelli (1999) andAntonelli (2005)). A general extension for such a default theory is apair(Γ+, Γ-) of sets of defaults (orconclusions thereof) that simultaneously satisfiestwofixpoint equations. The set Γ+ comprises (conclusionsof) defaults that are explicitly triggered, and the setΓ- comprises (conclusions of) defaults that areexplicitly ruled out. The intuition is that defaults that are notruled out can still prevent other defaults from being triggered(although they might not be triggered themselves). We thus obtain a“3-valued” approach (not unlike that ofKripke's (1975) theory of truth), in virtue of which general extensions arenow endowed with a non-trivial (i.e., not “flat”) algebraicstructure. It is then possible to pick out, in a principled way, aparticular general extension (for instance, the unique least one,which is always guaranteed to exist) on which to base a notion ofdefeasible consequence. As mentioned, such a notion of consequencesatisfies all fourdesiderata of Supraclassicality,Reflexivity, Cut, and Cautious Monotony.
A different set of issues arises in connection with the behavior ofdefault logic from the point of view of computation. For a givensemi-decidable set Γ of sentences, the set of all φ that area consequence of Γ in FOL is itself semi-decidable (see the entryoncomputability and complexity). Inthe case of default logic, to formulate the corresponding problem oneextends (in the obvious way) the notion of (semi-)decidability to setsof defaults. The problem, then, is to decide, given a default theory(W, Δ) and a sentence φ whether(W, Δ) φ,whereis defined, say,skeptically. Such a problem is not even semi-decidable, the essentialreason being that in general, in order to determine whether a defaultis triggered by a pair of sets of sentences, one has to perform aconsistency check, and such checks are not computable.
But the consistency checks are not the only source of complexity indefault logic. For instance, we could restrict our language toconjunctions of atomic sentences and their negations (makingconsistency checks feasible). Even so, the problem of determiningwhether a given default theory has an extension would still be highlyintractable (NP-complete, to be precise, as shown byKautz & Selman (1991)), seemingly because theproblem requires checking all possible sequences of firings ofdefaults.
Default logic is intimately connected with certainmodalapproaches to non-monotonic reasoning, which belong to the family ofautoepistemic logics. Modal logics in general have proved tobe one of the most flexible tools for modelling all sorts of dynamicprocesses and their complex interactions (see the entry “modal logic”, this Encyclopedia). Beside theapplications in knowledge representation, which we are going to treatbelow, there are modal frameworks, known asdynamic logics,that play a crucial role, for instance, in the modelling of serial orparallel computation. The basic idea of modal logic is that thelanguage is interpreted with respect to a given set ofstates,and that sentences are evaluated relative to one of these states. Whatthese states are taken to represent depends on the particularapplication under consideration (they could be epistemic states, orstates in the evolution of a dynamical system, etc.), but the importantthing is that there aretransitions (of one or more differentkinds) between states.
In the case of one transition that is bothtransitive(i.e., such that ifa→b andb→c thena→c) andeuclidean (ifa →b anda→c thenb →c), the resultingmodal system is referred to as K45. Associated with each kind of statetransition there is a corresponding modality in the language, usuallyrepresented as a box □. A sentence of theform □A is true at a states if and only ifA is true at every states′ reachable froms by the kind of transitionassociated with □ (seeChellas (1980) orHughes and Cresswell (1996) for comprehensive introductions to modallogic).
In autoepistemic logic, the states involved are epistemic states ofthe agent (or agents). The intuition underlying autoepistemic logic isthat we can sometimes draw inferences concerning the state of the worldusing information concerning our own knowledge or ignorance. Forinstance, I can conclude that I do not have a sister given that if Idid I would probably know about it, and nothing to that effect ispresent in my “knowledge base”. But such a conclusion is defeasible,since there is always the possibility of learning new facts. In orderto make these intuitions precise, consider a modal language in whichthe necessity operator □ is interpretedas “it is known that”. As in default logic or defeasible inheritance,the central notion in autoepistemic logic is that of anextension of a theoryS, i.e., a consistent andself-supporting set of beliefs that can reasonably be entertained onthe basis ofS. Given a setS of sentences, letS0 be the subset ofS composed of thosesentences containing no occurrences of □;further, let thepositive introspective closurePIC(S0) ofS0 be the set
{□φ : φ∈S0 },
and thenegative introspective closureNIC(S0) ofS0 the set
{¬□φ : φ ∉S0}.
The set PIC(S0) is called the introspective closurebecause it explicitly contains positive information about the agent'sepistemic status: PIC(S0) expresses what is known(similarly, NIC(S0) contains negative informationabout the agent's epistemic status, stating explicitly what isnot known).
With these notions in place, we define an extension forSto be a setT of sentences such that:
T = { φ : φ follows (in K45) fromS ∪ PIC(T0) ∪NIC(T0) }
Autoepistemic logic provides a rich language, with interestingmathematical properties and connections to other non-monotonicformalisms. It is faithfully intertranslatable with Reiter's version ofdefault logic, and provides a defeasible framework with well-understoodmodal properties.
There are three major issues connected with the development of logicalframeworks that can adequately represent defeasible reasoning:(i) material adequacy; (ii) formal properties; and(iii) complexity. Material adequacy concerns the question ofhow broad a range of examples is captured by the framework, and theextent to which the framework can do justice to our intutions on thesubject (at least the most entrenched ones). The question of formalproperties has to do with the degree to which the framework allows fora relation of logical consequence that satisfies the above mentionedconditions of Supraclassicality, Reflexivity, Cut, and CautiousMonotony. The third set of issues has to do with computationalcomplexity of the most basic questions concerning the framework.
There is a potential tension between (i) and (ii):the desire to capture a broad range of intuitions can lead toadhoc solutions that can sometimes undermine the desirable formalproperties of the framework. In general, the development ofnon-monotonic logics and related formalisms has been driven, since itsinception, by consideration (i) and has relied on a rich andwell-chosen array of examples. Of course, there is some question as towhether any single framework can aspire to be universal in thisrespect.
More recently, researchers have started paying attention toconsideration (ii), looking at the extent to whichnon-monotonic logics have generated well-behaved relations of logicalconsequence. AsMakinson (1994) points out,practitioners of the field have encountered mixed success. Inparticular, one abstract property, Cautious Monotony, appears at thesame time to be crucial and elusive for many of the frameworks to befound in the literature. This is a fact that is perhaps to be tracedback, at least in part, to the above-mentioned tension between therequirement of material adequacy and the need to generate awell-behaved consequence relation.
The complexity issue appears to be the most difficult among the onesthat have been singled out. Non-monotonic logics appear to bestubbornly intractable with respect to the corresponding problem forclassical logic. This is clear in the case of default logic, given theubiquitous consistency checks. But besides consistency checks, there areother, often overlooked, sources of complexity that are purelycombinatorial. Other forms of nonmonotonic reasoning, besides defaultlogic, are far from immune from these combinatorial roots ofintractability. Although some important work has been done trying tomake various non-monotonic formalism more tractable, this is perhapsthe problem on which progress has been slowest in coming.
The following list of references is of course far from exhaustive, butit is only meant to provide entry points to the literature.
[Please contact the author with suggestions.]
artificial intelligence |artificial intelligence: logic and |computability and complexity |logic: classical |logic: modal |model theory: first-order
