Nonmonotonic Reasoning and Multiple Belief Revision

1 Introduction

In recent years much work has been done on the relation­ ship between nonmonotonic reasoning and belief revision [Makinson and Gardenfors 1991] [Brewka 1991] [Nebel 1992] [Cravo and Martins 1993] [Li 1993][Giirdenfors and Makinson 1994] [Boutilier 1994] [Gardenfors and Rott 1995] [Zhang 1996]. A very close correspondence be­ tween them has been found based on the following formal translation:

The main idea is to identify revision of a belief set /{ by a proposition A with nonmonotonic inference from A under the. guidance of the background knowledge /{. With this connection , it has been shown in [Makinson and Gardenfors 1991] [Gardenfors and Rott 1995] that each postulate for the belief revision function * can be translated into a plausible conditions on the nonmono­ tonic inference relation I"'; conversely, almost all the plausible condit ions on the nonmonotonic inference re­ lation in the literature can also be translated into condi­ tions on * that are consequences of the postulates for the revision function. In fact, it is not difficult to verify that the revision function * satisfies all eight postulates in [Gardenfors 1988] if and only if I"' satisfies the following five inference rules:

1. If A f- B , then AI"'B (Supraclassicality).
2. If Ar.- l. , then A f-l. (Consistency Preservation) .
3. If Ar.-Bi for all B; E r , r f- C, then Ar-c (Clo­ sure) .
4. If AABI"'C, then AI"'B----> C (Conditionalization).
5. If Ak--·B and AI"'C, then A A BI"'C (Rational Monotony) .

This translation may be extended to the finite case. If r is a finite set of propositions , written by { A1 , · · ·,An} , then:

As mentioned in [Makinson 1993], however, this extension muddies the 'neat' distinction between A1, ···,An I"' A and A1 A · · · A An I"' A. A possible im­ provement is to replace the revision operation with some sort of multiple revision function. Suppose we have had a multiple revision function ® such that /{ <19 F repre­ sents the result of revising a belief set /{ with a set F of propositions. The translation given below would be more natural :

This extension is also essential because it enables a treat­ ment of inference relation in which premises are arbitrary sets of propositions, including infinite sets. The questions arises naturally now that :

• how the nonmonotonic inference rules on I"' are ex­ tended to the infinite level so that they are still plau­ sible for nonmonotonic reasoners ;
• how an infinite revision framework is constructed so that it is a natural generalization of the original one;
• whether the strict correspondence between belief revision and nonmonotonic reasoning can be pre­ served in the setting of the extended frameworks .

Fortunately, the first question has been widely inves­ tigated in the literature [Makinson 1989] [Freund 1990]

[Makinson 1993] [Herre 1994], only the presentation of the extended rules is mostly in the Tarski-style's infer­ ence operation C.

As far as the generalization of belief revision are con­ cerned , [Zhang 1996] presented a kind of multiple revi­ sion framework , called general revision, which enables a treatment of revisions of belief set by arbitrary set of sentences. [Zhang et al. 1997] further developed the framework by providing two presentation theorems and suggesting an additional postulate to characterize the in­ finite properties of revision operations.

This paper is devoted to the last question. In the next section, we combine some of the nonmonotonic inference rules which have been suggested in the literature into a system of nonmonotonic reasoning, called RN, and dis­ cuss its properties. Section 3 outlines the general belief revision, and then, section 4 investigates the relationship between the system RN and the general belief revision. Section 5 presents a specific system of default reasoning which satisfies all the inference rules of RN. The last section discusses the inference power of RN and con­ cludes the paper.

2 Rational N onmonotonic Frame

This section will define a nonmonotonic frame of infer­ ence through combining generalized rules of the five non­ monotonic relations of inference mentioned above into a system, named RN. Although each of the generalized rules has been suggested in the literature, their prop­ erties as a whole have not been investigated. We start with the syntax of RN and then discuss its properties and derived rules.

We shall restrict the language of the indented system within any propositional language .C with the standard logical connect ives --, , V, 1\ and ___. . Elements of .C are called formulas which are denoted by A,B,C. Sets of formulas are denoted by r , ~' F and etc . There are two relations of inference between premises on the left and conclusions on the right : r ' denoting the classical propositional derivability, and h used for a nonmono­ tonic relation of inference. An associated Tarski-style's consequence operation may be defined by each of the re­ lations of inference in such manner:

It is presupposed that the inference relation r satisfies all the inference rules of the classical propositional logic so it is compact:

f f- A iff there exists a finite subset r 0 of r such that for A.

A set r of formulas is said to be closed if r = Cn(f). fHr)~ indicates that r""(r)A for all A E ~ (~may be empty) ; r }-A indicates that fjv A does not hold.

Definition 2.1 A system RN = (.C, "") is said to be a rational nonmonotonic frame if .C is a language of clas­ sical propositional logic at least including propositional connectives (· ,1\,V and___.) and 1~ is a relation from 2c to .C, called the rational nonmonotonic inference rela­ tion, if it satisfies:

(RNl) If r r A , then f""A (Supraclassicality).

• (RN2) Iff"" 1.., then r r l.. (Consistency Preserva­ tion).
• (RN3) Iffl~~ r A , then fj-vA (Closure or Weak Tran­ sitivity).
• (RN4) If r u ~I~A and ~ -::j:. ¢, then there arc A1,···,An E ~ su ch that fi~(Al 1\ ···1\An) ___.A (Infinite Condit ionalization) . ·
• (RN5) Iff ;}v ·(Al 1\ ···1\An) for all A1 , ···, An E ~ ~ then fi~A implies r u ~I~A (Infinite Rational Monotonicity).

Furthermore, a rational nonmonotonic frame is said to be finit e supra compact if it satisfies:

• (RN6) f""A iff there exists a finit e subset f 0 of r such that f o U f'""A for every finite subset f' of Cn(f) (Finit e Supracompactness ).

The name 'rational ' follows from [Lehmann and Magi­ dar 1992] [Herre 1994] but the rational inference relation here is stronger because the consistency preservation is added.

For those who are familiar with Tarski-style's non­ monotonic consequence operations, the following equiv­ alent presentation of the conditions (RNl) - (RN6) would be preferential.

1. Cn(f) ~ C(f)(Supraclassicality).
2. If Cn(f) -::j:. .C , then C(f) -::j:. £(Consistency Preser­ vation).
3. Cn(C(f)) ~ C(f)(Closur e).
4. C(r U ~) ~ Cn(f U C(~))(Infinite Conditionaliza­ tion) .
5. IF ~ u C(r) -::j:. .C , then C(f) ~ C(r u ~)(Rational Monotony).
6. fi~A iff there exists a finite subset f 0 of r such that f 0 U ~""A for every finite subset~ of Cn(f)(Finite Supracompactness) .

It should be noted that none of the above conditions is the authors' invention. They all have been suggested for nonmonotonic reasonings in the literature . In fact, the conditions 1-4 were presented in [Makinson 1993] and the last two conditions are found in [Herre 1994]1

1 In (Herre 1994] the finite supracompactness refers to that f f--A if there exists a finite subset fo of r such that fo U!::. f--A for every finite subset !::. of Cn(f). However the complete !::.2-compactness is just the meaning of the finite supracompatness in this paper.

In order to reveal the power of RN, we shall show that most of the inference rules for nonmonotonic reasoning suggested in the literature are derived rules of RN.

Lemma 2.2 The following rules are derived rules of RN:

• (1). fl~f (Reflexivity)
• (2). Iff , AI~B, -.B, then fi~-.A (Reductio ad Absur­ dum).
• (3). Iff , Af---B, then fi~A-+ B (Deduction Theorem).
• (4). If fi~A --. B and fi~A , then fi~B (Modus Po­ nens).

Proof: (1) follows (RN1). (2) follows (RN2) and (RN3) . (3) is the special case of (RN4) where .6. = {A}. For (4), since f I~A -+ B and f I~A, so r HA-+ B , A} f- B. By (RN3) we get f I~B. 0

The above theorem shows that 1~ satisfies all th~ for­ mal inference rules of classical propositional logic except for the following deductive transitivity:

Lemma 2.3 The following rules are derived rules of RN:

• (1). If fl~~ and f u ~I~A , then fi~A(Cumulative Transitivity)
• (2). If fl~~ and fi~A , then f U ~~~A(Cautious Monotony)
• (3). If fl~~ and ~~~f, then fi~A if and only if ~ 1~ A (Reciprocity)
• (4). Iff H ~ ~ then fi~A if and only if ~I~A.(Left Log­ ical Equivalence)
• (5). If A H B , then fi~A if and only if fi~B.(Right Logical Equivalence)

Proof: For (1), suppose that f ~~~(~ :f cfi) and f U .6. I~ A. Then , by (RN 4) , there exists A1, ···,An E ~ such that f I~(A 1 1\ ···/\An)-+ A. Since A1, · · ·, AnE ~ implies ~ f- A1 1\ · · · 1\ An, hence we obtain f I~ A by (RN3) and Theorem 2.2 (4).

For (2), suppose that f I~~ and f I~A. If there are A1 , ···,An E ~ such that f 1~-.(A1 1\ · · · 1\ An) , since r r-~ implies f I~A1 1\ ... 1\ An by (RN3), then we have f I~ l_ again by (RN3). It follows from (RN2) that f f-L By the compactness of the classical propo­ sitional logic , f U ~ f-1_ , so f U ~ f- A. By the Supra­ classicality, we have f u ~ I~A . If f A'~ -.(A1 1\ ... An) for any A1, ···,An E ~ , then by (RN5) and f I~ A, we have f u ~ I~ A as desired.

(3) follows from (1) and (2) . (4) follows from (RNl) and (3). (5) follows from (RN3). 0

As shown by [Makinson 1993], the Infinite Condition­ alization along with other rules implies the following Dis­ tributivity.

Lemma 2.4 If f u ~11~A, f u ~2I~A , then f u

(~1 V ~2)f"--A. Specially, if ~d·,·A and ~2r.-A , then ~1 V ~2r-A (Dis­

tribution).

where ~1 V ~2 ={A VB: A E ~1 and ~2}.

It is well-known that compactness is a very important property of the classical logic which provides a bridge be­ tween inferences of finite and infinite premises: f f- A iff fa f- A for some finite subset fa of f. But such equiv­ alence implies monotony, so this kind of compactness must fail in any nonmonotonic logic. This does not mean that there are no properties of compactness for the non­ monotonic logic. In fact there are a number of alterna­ tive versions of compactness for nonmonotonic reasoning proposed([Freund 1990] [Makinson 1993] [Herre 1994]).

[Freund 1990] suggested the following Supracompact­ ness for nonmonotonic inference:

fi~A iff there exists a finite subset fa off such that for any set of formulas~, fl~~ implies fa u ~I~A.

The following theorem shows that such supracompact­ ness follows from the finite supracompactness. This was also noted by [Freund 1990] and [Makinson 1993] with a little different setting.

Theorem 2.5 Any finite supracompact rational infer­ ence relation satisfies the Supracompactness.

Proof: It is enough to show that if fi~A then there exists a finite subset fa of f such that ff---~ implies fa u ~I~A. For this, let fi~A. By Finite Supracom­ pactness , there exists a finite subset fa of f such that fa u f'I~A for every finite subset f' of Cn(f) . Suppose that fl~~. Since Cn((fa U ~) V f) ~ Cn(f), the finite supracompactness implies that fa U f'I~A for every fi­ nite subset f' of Cn((fa U ~) V f). Again by the finite supracompactness, we have Cn((faU~) V f) I~ A (noting that fa ~ Cn((faU~) V f)). It follows by the left logical equivalence that (fa u ~) V fi~A. On the other hand, by fl~~ and the supraclassicality as well as Lemma 2.4, it is not difficult to verify that (fa U~) V fr-~. Thus by the cautious monotony we have~ U ((fa U ~) V f) f---A. Noting that ~ U ((fa U ~) V f) H fa U ~, we conclude from the left logical equivalence that fa U ~I~A as de­ sired. 0

On the basis of Makinson's work on general patterns in nonmonotonic reasoning, it is not difficult to see that any rational nonmonotonic relation of inference also sat­ isfies conditions such as Absorption, Cut, Cumulativ­ ity, Loop, Negation Rationality(see [Makinson 1989] and [Makinson 1993]) .

3 Multiple Belief Revision

This section recalls definitions and results on the multi­ ple belief revision. [Zhang 1995][Zhang 1996] introduced and further developed by [Zhang et a/. 1997] a frame­ work for multiple belief changes through extending the AGM theory([Gardenfors 1988]) . The extended revision function was called the general revision . Formally, a function K Q<O 2 : 2c --+ 2c with respect to a given belief set K is said to be a general revision fun ction over K if it satisfies the following nine postulates:

(I\ ® 2) F ~ K ® F.

{I\ C?J 3) IU <; F ~ K +F.

(I\ ® 4) If K U F is consistent, then J( + F ~ K ® F .

• (K ® 5) K ® F is inconsistent iff F is inconsistent.

(I\ ® 6) If C n(Fl) = Cn(F2), then K ® F1 = K ® F2.

{J\ ® 7) K ¢:o (F1UF2)~K ® F1+F2.

(K ® 8) If F2 U (K ® Fl) is consistent , then (I\ ® Fl) + F2~K ® (F1UF2).

where Cp = {F: F ~ Cn(F) and F is finite}.

The postulates (I\ ® 1)-(K ® 8) were presented in [Zhang 1996] and the last one, called the Limit Postu­ lat e, was introduced by [Zhang et al. 1997] . The repre­ sentation theorem for all nine postulates was given in [Zhang et al. 1997] based on the following notions :

For any set r of formulas , let P be a partition 3 of r and < a total-ordering( well-ordering) relation on P . For any p E P, if A E p , p is called the rank of A, denoted by b(A) .

The triple 'E = (r , P , <) is called a nice-ordered par­ tition(NOP) (perfect-ordered partition(POP)) of r if it satisfies the following Logical Constraint:

If A1 , .. · , An 1- B , then sup{b(A1) , .. ·, b(An)} 2: b(B) .

Now let K be a closed set of formulas and 'E = (K, P , < )a nice-ordered partition. A function ® : 2c--+ 2c is said to be the revision function generated by 'E if for any F ~ £ ,

i). ifF U J( is consistent , then K ® F = K + F ; oth­ erwise,

ii). B E K ® F if and only if B E K + F and there exists A E K such that F 1- ·A and

The original presentation of the representation theorem is based on the contraction function(see [Zhang et al. 1997]). The following theorem is obtained by using the interrelation of revision and contraction.

Theorem 3.1 For any closed set K of formulas , a re­ vision function ® satisfies (K ® 1)- (K ® 8) as well as ( K ® LP) if and only if there exists a nice-ordered parti­ tion 'E = (K , P , <) such that ® is the revision function generat ed by 'E.

2 In the present paper, K @ is also written as @K or @ if without confusion.

3 A partition of a set r is a disjoint family P of subsets of r such that r = U{P : p E P} .

4 Representation Theorem

In order to reveal the interrelation between RN and the multiple belief revision , we shall take revision operations as the semantic of RN rather than follow the traditional approach of Shoham's preferential models.

Theorem 4.1 (Soundn ess)Let £ be a language of propositional logic and K a consistent closed set in £ . Let ® be a general revision function over K. Defin e a relation 1~ ~ 2c x £ as follows: for any set r ~ £ and any formula A E £ ,

then (£, r-) is a finite supracompact rational non­ monotonic frame .

Proof: We need to show 1~ satisfies the rules (RN1) ­ (RN6) . For (RN1) , assume that r I~A . Since r ~ K ® r and K ® r is closed, thus A E K ® r , that is , r f-vA.

For (RN2) , assume that r 1~ 1_ , i.e. , l_E K® f , which means that K ® r is inconsistent. It follows by (I\ ® 5) that r is inconsistent. Thus r 1-L

For (RN3) , assume that r I~Ll 1- A which means that Ll ~ K ® rand A E Cn(Ll). By (K ® 1) , we have A E K ® r, i.e., r I~A.

For (RN4) , assume that r U Ll I~A , that is , A E K ® (r u Ll). By (K ® 7) , K ® (r u Ll) ~ K ® r + Ll , so we have A E K ® r + Ll . There exist then A1, · ··, An E Ll such that (A1 A ··· A An) --+ AE K ® r , that is r f-v(A1 A .. · A An )--+ A.

For (RN5) , iffor any A1 A··· A An ELl, r J~·(A1 A · · ·AAn), or ·(A1A · · ·AAn) fl. K 0 f , then LlU(K 0 r) is consistent. Therefore, when r f-vA , or A E K ® r , we conclude by (K@ 8) that A E K @ (r u Ll) , so r u Ll I~ A as desired.

For the finite supracompactness, suppose that @ sat­ isfies (K ® LP) , that is, A E K ® r iff there exists a finite subset r 1 of Cn(r) such that for any finite S \l b­ set f2 ~ Cn(f) , f 1 ~ f2 implies A E K ® f 2. It is easy to see that we only need to show that r I~A implies that there exists a finite subset r 0 of r such that fo U Ll I~A for every finite subset Ll of Cn(f). To this end, assume that r f-vA , that is A E K ® r. By (I\ 0 LP) , there exists a finite subset f 1 of Cn(r) such that for any finite subset r 2 of Cn(f), if r 1 ~ r 2, then A E K ® f2 . Let fo be a finite subset of r such that f 1 E Cn(f0 ) . For any finite subset Ll of Cn(f), since r o U r 1 U Ll is finite and also a subset of Cn(r) , we have A E K ® (fo U f1 U Ll). It follows from (I\ ® 6) that A E K ® Cn(fo U f1 U Ll). On the other hand, f1 ~ Cn(fo) implies Cn(fo U Ll) = Cn(fo u f 1 u Ll) . Thus we obtain that A E K ® Cn(f0ULl) . It follows from (K® 6) again that A E K ® (foULl), that is f0 ULli~A. D

Theorem 4.2 (Completeness) Let (£ , I~) be a finit e supracompact rational nonmonotonic frame. Let K = {A E £ : ¢I~A} . Define a function ® K : 2c --+ 2c as follows: for any F ~ £ ,

Then il!K is a general belief revision function over K.

Proof: We first prove that K is closed and consis­ tent. The consistency of K follows easily from (RN2) . To show that J{ is closed, let us assume that K f- A. There are then A1, · · ·, AnE K such that A1, · · ·, Anf- A. Hence ¢1~Al, · · ·, ¢ 1~An, that is¢ I~{Al, ···,An}. By (RN3) , we see ¢1~A and then A E K.

We now turn to show that 0 K satisfies all nine postu­ lates for the general belief revision.

Proof of ( K @ 1) is similar to that of closeness of K. (I( 0 2) follows immediately from the Reflexivity. ( K 0 3) and (I( ~ 4) are special cases of (I< 0 7) and (K 0 8), re­ spectively. (I( 0 5) follows directly from (RN2). (K 0 6) follows from the Reciprocity.

For (K 0<:1 7), assume that A E 0 K(Fl U F2), or F1 U F2 I~A. Then by (RN4) , there are A1, · · ·, AnE F2 such that F1 HA1 1\ · · · 1\ An!-+ A, that is, (A1 1\ · · · 1\ An) ---> AE il!K(Fl). Consequently we have A E 0 K(Fl) + F2. Therefore , 0 K(Fl U F2) ~ 0 K(Fl) + F2.

For (K 0 8), assume that F2 U 0 K(Fl) is consistent, which means that for any A1 , · · ·, AnE F ,·(A1 1\ · · · 1\ An)~ !6JK(Fl) , or F1 ,1~-.(Al 1\ · · · 1\ An)· Now sup­ pose A E ® K(Fl) + F2, then there exist E1,···,EmE F'2 such that (E1 1\ · · · 1\ Em)-> A E 0 K(Fl), or Fd~(E1 1\ ···Em) ---> A. It follows from (RN5) that F1 U F2I~(E1 1\ · · · 1\ Em)-+ A. Since E1, ···, Em E F2 implies F1 UF2 I~E1 1\ ···/\Em, we conclude, by Theorem 2.2(4) , that F1 UF2 I~A, that is, A E 0 K(F1UF2). There­ fore we have proven that 0 K(Fl) + F2 ~ 0 K(Fl U F2) as desired.

The proof of the limit postulate is similar to that of the soundness. D

5 A Paradigm of Default Reasoning

Following the general considerations of the previous sec­ tions, we now look at a specific approach to nonmono­ tonic reasoning . We aim to seek a 'natural' system of nonmonotonic logic which satisfies all the inference rules for the rational nonmonotonic frame. On the basis of Makinson's 'satisfaction table' in [Makinson 1993), only Poole's system without constraints based on finite set of defaults in the systems of nonmonotonic logic consid­ ered in that paper satisfies all the inference rules of RN except the rational monotony. There is a disadvantage of Poole 's approach, however, that it does not allow to represent priorities between defaults , which causes that the inference relations generated by Poole's system hap­ pen to collapse into the classical one when the default set is closed. [Nebel 1992] developed a system of de­ fault logic , called ranked default theory (RDT), which efficiently overcame this shortage. We here reformulate Nebel's system in a more general fashion.

Let (F, D) be a default theory, where F and D are both sets of propositions, interpreted as 'facts' and 'de­ faults', respectively. (F, D) is said to be a perfect­ ordered partitioned default theory (POP DT) w .r .t. ~

if~ = (D, P, <) is a perfect-ordered partition(see sec­ tion 3). The order-type 'f/ of P is called the type of ( F, D) , denoted by 'f/D. The partition P is denoted as {Da:a<ryD}·

A set E of propositions is a syntax-based extension of (F, D) if E = Cn(( U Ra) U F) such that for all a< 'f/D ,

Ra ~ De. and Ra is maximal (with respect to set­ inclusion) among the subsets of De. such that ( U R-y ) U 'Y:Set

F is consistent.

A proposition A is strongly provable in (F, D), denoted by FI"'DA, iff for every extension E of (F, D) , A E E.

It is easy to see that Poole' system without constraints is a limiting case of POP DT when P = {D} and Nebel' RDT is the special case when 'f/D is finite. Unfortunately, as pointed out by [N ebel1992], the inference relation I"' D generated by syntax-based extensions still fails to satisfy the rational monotony. [Zhang 1996] modified the defi­ nition of extensions into the following form:

a set Eisa syntax-independent extension of (F, D) if E = Cn(( U Ra) U F) such that for all a< 'f/D ,

et<IJD Ra ~ Cn( U D-y) and Ra is maximal among the sub­ -y:Sc.

sets of Cn( U D-y) such that ( U R-y) U F is consistent. -y :Sc. -y:Sc.

This approach, though slightly complicated, can yet be regarded as 'natural'. The only difference between two types of extensions is that the former does not sat­ isfies the principle of irrelevance of syntax but the latter does.

On the basis of the notion of syntax-independent ex­ tensions, we have the following result:

Theorem 5.1 Let D be a set of formulas in a language £. For any perfect-ordered partition~ of D, (£,~D) is a finite supracompact rational nonmonotonic frame.

The limited space does not afford a direct proof of the theorem. An indirect one may be done by using the re­ sult in [Zhang 1996] that F i"'DA iff A E Cn(D) 0 F.

6 Discussions and Conclusions

We have established a very close connection between the general patterns ofnonmonotonic reasoning and the mul­ tiple belief revision. This enables us to take the strategy to use methods from belief revision, set-theoretical, to contribute to a better understanding of nonmonotonic reasoning. We have seen that RN is such a strong sys­ tem that almost all the rules suggested for nonmonotonic inference in the literature are the derived rules of RN. One may think that much more consequences would be derived in RN than in the classical logic from the same premises. This is clearly false when none of the pieces of background knowledge is available. Precisely specking, we have Proposition 6.1 Let (.C, f-v) be a rational nonmono­ tonic inference frame. Iff{ = { B <P I~B} = Cn( <f; ), then

Furthermore, even though we equip with the whole background knowledge, the upshot is still less optimistic.

Proposition 6.2 For any propositional language .C ,

there is a rational nonmonotonic frame (.C , f-v) such that for any r ~ .C and any formula A E .C , i) . if K U r is consistent, then fi~A iff K U r 1- A; ii) . if K u r is inconsistent, then ff"vA iff r 1- A . where f{ = {B: <f; f"vB} .

This means that we can not always count on entail­ ing more information from nonmonotonic inference rules alone than from classical ones. For example, even if we are told that <P l~p --+ q and <P f-v·p , we still can not conduct the inference p f"vq . There are two ways to surmount this obstacle. One is to construct some sort of ordering for the background knowledge such as nice-( perfect-)ordered partition, epistemic entrenchment or expectation ordering. The other is to transform the background knowledge into a conditional knowledge base as [Kraus et al. 1990] and [Lehmann and Magidor 1992] have already done. After all , the less we know, the less we can do.