arXiv:cs/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

[email protected] 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 information and the clas-sical consequence relation proves to be insufficient. Indeed, in case of inconsistent information, it leads to accept every formula as a conclusion, which amounts to loose the whole information. 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,CMdA00, dACM02, AA94, AA96, AA98]. They are defined in frameworks where valuations can assign more than two different truth values to formulas. In fact, they tolerate contradictions within theconclusions,butrejecttheprincipleofexplosionaccordingtowhicha singlecontradictionentails the deduction of every formula. In case of incomplete information, the classical consequence relation also shows its limits. In- deed,no risk is taken, the conclusionsare sure, but toofew. We needotherrelationsleadingto accept as conclusions formulas that are not necessarily sure, but still plausible. Eventually, some “hasty” conclusions will be rejected later, in the presence of additional information. 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 formula α follows from a set of formulas Γ 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 information 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 information. On the other hand, neither the web nor big databases can contain “all” information. Indeed, there are rules of which the exceptions cannot be enumerated. Also, some information might be left voluntarily vague or in concise form. 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 accordingtosomeparticularbinarypreferencerelationonvaluations(inthestyle 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 formulas 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 information, we will simply conclude nothing. On the other hand, in the many-valued frameworks, where the conclusions are non-trivial even from incon- sistent information, 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 (sub)families of preferential(-discriminative)consequencerelations. 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(-discriminative)consequencerelations 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 formulas, 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 formulas, V a set of valuations for these formulas, and |= a satisfactionrelation for these objects (i.e. v |= α means the formula α 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 |= α}, T(V ) := {α ∈ 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, Td(V ) := {α ∈ F : V ⊆ Mαand V 6⊆ M¬α}, Tc(V ) := {α ∈ 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 T(V ) the set of all formulas satisfied in V . Every element of T(V ) belongs either to Td(V ) or Tc(V ), according to whether its negation is also inT(V ). D is the set of all those sets of valuations that are definable by a set of formulas and C the set of all those sets of valuations that do not satisfy both a formula and its negation. As usual, MΓ,α, T(V,v) stand for respectively MΓ∪{α}, T(V ∪ {v}), etc.Remark 3 The notations MΓ, T(V ), 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 relation:Notation 4 We denote by P the power set operator. Let hF,V,|=i be a semantic structure. We denote by ⊢ the relation on P(F) × F such that ∀ Γ ⊆ F, ∀ α ∈ F,Γ ⊢ α iff MΓ⊆ Mα.Let |∼ be a relation on P(F) × 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 sequel:Remark 5 Let hF,V,|=i be a semantic structure and Γ,∆ ⊆ F. Then: MΓ,∆= MΓ∩ M∆; ⊢(Γ) = T(MΓ); MΓ= M⊢(Γ); Γ ⊆ ⊢(∆) iff ⊢(Γ) ⊆ ⊢(∆) iff M∆⊆ MΓ.Sometimes, we will need some of the following assumptions about a semantic structure:Definition 6 Suppose hF,V,|=i is a semantic structure.Then, define the following assumptions about it:(A1) V is finite.4Suppose L is a language, ¬ a unary connective of L, and F the set of all wffs of L. Then, define:(A2) ∀ Γ ⊆ F, ∀ α ∈ F, if α 6∈ T(MΓ) and ¬α 6∈ T(MΓ), then MΓ∩ Mα6⊆ M¬α.Suppose ∨ and ∧ are binary connectives of L. Then, define:(A3) ∀ α,β ∈ 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 information. 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 information and, on the other hand, a processor that listens to them. The sources provide information about the atoms only, not about the compound formulas. For each atom p, there are exactly four possibilities: either the processor is informed (by the sources, taken as a whole) that p is true; or he is informed that p is false; or he is informed of both; or he has no information about p.Notation 8 Denote by 0 and 1 the classical truth values and define: f := {0};t := {1};⊤ := {0,1};⊥ := ∅.Theglobalinformationgivenby the sourcesto the processorcanbe modelledby a functions fromA to {f,t,⊤,⊥}. Intuitively, 1 ∈ s(p) means the processor is informed that p is true, whilst 0 ∈ s(p) means he is informed that p is false. Then, the processor naturally builds information about the compound formulas 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 formulas. Now, take p and q in A and suppose 1 ∈ v(p) or 1 ∈ v(q). Then, the processor naturally adds 1 to v(p ∨ q). Similarly, if 0 ∈ v(p) and 0 ∈ v(q), then he adds 0 in v(p ∨ q). Of course, such rules hold for ¬ and ∧ too. Suppose all those rules are applied recursively to all compoundformulas. Then, v represents the “full” (or developed) information 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 information sources. More formally,5Definition 9 We say that v is a four-valuedvaluationiff v is a function from Fcto {f,t,⊤,⊥} such that v(true) = t, v(false) = 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 below:v(α)v(¬α) ft tf ⊤⊤ ⊥⊥ Table 1.v(β) ft⊤⊥v(α)fft⊤⊥ ttttt ⊤⊤t⊤t ⊥⊥tt⊥ v(α