Inductive inference operators capture the process of completing a conditional belief base to an inference relation. One such operator is c-inference which is based on the c-representations of a belief base, c-representations being a special kind of ranking functions. c-Inference exhibits many desirable properties put forward for nonmonotonic reasoning; for instance, it fully complies with syntax splitting. A characterization of c-inference as a constraint satisfaction problem (CSP) yields a basis for implementing c-inference. However, the definitions of c-representations and of c-inference only take belief bases into account that satisfy a rather strong notion of consistency requiring every possible world to be at least somewhat plausible. In this paper, we extend the definition of c-representations to belief bases that need to satisfy only a weaker notion of consistency where some worlds may be completely infeasible. Based on these extended c-representations, we also extend the definition of c-inference correspondingly, thus covering all weakly consistent belief bases. Furthermore, we develop an adapted CSP characterizing the such extended c-inference that can be used as a basis for an implementation.
Ranking functions [
The notion of c-inference was introduced in [
The c-representations of a belief base ∆ can be
characterized by a constraint satisfaction problem (CSP), and
in [
To summarize, the main contributions of this paper are: • extension of c-representations for all weakly consistent belief bases; • extension of c-inference to all weakly consistent belief bases; • proof of some key properties of extended cinference; • construction of a CSP describing extended crepresentations and then development of a simplified version of this CSP; • development of a CSP realizing extended cinference.
Thus, ∆ is strongly consistent if there is at least one ranking function modelling ∆ that considers all worlds A (propositional) signature is a finite set Σ of proposi- feasible. This notion of consistency is used in many aptional variables. Assuming an underlying signature Σ , proaches, e.g., [12]. The notion of weak consistency is we denote the resulting propositional language by ℒΣ. equivalent to the more relaxed notion of consistency that Usually, we denote elements of signatures with lower- is used in, e.g., [13, 14]. Trivially, strong consistency case letters , , , . . . and formulas with uppercase let- implies weak consistency. ters , , , . . .. We may denote a conjunction ∧ by and a negation ¬ by for brevity of notation.
The set of interpretations over the underlying signature 3. Inductive Inference is denoted as Ω Σ. Interpretations are also called worlds and Ω Σ the universe. An interpretation ∈ Ω Σ is a The conditional beliefs of an agent are formally captured model of a formula ∈ ℒ if holds in , denoted as by a binary relation |∼ on propositional formulas with |= . The set of models of a formula (over a signature |∼ representing that (defeasibly) entails ; this Σ ) is denoted as Mod Σ() = { ∈ Ω Σ | |= } or relation is called inference or entailment relation. Difershort as Ω . The Σ in Ω Σ, ℒΣ and Mod Σ() can be ent sets of properties for inference relations have been omitted if the signature is clear from the context or if the suggested in literature, and often the set of postulates underlying signature is not relevant. A formula entails called system P is considered as minimal requirement for a formula , denoted by |= , if Ω ⊆ Ω . By slight inference relations. Inference relations satisfying system abuse of notation we sometimes interpret worlds as the P are called preferential inference relations [15, 16]. corresponding complete conjunction of all elements in Every ranking function induces a preferential inferthe signature in either positive or negated form. ence relation |∼ by
A conditional (|) connects two formulas , and
represents the rule “If then usually ”, where |∼ if () = ∞ or () < (). (1)
is called the antecedent and the consequent of the Note that the condition () = ∞ in (1) ensures that
conditional. The conditional language is denoted as system P’s axiom (Reflexivity): |∼ is satisfied for
(dℒit|iℒon)Σals=is{c(alle|d)a |beli,efb∈aseℒ.ΣW}e. Ausefiniatethsereteo-fvacolune-d I≡n⊥duc.tive inference is the process of completing a given
semantics of conditionals in this paper [
Note that there are diferent definitions of consistency inferences that can be obtained by iteratively applying
of a belief base in the literature. To distinguish two difer- the rules of system P to the belief base. Every other
preferent notions of consistency that both occur in this paper ential inductive inference operator extends p-entailment.
we call one notion of consistency strong consistency and While extending p-entailment and adding some more
the other notion weak consistency, as suggested in [
Definition 1 ([
An inductive inference operator : ∆ ↦→ |∼ Δ satisfies (Classic Preservation) if for all belief bases ∆ and , ∈ ℒ it holds that |∼ Δ ⊥ if |∼ Δ ⊥.
System Z is an inductive inference operator that is defined based on the Z-partition of a belief base [ 17].
Here we use an extended version of system Z that also covers weakly consistent belief bases and that was shown to be equivalent to rational closure [18] in [19].
Let us illustrate weak and strong consistency with an example.
Example 1. Let Σ = , , , be a signature. The belief bases ∆ 1 = {(⊥|⊤)} and ∆ 2 = {(⊥|), (|), (|)} are not weakly consistent and thus also not strongly consistent. The belief base ∆ 3 = {(⊥|)} is weakly consistent but not strongly consistent. The belief base ∆ 4 = {(|), (|)} is strongly consistent and thus also weakly consistent.
Definition 3 ((extended) Z-partition). A conditional (|) is tolerated by ∆ = {(|) | = 1, . . . , } if there exists a world ∈ Ω such that verifies (|) For every weakly consistent belief base ∆ there is a and does not falsify any conditional in ∆ , i.e., |= world that does not falsify any conditional in ∆ . and |= ⋀︀
=1( ∨ ).
The (extended) Z-partition EZP (∆) = (∆ 0, . . . , ∆ , Lemma 3. For every weakly consistent belief base ∆ there ∆ ∞) of a belief base ∆ is the ordered partition of ∆ that is is an ∈ Ω s.t. does not falsify any conditional in ∆ . constructed by letting ∆ be the inclusion maximal subset of ⋃︀ = ∆ until ∆ +1 =
= ∆ that is tolerated by ⋃︀ ∅. The set ∆ ∞ is the remaining set of conditionals that contains no conditional which is tolerated by ∆ ∞.
Proof. Because ∆ is weakly consistent, there is a ranking function with |= ∆ . Let ∈ − 1(0). Towards a contradiction, assume that there is a (|) ∈ ∆ that is
Because the ∆ are chosen inclusion-maximal, the Z- falsified by , i.e., |= . For to accept (|) it partition is unique [17]. must be either () = ∞ or () < (). Because |= and () = 0 we have () ̸= ∞. Because Definition 4 ((extended) system Z). Let ∆ be a belief () ⩽ 0 and there are no ranks below 0 the condition base with EZP (∆) = (∆ 0, . . . , ∆ , ∆ ∞). If ∆ is not () < () does not hold. This is a contradiction; weakly consistent, then let |∼ Δ for any , ∈ ℒ. hence does not falsify any conditional in ∆ .
Otherwise, the (extended) Z-ranking function Δ is deifned as follows: For ∈ Ω , if one of the conditionals in It is well-known that the construction of the extended ∆ ∞ is applicable to define Δ() = ∞. If not, let ∆ be Z-partition EZP (∆) is successful with ∆ ∞ = ∅ if ∆ the last partition in EZP (∆) that contains a conditional is strongly consistent. We can also use the extended Zfalsified by . Then let Δ() = + 1. If does not fal- partition to check for weak consistency. The following sify any conditional in ∆ , then let Δ() = 0. (Extended) proposition summarizes the relations between EZP (∆) system Z maps ∆ to the inference relation |∼ Δ induced by and the consistency of ∆ . Δ.
For strongly consistent belief bases the extended system Z coincides with system Z as defined in [ 17, 12]. Note that for any belief base ∆ the OCF Δ is a model of ∆ .
Lemma 1 ([
Lemma 2 ([
Proof. Direction ⇒: Assume that falsifies a conditional in ∆ ∞. Then this conditional is applicable for .
Direction ⇐: Assume that is applicable for at least one conditional (|) ∈ ∆ ∞. There are two possible cases: Either falsifies one of the other conditionals in ∆ ∞ or not. In the first case the lemma holds. In the second case, towards a contradiction, we assume that does not falsify (|). If is applicable and does not falsify (|) then must verify (|). That implies that (|) is tolerated by ∆ ∞ which contradicts the construction of EZP (∆) .
Proposition 1. Let ∆ = {(1|1), . . . , (|)} be a belief base with EZP (∆) = (∆ 0, . . . , ∆ , ∆ ∞). (1.) ∆ is not weakly consistent if ∆ ∞ = ∆ and 1 ∨ · · · ∨
≡ ⊤ . 1 ∨ · · · ∨
̸≡ ⊤ . (2.) ∆ is weakly consistent if ∆ ∞ ̸= ∆ or (3.) ∆ is strongly consistent if ∆ ∞ = ∅.
Continuing Example 1, for the not weakly consistent ∆ 2 we have EZP (∆ 2) = (∆ 2∞) with ∆ 2∞ = ∆ and ∨ ∨ ≡ ⊤ . For the weakly consistent ∆ 3 we have EZP (∆ 3) = (∆ 3∞) with ∆ 3∞ = ∆ but ̸≡ ⊤ . For the strongly consistent ∆ 3 we have EZP (∆ 4) = (∆ 40) with ∆ 40 = ∆ and ∆ 4∞ = ∅.
For strongly consistent belief bases, c-representations have been defined as follows.
Definition 5 (c-representation [
(2) We will denote the set of all c-representations of ∆ by Mod Σ(∆) .
A belief base ∆ that is not strongly consistent will not have a c-representation: by Definition 5, a crepresentation of ∆ is a finite ranking function modelling ∆ ; if ∆ is not strongly consistent, such a ranking function cannot exist.
To work with belief bases that are only weakly consistent, we need a more general definition of crepresentations. A ranking function that is a model of a weakly but not strongly consistent belief base must assign rank ∞ to some worlds. To achieve this while keeping a construction of c-representations similar to the one given in (2), we extend the definition of c-representations to allow infinite impacts. (|) ( |) (|)
impact on ⃗ () v f v f − − v v f f − − − − − − − − − − f f v v
Proof. Because ∆ is weakly consistent, there is at least one world ∈ Ω Σ that does not falsify any of the conditionals (see Lemma 3). This implies ⃗ () = 0. Thus, ⃗ is a ranking function.
For every (|) ∈ ∆ it holds that ⃗ () = ∞ Definition 6 (extended c-representation). An extended because every model of falsifies the conditional c-representation of a belief base ∆ = {(1|1), (|) with impact ∞. For ⃗ () we have either . . . , (|)} over Σ is a ranking function ⃗ con- (1.) ⃗ () = 0 or (2.) ⃗ () = ∞. In case structed from impacts⃗ = ( 1 , . . . , ) with ∈ (1.) we have ⃗ () = 0 < ∞ = ⃗ (). In N0 ∪ ∞, ∈ {1, . . . , } assigned to each conditional case (2.) we have ⃗ () = ∞ and ⃗ () = (|) such that ⃗ accepts ∆ and is given by: ∞ and therefore ⃗ () = ∞ because ⃗ () = ⃗ () = ∑︁ (3) (mi|n{)⃗. T(hus,) ,⃗ ⃗ |=( ∆.)}. In both cases ⃗ accepts 1⩽⩽ |= We will denote the set of all extended c-representations of ∆ by Mod Σ(∆) .
Example 2. Let Σ = {, , } and ∆ = {(|), ( |), (|)}. Note that ∆ is weakly consistent but not strongly consistent. Then the ranking function ⃗ displayed in Table 1 is an extended c-representation of ∆ induced by the impacts⃗ = (∞, 1, ∞).
Proposition 3 also illustrates that in extended crepresentations worlds may have rank infinity without the belief base requiring this. In an extended crepresentation of ∆ only those worlds need to have rank infinity that have rank infinity in the z-ranking Δ of ∆ .
Proposition 4. Let ∆ be a weakly consistent belief base.
If Δ() = ∞ for a world , then ⃗ () = ∞ for all c-representations ⃗ of ∆ .
Every c-representation of a strongly consistent belief Proof. Assume that Δ() = ∞. Let EZP (∆) = base ∆ is obviously an extended c-representation of ∆ . {∆ 0, . . . , ∆ , ∆ ∞} be the extended Z-partition of ∆ . By definition of Δ there exists a conditional (|) ∈ Proposition 2. Let ∆ be a strongly consistent belief ∆ ∞ s.t. |= . Because (|) ∈ ∆ ∞ the conditional base. Every c-representation ⃗ of ∆ is an extended c- (|) is not tolerated by ∆ ∞, so there is a conditional representation of ∆ . (′|′) ∈ ∆ ∞ that is falsified by (this can be (|) Proposition 6. Let ∆ be a belief base with EZP (∆) = again). {∆ 0, . . . , ∆ , ∆ ∞}, and let ∈ Ω . We have that
Towards a contradiction assume that there is a c- () = ∞ for all ∈ Mod Δ if |= for some representation ⃗ of ∆ with ⃗ () < ∞. As ⃗ models (|) ∈ ∆ ∞. ∆ and thus also (′|′) there must be a world 1 that verifies (′|′) and satisfies ⃗ (1) < ⃗ (). With the Proof. Direction ⇒ If () = ∞ for all ∈ Mod Δ same argumentation there must be another conditional then there is no ⃗ ∈ Mod Δ with ⃗ () < ∞. With (1|1) ∈ ∆ ∞ that is falsified by 1, and another world Proposition 5 this implies Δ() = ∞. By Definition 4 2 that verifies (1|1) and satisfies ⃗ (2) < ⃗ (1). this is the case if a conditional in ∆ ∞ is applicable for . Repeating this argumentation we obtain an infinite chain Assume |= for some (|) ∈ of worlds 1, 2, . . . s.t. ⃗ (1) > ⃗ (2) > . . .. But ∆ ∞D.irTehcetnio nΔ⇐() = ∞ and with Proposition 4 we have () = ∞ for all ∈ Mod Δ. as there are only finitely many worlds (and also because there are only finitely many ranks below ⃗ (1)) such a chain cannot exist. Contradiction.
Proposition 5. Let ∆ be a weakly consistent belief base.
There is a c-representation ⃗ of ∆ with ⃗ () < ∞ for all worlds with Δ() < ∞.
c-Inference [
Proof. Let ∆ = {(1|1), . . . , (|)} be a Definition 7 (c-inference, |∼ Δ [
⃗ is a c-representation of ∆ : Let (|) be any conditional in ∆ . If (|) ∈ ∆ ∞ then Δ() = ∞ by Definition 8 (extended c-inference, |∼ Δ). Let ∆ be a the definition of Δ which implies with Proposition 4 belief base and let , ∈ ℒ. Then is an extended cthat ⃗ () = ∞ and therefore ⃗ |= (|). Oth- inference from in the context of ∆ , denoted by |∼ Δ , erwise, we have (|) ∈ ∆ with < ∞. Then for if |∼ holds for all extended c-representations of any world ′ falsifying (|) we have ⃗ () > ; ∆ . hence ⃗ () ⩾ . Because (|) ∈ ∆ , there First, let us verify that extended c-inference is indeed issifya awcoornldditio′ntahlaitnv∆ erifie∪s · · · ∪(|∆ ) ∪an∆ d ∞do.eTshenroetfofrael-, wapitrhefce-riennfetiraelnicnedufocrtisvteroinnfgelryenccoensoipseternattobretlhieaft bcaosinesc.ides ⃗ () < . Thus, ⃗ () < ⩽ ⃗ () and ⃗ |= (|). Proposition 7. Extended c-inference is an inductive in
Furthermore, it holds that ⃗ () = ∞ if falsifies a ference operator. conditional in ∆ ∞. Therefore, ⃗ () < ∞ for all worlds with Δ() < ∞.
Using Proposition 4 we can see that for all worlds the c-representation constructed in the proof of Proposition 5 satisfies that ⃗ () < ∞ if Δ() < ∞. Using Lemma 1 we have ⃗ () < ∞ if does not entail ⊥ with p-entailment.
Lemma 4. Let ∆ be a weakly consistent belief base. There is an extended c-representation ⃗ of ∆ such that for all ∈ Ω we have ⃗ () < ∞ if |̸∼ Δ ⊥, where the world is considered as a formula on the right side of the “if”.
Another consequence of Propositions 4 and 5 is the following.
Proof. We need to show that extended c-inference satisifes (DI) and (TV). (DI) is trivial: Every c-representation of ∆ accepts the conditionals in ∆ by definition. Therefore, |∼ Δ for every (|) ∈ ∆ . (TV) is also clear: For ∆ = ∅ the only c-representation is = 0. In this case accepts only conditionals (|) with = ⊥, which are conditionals with |= .
Proposition 8. For strongly consistent belief bases, extended c-inference coincides with normal c-inference.
Proof. Let ∆ = {(1|1), . . . , (|)} be a strongly consistent belief base and , ∈ ℒ. We need to show that |∼ Δ if |∼ Δ .
Direction ⇒: Let |∼ Δ , i.e., every extended c- Proposition 9. Extended c-inference is preferential, i.e., representation models (|). As every c-representation it satisfies system P. is an extended c-representation (Proposition 2), every c-representation models (|). Thus, |∼ . Proof. Every ranking function, and thus every extended repDreirseecnttiaotinon⇐m:odeLlest(|)|∼. ΔWe nee,di.teo., sheovwerythact- tci-ornep.rTehseenitnatteiorsne,citniodnucoefstwaoprperfeerfeernetniatliailnifnefreernecnecererlae-any extended c-representation ⃗ models (|). If⃗ lations is again preferential. As extended c-inference is contains only finite values it is a c-representation and the intersection of the inference relations induced by thus models (|) by assumption. each extended c-representation, extended c-inference is
Assume that ⃗ contains infinite entries. Let preferential.
EZP (∆) = {∆ 0, . . . , ∆ , ∆ ∞} be the extended toler- Proposition 9 implies that extended c-inference capahnacvee p∆ar∞tit=ion∅o.fL∆ et. fBien⃗c(au)s=e∆ { is s|tro∈ng{ly0,c.o.n.s,ist}en,t,w<e tu.reFsurpt-heenrtmaiol mree,netx,teid.ee.,d icf-infer|∼enΔce cointhciedneswit|∼h Δp∞} be the set of finite values in impact vector ⃗ and entailment on entailments of the form |∼⊥ which can 0 = 1 + |fin⃗( )| · max(fin⃗( )). Now construct⃗ be seen as representations of “strict” beliefs (i.e., is from⃗ as follows. For (|) ∈ ∆ 0 with = ∞ let completely unfeasible). = 0. Let 1 = (0 + 1) · |{ (|) ∈ ∆ 0 | = ∞}|. For (|) ∈ ∆ 1 with = ∞ let = 1. Proposition 10. Extended c-inference satisfies (Classic Let 2 = (1 + 1) · ⃒⃒ {(|) ∈ ∆ 1 | = ∞}⃒⃒ . For Preservation). (|) ∈ ∆ 1 with = ∞ let = 2; and so on.
By construction the sum of the impacts in fin⃗( ) is less than 0 and the sum of the impacts of the conditionals in ∆ 0 ∪ · · · ∪ ∆ is less than for = 0, . . . , .
Let = ⃗ . Now verify that:
Proof. We need to show that |∼ Δ ⊥ if |∼ Δ ⊥.
Using Lemma 1 it is suficient to show that |∼ Δ ⊥ if () = ∞.
Direction ⇐: Let Δ() = ∞. Then Proposition 4 states that ⃗ () = ∞ for every c-representation ⃗ () of ∆ . Thus, |∼ Δ ⊥.
Direction ⇒: Let |∼ Δ ⊥, i.e., there is no crepresentation ⃗ of ∆ s.t. ⃗ () < ∞. By Proposition 5 we have Δ() = ∞. 2. |∼ ⊆ |∼
an inference in |∼ ⃗ . 1. is a c-representation of ∆ . For this we need to check that models all conditionals in ∆ .
⃗ , i.e., every inference in |∼ is also From (1.) it follows that is a model of (|), because Extended c-inference does not satisfy Rational |∼ Δ . With (2.) it follows that (|) is modelled Monotony (RM) as c-inference already violates (RM). by ⃗ .
Ad (1): Let (|) ∈ ∆ . We distinguish three cases.
Case 1: ⃗ () < ⃗ () < ∞ 7. CSPs for Extended In this case () < () < 0 and therefore c-Representations |= (|).
Case 2: ⃗ () < ∞ and ⃗ () = ∞ In this section, we investigate constraint satisfaction In this case () < 0 < () and therefore problems (CSPs) dealing with extended c-representations. |= (|). In Section 7.1, after presenting a constraint system de
Case 3: ⃗ () = ∞ and ⃗ () = ∞ scribing all extended c-representations of a belief base, As|s=umethaatn(d|fal)siifiessinn o∆ co.nTdhiteionntahleirne i s∆ a0w∪o· · r·∪ld ∆ s.t.. wtaekedsevtheeloepfecatssiomfpcloificnadtiitoionnoaflsthinis c∆on∞strianitnotascycsoteumnttrhigatht Therefore, () < and thus () < . Any from the beginning. In Section 7.2 we show how extended model of falsifies (|), therefore () > c-inference can be realized by a CSP. . Thus, we have () < < () and theArdef(o2r.e): Ass|=um(eth|at). |∼ . There are two cases. 7.1. Describing Extended
Case 1: ( ) < 0 c-Representations by CSPs In this case ( ) < ( ) < 0 and therefore ⃗ ( ) < ⃗ ( ) < ∞. Hence, |∼ ⃗ .
Case 2: ( ) ⩾ 0 In this case ⃗ ( ) = ∞ and therefore |∼ ⃗ .
Let us continue by showing some further properties of extended c-inference.
The c-representations of a belief base ∆ can conveniently
be characterized by the solutions of a constraint
satisfaction problem. In [
For a belief base ∆ = {(1|1), . . . , (|)} over Σ the constraint satisfaction problem for c-representations of ∆ , denoted by CRΣ(∆) , on the constraint variables { 1, . . . , } ranging over N0 is given by the constraints cr Δ, for all ∈ {1, . . . , }: (cr Δ)
The constraint cr Δ is the constraint corresponding to the conditional (|). The sum terms are induced by the worlds verifying and falsifying (|), respectively.
A solution of CRΣ(∆) is an -tuple ( 1, . . . , ) ∈ N0. For a constraint satisfaction problem CSP , the set of solutions is denoted by Sol (CSP ). Thus, with Sol (CRΣ(∆)) we denote the set of all solutions of CRΣ(∆) . The solutions of CRΣ(∆) correspond to the c-representations of ∆ .
Proposition 11 (soundness and completeness of
CRΣ(∆) [
Mod Σ(∆) = { ⃗ |⃗ ∈ Sol (CRΣ(∆)) } (4) Let (|) ∈ ∆ . There are three cases.
Case 1: ⃗ () = ∞ and ⃗ () = ∞ In this case ⃗ () = ∞ and therefore ⃗ |= (|).
Case 2: ⃗ () = ∞ and ⃗ () < ∞ In this case ⃗ ( > ⃗ () < ∞ and therefore ⃗ |= (|).
Case 3: ⃗ () < ∞ In this case min∈ΩΣ ∑︀ 1⩽⩽ = ⃗ () <
|= |= ∞; hence the condition in (cr Δ) before the or is not satisfied.
Because⃗ ∈ Sol (CRΣ(∆)) it must satisfy all constraints in CRΣ(∆) including (cr Δ). Because the condition before the or is violated, it must hold that ⇔ ⇔ ⇔ min ∈ΩΣ ̸= |= |= min ∈ΩΣ ̸= |= |=
If we want to construct a similar CSP for extended c-representations, we have to take worlds and formulas with infinite rank into account. and therefore ⃗ |= (|).
Completeness: Let ⃗ be an extended cDefinition 9 (CRΣ(∆) ). Let ∆ = {(1|1), . . . , representation of ∆ with impact vector ⃗ . We (|)} be a belief base over Σ . The constraint satisfac- need to show that⃗ ∈ Sol (CRΣ(∆)) , i.e., that⃗ tion problem for extended c-representations of ∆ , denoted satisfies every constraint ( cr Δ) in CRΣ(∆) . Because by CRΣ(∆) , on the constraint variables { 1, . . . , } ⃗ is an extended c-representation of ∆ , we have ranging over N0 ∪ {∞} is given by the constraints cr Δ, ⃗ |= (|). This requires either (1.) ⃗ () = ∞ for all ∈ {1, . . . , }: or (2.) ⃗ () > ⃗ (). In case (1.) it is min∈ΩΣ ∑︀ 1⩽⩽ = ⃗ () = ∞ and the (cr Δ) min ∑︁ = ∞ or |= |=
∈|=ΩΣ 1|=⩽⩽ wcoencdaitniosneebewfoitrhe tthhee oerquiniv(eclrencΔe)triasnsasftoisrfiemd.aItniocnassein(2t.h)e > ∑︁ − ∑︁ tShoeunodrnisesssatpiasfiertd.oIfnthbiosthprcoaosefsth⃗at stahteiscfieosn(dcitri on Δb)e.hind ⃗ () > ⃗ () Proof. Soundness: Let⃗ be an impact vector in Sol (CRΣ(∆)) . Because ∆ is weakly consistent, there is a world that does not falsify any conditional in ∆ ; therefore ⃗ () = 0 and ⃗ is a ranking function. It is left to show that ⃗ satisfies all conditionals in ∆ .
The requirement for weak consistency in Proposi
Again, each constraint cr Δ corresponds to the con- tion 12 is necessary because for a belief base ∆ that ditional (|) ∈ ∆ . is not weakly consistent it holds that Mod Δ = ∅ but Sol (CRΣ(∆)) = ( ∞, . . . , ∞). If we rule out the soluProposition 12 (soundness and completeness of tion (∞, . . . , ∞) by adding a constraint, Proposition 12 CRΣ(∆) ). Let ∆ = {(1|1), . . . , (|)} be a also holds for not weakly consistent belief bases. weakly consistent belief base over Σ . Then we have: The resulting CSP CRΣ(∆) is not a conjunction of inequalities any more, but it now contains disjunctions Mod Σ(∆) = { ⃗ |⃗ ∈ Sol (CRΣ(∆)) } (5) and is thus more complex. However, for the computation of extended c-inference we can construct a simplified CSP CRS Σ(∆) that still yields all extended c-representations necessary for c-inference. This is possible, because from Propositions 4 and 5 we already know which worlds must have rank infinity and which worlds may have
Soundness: is a vector⃗
Because = ∈ Sol (CR∈SΣ( ∆))+∞. By definition, there
Let⃗ Δ such tha⃗t
=⃗ +∞.
∞ for every (|) ∈ ∆ ∞ and due to Mod Δ. in ∆ ∞ is applicable have rank ⃗ () = ∞. Therefore,
Lemma 2, all worlds for which one of the conditionals all conditionals in ∆ ∞ are accepted by ⃗ .
For any conditional (|) ∈ ∆
∖ ∆ ∞ there is at least one world that verifies
(|) without falsifying a conditional in ∆ ∞ (otherwise (|) would not be tolerated by ∆ ∞). Because every world that falsiifes a conditional ( | ) with ∈/ Δ also falsifies
∞, the world does not falsify any Otherwise, for ⃗ () < such conditional ( | ) with impact ∞. Therefore, ⃗ () < ∞. If ⃗ () = ∞ then ⃗ |
= (|).
∞, there is a world that falsifies
(|) without falsifying a conditional in ∆ ∞.
In this case it is ∈ Δ and the CSP CRS Σ(∆) the constraint (crs Δ) which must hold for⃗ :
contains holds for all c-representations in Mod Δ if |∼ in Mod Δ.
Proof. Direction ⇐: Observe that Mod Δ ⊆ Therefore, if |∼ holds for all c-representations in Mod Δ, then |∼ holds for all c-representations
Direction ⇒: Show this by contraposition. Assume of i∈n thMepodroΔofwoifthProp|≁o sitio.nU8siwnge tchaencfinodnsatruct′io=n that that is a c-inference of ∆ c-representation ′ with |̸∼ ′ .
Therefore, if |≁ then |≁ ′ . Hence, there is a
As already indicated above, the c-representations in Mod Δ can then be represented by a simplified CSP.
Definition 11 (CRS Σ(∆) ). Let ∆ = ance partition EZP (∆) = (|)} be a belief base over Σ with the extended toler
{(1|1), . . . , { ∆ 0, . . . , ∆ , ∆ ∞}. Let Δ = { |( | ) ∈ ∆ ∖ ∆ ∞ s.t.
The simplified constraint satisfaction problem for extended c-inference of ∆ , denoted by CRS Σ(∆) , on the constraint variables { 1 , . . . , },
∈ Δ ranging over N0 is given by the constraints crs Δ, for all ∈ Δ: (crs Δ) ⇔ ⇔ (* ) ⇔ ⇔ ⃗ () > ⃗ ().
Therefore, ⃗ |= (|).
The equivalence (* ) holds, because there is a model for
̇ that does not falsify a conditional in ∆ ∞, we have = ∞ for all ( | ) with ∈/ Δ, and therefore min ∈ΩΣ ∈Δ |=˙ |= ∑︁ = min ∈ΩΣ 1⩽⩽ |=˙ |= ∑︁
For any world with Δ() < ∞ it holds that all conditionals in ∆ ∞ are not applicable in . Therefore, ⃗ () is the sum of some of the impacts in⃗ ; and because⃗ ∈ N0 we have ⃗ () < ∞.
In summary, ⃗ ∈ Mod Δ.
Completeness: Let ∈ Mod Δ be an extended c-representation. Let⃗ ∈ (N0 ∪ ∞) be an impact vector such that = ⃗ . Because of Proposition 13, w.l.o.g. we can assume = ∞ for all (|) ∈ ∆ ∞.
Furthermore, w.l.o.g, we can assume = ∞ for all conditionals (|) ∈ ∆ ∖ ∆ ∞ which are falsified only by worlds that also falsify a conditional in ∆ ∞ – all worlds for which these impacts apply already have rank ∞ because of the impacts for ∆ ∞.
The vecto⃗r is a combination of a vecto⃗r of impacts for ∈ Δ, and a vector (∞, . . . , ∞) of size − | Δ| of impacts for conditionals ( | ) with ∈/ Δ.
For every ∈ Δ, by construction of Δ there is at least one world falsifying (|) without falsifying a conditional in ∆ ∞. Then, Δ() < ∞ because falsifies no conditionals in ∆ ∞ and due to Lemma 2; therefore < ⃗ () < ∞ because ⃗ ∈ Mod Δ.
Hence⃗, ∈ N0.
It is left to show that⃗ is a solution of CRS Σ(∆) , i.e., that for every ∈ Δ it satisfies the constraint (crs Δ). As ⃗ is a model of ∆ , it satisfies the conditional ( | ) ∈ ∆ . By construction of Δ, there is at least one world falsifying ( | ) without falsifying a conditional in ∆ ∞. As established above, the rank of such a world in ⃗ is finite, and thus ⃗ () is finite. To satisfy( | ) it is necessary that ⃗ () > ⃗ (). Using the equivalence transformation in the Soundness part of this proof, we obtain that (crs Δ) holds for .
The following example illustrates how CRS Σ(∆) is simpler than CRΣ(∆) .
Example 3. Let Σ = {, , } and ∆ = {(⊥|), (|), (|)}. The CSP CRΣ(∆) over 1, 1, 3 ∈ N0 ∪ ∞ contains the constraints min ∈ΩΣ ̸=1 |=∧⊥ |= ∑︁
The extended Z-partition of ∆ is EZP (∆) = (∆ 0, ∆ ∞) with ∆ 0 = {(|), (|)} and ∆ ∞ = {(⊥|)}. The conditional (|) cannot be falsified without also falsifying (⊥|) ∈ ∆ ∞. Therefore, Δ = {3} and the CSP CRS Σ(∆) over 3 ∈ N0 contains only the constraint (crs3 Δ) 3 >
∑︁ min ∈|=ΩΣ ∉=3Δ |=
∑︁
which simplifies to 3 > 0. For⃗ ∈ +∞ it holds that
Δ 1 = 2 = ∞ and 3 ∈ Sol (CRS Σ(∆)) .
In [
solutions⃗ of CRΣ(∆) . Based on this idea, we develop a CSP that allows doing something similar for extended c-inference.
In this paper, we introduced extended c-representations
as a generalization of c-representations for also
Definition 13. Let ∆ = {(1|1), . . . , (|)} be a weakly consistent belief bases. Based on extended
belief base and let Δ be as defined in Definition 11. The c-representations we developed extended c-inference
constraint ¬CRΔ(|) is given by which is an extension of c-inference. We investigated
min ∑︁ ⩾ min ∑︁ . (7) the basic properties of extended c-representations and
|= ∈Δ |= ∈Δ extended c-inference. Additionally, we developed a CSP
|= |= that characterizes extended c-representations. We
introProposition 17. Let ∆ be a weakly consistent belief base. duced a simplified version of this CSP that still describes
Then |∼ Δ if either Δ() = ∞ or (︀ Δ() < all extended c-representations relevant for c-inference,
∞ and CRS Σ(∆) ∪ ¬CRΔ(|) is unsolvable )︀ . and we showed how extended c-inference can be
realized by a CSP. Note that our concept of extended
Proof. Direction ⇒: Assume that |∼ Δ and that c-representations can be used not only to define extended
Δ() < ∞. Then () < ∞ for all ∈ Mod Δ c-inference; analogously, it yields extended versions of
by the definition of Mod Δ. Therefore, () < ∞ for credulous and weakly skeptical c-inference [20, 21]
covall ∈ Mod Δ. Furthermore, |∼ Δ implies that ering also weakly consistent belief bases.
for every ∈ Mod Δ, we have |∼ . Therefore, Nonmonotonic inference is closely connected to belief
() < () for every ∈ Mod Δ, and because revision [22]. The idea that some formulas are completely
of Proposition 15 ⃗ () < ⃗ () for every⃗ ∈ infeasible, that is used for inference here, also occurs in
Δ+∞. We have credibility limited revision [
Therefore, ¬CRΔ(|) does not hold for any so- c-inference and to other inductive inference operators
lution of CRS Σ(∆) , implying that CRS Σ(∆) ∪ taking also weakly consistent belief bases into account.
¬CRΔ(|) is unsolvable. Similarily as it has been done for c-inference [
Direction ⇐: Assume that either Δ() = ∞ plan to realize extended c-inference as a SAT and as an
or (︀ Δ() < ∞ and CRS Σ(∆) ∪ ¬CRΔ(|) is SMT problem and to implement it in the InfOCF platform
unsolvable )︀ . There are three cases. [
Case 1: Δ() = ∞ and Δ() = ∞ Then Δ() = ∞ and, by Proposition 4, () = ∞ for every ∈ Mod Δ. Therefore |∼ Δ .
Case 2: Δ() < ∞ and Δ() = ∞ Then, by the definition of Mod Δ, we have () < ∞ and, by Proposition 4, () = ∞ for every ∈ Mod Δ. Therefore, () < () for every ∈ Mod Δ and hence |∼ Δ by Proposition 14.
Case 3: Δ() < ∞ Then, by assumption, CRS Σ(∆) ∪ ¬CRΔ(|) is unsolvable and Δ() < ∞. This implies that ¬CRΔ(|) is false for every⃗ ∈ Sol (CRS Σ(∆)) .
In this case, using the equivalence transformations in the part of the proof for Direction ⇒, we have ⃗ () < ⃗ () for every⃗ ∈ Δ+∞. With Proposition 16 it follows that |∼ Δ .
This work was supported by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation), grant BE 1700/10-1 awarded to Christoph Beierle as part of the priority program “Intentional Forgetting in Organizations” (SPP 1921). Jonas Haldimann was supported by this grant.