# preferential and preferential-discriminative consequence relations[精选推荐pdf]

arXivcs/0506030v6 [cs.AI] 8 Apr 2007Preferential and Preferential-discriminative Consequence Relations∗Jonathan Ben-Naim LIF, CNRS CMI 39, rue Joliot-Curie F-13453 Marseille Cedex 13, France jbennaimlif.univ-mrs.frAbstractThe present paper investigates consequence relations that are both non-monotonic and paraconsistent. Moreprecisely, we put the focus on preferential consequence relations, i.e. those relations that can be defined by a binary preference relation on states labelled by valuations. We worked with a general notion of valuation that coverse.g. theclassicalvaluations aswellascertainkinds of many-valued valuations. Inthemany-valued cases, preferential consequence relations are paraconsistant in addition to be non-monotonic, i.e. they are capable ofdrawing reasonable conclusions which contain contradictions. The first purpose of this paper is to provide in our general framework syntactic characterizations of several families of preferential relations. The second and main purpose isto provide, again in our general framework, characterizations of several families of preferential-discriminativeconsequence relations. Theyare defined exactlyasthe plainversion, but any conclusion such that its negation is also a conclusion is rejected these relations bring something new essentially in the many-valued cases.∗This is an updated version of the paper of the same title published in The Journal of Logic and Computation. This versionjust contains a better presentation so the numbering of definitions and propositions is different.11IntroductionIn many situations, we are confronted with incomplete and/or inconsistent ination and the clas-sical consequence relation proves to be insufficient. Indeed, in case of inconsistent ination, it leads to accept every ula as a conclusion, which amounts to loose the whole ination. Therefore, we need other relations leading to non-trivial conclusions in spite of the presence of con- tradictions. So, several paraconsistent consequence relations have been developed. In the present paper, we will pay attention in particular to certain many-valued ones [Bel77b, Bel77a, DdC70,A00, dACM02, AA94, AA96, AA98]. They are defined in frameworks where valuations can assign more than two different truth values to ulas. In fact, they tolerate contradictions within theconclusions,butrejecttheprincipleofexplosionaccordingtowhicha singlecontradictionentails the deduction of every ula. In case of incomplete ination, the classical consequence relation also shows its limits. In- deed,no risk is taken, the conclusionsare sure, but toofew. We needotherrelationsleadingto accept as conclusions ulas that are not necessarily sure, but still plausible. Eventually, some “hasty” conclusions will be rejected later, in the presence of additional ination. So, a lot of plausible generally non-monotonic consequence relations have been developed. Choice functions are cen-tral tools to define plausible relations [Che54, Arr59, Sen70, AM81, Leh02, Leh01, Sch92, Sch04]. Indeed, suppose we have at our disposal a function µ, called a choice function, which chooses in any set of valuations V , those elements which are preferred, not necessarily in the absolute sense,but when the valuations in V are the only ones under consideration. Then, we can define a plausible consequence relation in the following natural way a ula α follows from a set of ulas Γ iff every model for Γ chosen by µ is a model for α. In the present paper, we put the focus on a particular family of choice functions. Let us present it. Suppose we are given a binary preference relation ≺ on states labelled by valuations in thestyle of e.g. [KLM90, Sch04]. This defines naturally a choice function. Indeed, choose in any set of valuations V , each element that labels a state which is ≺-preferred among those states whichare labelled by the elements of V . Those choice functions which can be defined in this mannerconstitute the aforementioned family. The consequence relations defined by this family will be called preferential consequence relations. For a long time, research efforts on paraconsistent relations and plausible relations were sep- arated. However, in many applications, the ination is both incomplete and inconsistent. For instance, the semantic web or big databases inevitably contain inconsistencies. This can be due to human or material imperfections as well as contradictorysources of ination. On the other hand, neither the web nor big databases can contain “all” ination. Indeed, there are rules of which the exceptions cannot be enumerated. Also, some ination might be left voluntarily vague or in concise . Consequently, consequence relations that are both paraconsistent and plausible are useful to reason in such applications.Suchrelationsfirst appearin e.g. [Pri91, Bat98, KL92,AA00, KM02]. Theidea beginsbytaking a many-valued framework to get paraconsistency. Then, only those models that are most preferred accordingtosomeparticularbinarypreferencerelationonvaluationsinthestyle of[Sho88,Sho87] are relevant for making inference, which provides plausibility. In [AL01b, AL01a], A. Avron and I. Lev generalized the study to families of binary preference relations which compare two valuationsusing, for each of them, this part of a certain set of ulas it satisfies. The present paper follows this line of research by combining many-valued frameworks and choice functions. More explicitly, we will investigate preferential consequence relations in a general framework. According to the different assumptions which will be made about the latter, it will cover various2kinds of frameworks, including e.g. the classical propositional one as well as certain many-valued ones. Moreover, in the many-valued frameworks, preferential relations are paraconsistent in addi- tion to be plausible. However, they do not satisfy the Disjunctive Syllogism from α and ¬α ∨ β we can conclude β, whilst they satisfy it in classical framework. In addition, we will investigate preferential-discriminative consequence relations. They are de-fined exactly as the plain version, but any conclusion such that its negation is also a conclusion is rejected. In the classical framework, they do not bring something really new. Indeed, instead of con- cluding everything in the face of inconsistent ination, we will simply conclude nothing. On the other hand, in the many-valued frameworks, where the conclusions are non-trivial even from incon- sistent ination, the discriminative version will reject the contradictions among them, rendering them all the more rational. The contributionof the present papercan now be summarizedin one sentence we characterized, in a general framework, several subfamilies of preferential-discriminativeconsequencerelations. In many cases, our characterizations are purely syntactic. This has a lot of advantages, let us quote someimportantones. Takesomesyntacticconditionsthatcharacterizeafamilyofthoseconsequencerelations. This gives a syntactic point of view on this family defined semantically, which enables us to compare it to conditions known on the “market”, and thus to other consequence relations. Thiscan also give rise to questions like if we modified the conditions in such and such a natural-looking way, what would happen on the semantic side More generally, this can open the door to questions that would not easily come to mind otherwise or to techniques of proof that could not have been employed in the semantic approach. Several characterizations can be found in the literature for preferential relations e.g. [Gab85, Mak89, Mak94, KLM90, LM92, Leh02, Leh01, Sch92, Sch96, Sch00, Sch04]. We will provide some new ones, though to do so we have been strongly inspired by techniques of K. Schlechta [Sch04]. In fact, our innovation is rather related to the discriminative version. To the author knowl-edge, the present paperis the first systematic work of characterizationfor preferential-discriminative consequence relations. The rest of the paperis organizedas follows. In Section2.1, we introduceourgeneral framework and the different assumptions which sometimes will be made about it. We will see that it covers in particular the many-valued frameworks of the well-known paraconsistent logics FOUR and J3. In Section 2.2, we present choice functions and some of their well-known properties. In Section 2.3,we define preferential-discriminativeconsequencerelations andgiveexamplesin both the classical and the many-valued frameworks. We will also recall a characterization which involves the well- known system P of Kraus, Lehmann, and Magidor. In section 3, we provide our characterizations. Finally, we conclude in Section 4.2Background2.1Semantic structures2.1.1Definitions and propertiesWe will work with general ulas, valuations, and satisfaction. A similar approachhas been taken in two well-known papers [Mak05, Leh01].Definition 1 We say that S is a semantic structure iff S hF,V,|i where F is a set, V is a set, and | is a relation on V F.3Intuitively, F is a set of ulas, V a set of valuations for these ulas, and | a satisfactionrelation for these objects i.e. v | α means the ula α is satisfied in the valuation v, i.e. v is a model for α.Notation 2 Let hF,V,|i be a semantic structure, Γ ⊆ F, and V ⊆ V. Then, MΓ {v ∈ V ∀ α ∈ Γ, v | α}, TV {α ∈ F V ⊆ Mα}, D {V ⊆ V ∃ Γ ⊆ F,MΓ V }. Suppose L is a language, ¬ a unary connective of L, and F the set of all wffs of L. Then, TdV {α ∈ F V ⊆ Mαand V 6⊆ M¬α}, TcV {α ∈ F V ⊆ Mαand V ⊆ M¬α}, C {V ⊆ V ∀ α ∈ F, V 6⊆ Mαor V 6⊆ M¬α}.Intuitively, MΓis the set of all models for Γ and TV the set of all ulas satisfied in V . Every element of TV belongs either to TdV or TcV , according to whether its negation is also inTV . D is the set of all those sets of valuations that are definable by a set of ulas and C the set of all those sets of valuations that do not satisfy both a ula and its negation. As usual, MΓ,α, TV,v stand for respectively MΓ∪{α}, TV ∪ {v}, etc.Remark 3 The notations MΓ, TV , etc. should contain the semantic structure on which they are based. To increase readability, we will omit it. There will never be any ambiguity. We will omit similar things with other notations in the sequel, for the same reason.A semantic structure defines a basic consequence relationNotation 4 We denote by P the power set operator. Let hF,V,|i be a semantic structure. We denote by ⊢ the relation on PF F such that ∀ Γ ⊆ F, ∀ α ∈ F,Γ ⊢ α iff MΓ⊆ Mα.Let |∼ be a relation on PF F. Then, |∼Γ {α ∈ F Γ |∼ α}. Suppose L is a language, ¬ a unary connective of L, F the set of all wffs of L, and Γ ⊆ F. Then, we say that Γ is consistent iff ∀ α ∈ F, Γ 6⊢ α or Γ 6⊢ ¬α.The following trivial facts hold, we will use them implicitly in the sequelRemark 5 Let hF,V,|i be a semantic structure and Γ,∆ ⊆ F. Then MΓ,∆ MΓ∩ M∆; ⊢Γ TMΓ; MΓ M⊢Γ; Γ ⊆ ⊢∆ iff ⊢Γ ⊆ ⊢∆ iff M∆⊆ MΓ.Sometimes, we will need some of the following assumptions about a semantic structureDefinition 6 Suppose hF,V,|i is a semantic structure.Then, define the following assumptions about itA1 V is finite.4Suppose L is a language, ¬ a unary connective of L, and F the set of all wffs of L. Then, defineA2 ∀ Γ ⊆ F, ∀ α ∈ F, if α 6∈ TMΓ and ¬α 6∈ TMΓ, then MΓ∩ Mα6⊆ M¬α.Suppose ∨ and ∧ are binary connectives of L. Then, defineA3 ∀ α,β ∈ F, we have Mα∨β Mα∪ Mβ; Mα∧β Mα∩ Mβ; M¬¬α Mα; M¬α∨β M¬α∧¬β; M¬α∧β M¬α∨¬β.Clearly, those assumptions are satisfied by classical semantic structures, i.e. structures where F, V,and | are classical. In addition, we will see, in Sections 2.1.2 and 2.1.3, that they are satisfied also by certain many-valued semantic structures.2.1.2The semantic structure defined by FOURThe logic FOUR was introduced by N. Belnap in [Bel77a, Bel77b]. This logic is useful to deal with inconsistent ination. Several presentations are possible, depending on the language underconsideration. Fortheneedsofthepresentpaper,aclassicalpropositionallanguagewillbesufficient. The logic has been investigated intensively in e.g. [AA94, AA96, AA98], where richer languages,containing an implication connective ⊃ first introduced by A. Avron [Avr91], were considered.Notation 7 We denote by A a set of propositional symbols or atoms. We denote by Lcthe classical propositional language containing A, the usual constants false and true, and the usual connectives ¬, ∨, and ∧. We denote by Fcthe set of all wffs of Lc.We recall a possible meaning for the logic FOUR more details can be found in [CLM99, Bel77a, Bel77b]. Consider a system in which there are, on the one hand, sources of ination and, on the other hand, a processor that listens to them. The sources provide ination about the atoms only, not about the compound ulas. For each atom p, there are exactly four possibilities either the processor is ined by the sources, taken as a whole that p is true; or he is ined that p is false; or he is ined of both; or he has no ination about p.Notation 8 Denote by 0 and 1 the classical truth values and define f {0};t {1};⊤ {0,1};⊥ ∅.Theglobalinationgivenby the sourcesto the processorcanbe modelledby a functions fromA to {f,t,⊤,⊥}. Intuitively, 1 ∈ sp means the processor is ined that p is true, whilst 0 ∈ sp means he is ined that p is false. Then, the processor naturally builds ination about the compound ulas from s. Before he starts to do so, the situation can be be modelled by a function v from Fcto {f,t,⊤,⊥} which agrees with s about the atoms and which assigns ⊥ to all compound ulas. Now, take p and q in A and suppose 1 ∈ vp or 1 ∈ vq. Then, the processor naturally adds 1 to vp ∨ q. Similarly, if 0 ∈ vp and 0 ∈ vq, then he adds 0 in vp ∨ q. Of course, such rules hold for ¬ and ∧ too. Suppose all those rules are applied recursively to all compoundulas. Then, v represents the “full” or developed ination given by the sources to the processor. Now, the valuations of thelogic FOUR can be defined as exactly those functions that can be built in this manner i.e. like v from some ination sources. More ally,5Definition 9 We say that v is a four-valuedvaluationiff v is a function from Fcto {f,t,⊤,⊥} such that vtrue t, vfalse f and ∀ α,β ∈ Fc, 1 ∈ v¬α iff 0 ∈ vα; 0 ∈ v¬α iff 1 ∈ vα; 1 ∈ vα ∨ β iff 1 ∈ vα or 1 ∈ vβ; 0 ∈ vα ∨ β iff 0 ∈ vα and 0 ∈ vβ; 1 ∈ vα ∧ β iff 1 ∈ vα and 1 ∈ vβ; 0 ∈ vα ∧ β iff 0 ∈ vα or 0 ∈ vβ. We denote by V4the set of all four-valued valuations.The definition may become more accessible if we see the four-valued valuations as those functions that satisfy Tables 1, 2, and 3 belowvαv¬α ft tf ⊤⊤ ⊥⊥ Table 1.vβ ft⊤⊥vαfft⊤⊥ ttttt ⊤⊤t⊤t ⊥⊥tt⊥ vα