о뷢չ
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
1999 36 5 Vol.36 No.5 1999



߼лһR-ع
տ
ժҪڿ߼УR-عΪһ֪ʶĽΨһʱ̫ȷͱʾ.Ϊˣи˻һR-عĸ.һR-عҪR-عٵö࣬R-ع⣬ûĹһ֪ʶ֪ʶʱڸR-ع̻Ը֪ʶĺά.дӿ߼еģ۸ʵ˻عĶ壬̻عһϵҪʣɿԣԣϵĵԣԼԵ.
ؼʡ߼R-ع
ͼšTP18
R-RECONSTRUCTIONS BASED ON A PRIORITY RELATION
SU Kai-Le
(Science Center,Shantou University,Shantou515063)
AbstractIn open logic the notion of R-reconstruction plays an essential role. However, R-reconstructions can be too numerous to compute and to list out. Based on a priority relation a new notion of R-reconstruction is proposed, which does not have the problem mentioned above. Moreover, the notion is reasonable in characterizing the update of a knowledge base when some priority relation among the pieces of the knowledge base is given. Starting by the model-theoretic notion of rejection by fact in open logic, the definition of R-reconstruction is given based on priority relation. Then proved are a series of important properties about this kind of R-reconstructions, including soundness, existence, monotonicity, and continuity.
Key wordslogic, belief revision, priority relation, R-reconstruction
10˹ܼ.ӳĺѧĽǶȣҪоӦʲôʽɣAlchourronAGMۣ1.˹ܷ棬ĳּС仯ԭ˺ܶ͸µľ巽ģ͵ķ2ݣεķ3.ҹѧδĿ߼4ݣʵģ۵ĸǵ仯ĵԪ֪ʶеĹʽԿ෽Ľ.⣬߼һǿ߼е֪ʶ輯һۣʱTh()٦ȷĿǶ޴µĵ.κ֪ʶϵͳʵ϶֪߼ۣν߼ȫ֪⣩ڵ͸¶˹ӦõıҪԣΪ۷չһƣ5,6.
ǣ˵֪ʶʱ߼ûпǼ˵֪ʶеĹʽ򣬶ʵϣûǶԼ֪ʶȷǱڵȷ.ĸ˻R-عĸؿ̻֮µļ˵֪ʶĸ.ڿ߼УR-عΪ֪ʶĽΨһʱ̫ȷͱʾR-عҪR-عٵö࣬R-ع.ΪҪǱ۵֪ʶϵͨν֪Ӳ(epistemic entrenchment)(μף5,7)ͬĵطǣǰ߽һϵȫû֤߱漰϶߼̺ϵļ⣩.Ĵӿ߼еģ۸ʵ˻عĶ壬̻عһϵҪɿԣԣϵĵԣԼԵ.
1Ԥ֪ʶһЩ
Ǹף8һЩ߼ĻͽȻõһR-عģ۵Ŀ̻.߼оԼһĹԲμף8ף12ݵ.
1.(ʵ, ʵR-ع) Ϊһ˵ݾӼϣ, AΪһ, A. ˵һģMAʵMA. ʱüǺŦM(A)ʾ{Xʦ: MX}. AʵMΪAʵҽM(A)ǼģAʵM ʹæM(A)M(A). κAʵM, ǳƦM(A){A}ΪģAʵMģR-ع. 
1.8 AҴAʵ. ôһQǦAʵҽ Q={A}, Ц멵AݵĦļӼ.
2.(ϼޣ¼ޣ) һ˵{n}nʦǳƼϣֱΪе¼.е¼ȣ˵ҳƸе()ΪļޣΪlim{n}nʦ.
ǹ̶һ˵;A覣A,ҴAʵ. ĦϵϵRǽRR-عĸ. ʵ֮һϵR.
3. AʵMM, ˵MRMҽXʦ MXҷMXôYʦʹYRX, MYҷMY.
1. ڡRʵ:
(1) RһдԺͷԵĹϵ.
(2) AʵMM, MRMҽԼ(M(A)-M(A))(M(A)-M(A))емСԪڹϵRZZ(M(A)-M(A)).
֤. ʵ1СRķֱɶõ.Ϊ֤ԣAʵM1M2M3M1RM2M2RM3. Ҫ֤M1RM3.XʦʹM3XҷM1X, ǽ֤YʦʹYRX,M1YҷM3Y. 
M2XM2X.M2XôM1XM1RM2ڹʽYʦʹYRX,M1YҷM2Y. Y1ΪСģRĹʽ, ʱM3Y1Ҫ֤.M3Y1.M2RM3Y2ʦʹY2RY1,M2Y1ҷM3Y1.ʱRĴԵõ Y2RX. M1Y2Ҫ֤. 򣬼M1Y2.M1RM2Y3ʦʹY3RY2,M1Y3ҷM2Y3. RĴԵõ Y3RXY1ļСì.
ڷM2X֤M2RM3 .
֤ʵ2.MRMZǼ(M(A)-M(A))(M(A)-M(A))еģڹϵRģСԪҪ֤Z(M(A)-M(A)). ȻZ(M(A)-M(A)). ɶ13ôYʦʹYRXY(M(A)-M(A)), ZļСì.һ棬м(M(A)-M(A))(M(A)-M(A))еģڹϵRģСԪZZ(M(A)-M(A))ǽ֤MRM. θXʦMXҷMXX(M(A)-M(A)). ɼXǼ(M(A)-M(A))(M(A)-M(A))еļСԪʴڸüʹYRXYYǼСYɼ輴Y(M(A)-M(A)). ӶYʦ, YRX, MYҷMY. ֤ MRM.
4.RļСԪϵRR-عһAʵMΪϵRļСԪκAʵMʹMRMMRM. κΡRļСԪMǳƦM(A){A}Ϊ(Aʵ)ϵRR-ع. 
2ɿԶ
ǸRR-عڿ߼еR-عһҪʼ2, ǳ֮ΪɿԶ.Ҫ֤»RR-عĴԶ.
2. κΦ(Aʵ)RR-عǦR-ع.
֤. ɶֱƳҲһڵ23ۺ϶.
1. ٶCǹڡRCAʵļҶM1,M2CM1RM2M2RM1.
{Xʦ|(M1C)(M2C)(M2M1M2X)}
ô
(1) 멵A.
(2) MC, Xʦ, MX ҷXʦ, ô X1ʦ ʹ X1ʦ, X1RX,  MX1.
֤. (1) һ߼Ľֻ޶X1,,Xkʦ֤{X1,,Xk}{A}. ɦĶÿһXiһ Mi1Cʹö M2CM2RMi1 ̺M2Xi. ΪCһ, Mm1{M11,,Mk1}йڡRСԪ. i(0<ik)УMm1Xi. {X1,,Xk}{A} .
(2)  MC, Xʦ ʹ MX ҷ Xʦ. κ X1ʦ  X1RXMX1ôX1. ǽCеʵ {Mn}ͦеľ{Yn} ʹöÿһn: 
 Mn+1RMn;
 MnYn,Mn+1Yn;
 Yn+1{Xʦ|XRYn,Mn+1X,MnX}йRļСԪ.
{Yn}γ˽Rϵì. 
 M0=M, Y0=X. ΪY0ʦ, M1CʹM1RM0 M1Y0(Ķ). Ӷ Xʦʹ XRY0, M1X, M0X( M1RM0 M0Y0), Y1ǼСRX. 
ٶ̶kѾõ {Mn}nk+1{Yn}nk+1 nk,,۱. Ǹ Mk+2, Yk+2ʹâ,,۶nk+1.
֤M0Yk+1.  MkYk+1, ֻ֤0<ik MiYk+1̺Mi-1Yk+1. ĳi0<ik) MiYk+1  Mi-1Yk+1.  MiRMi-1 Mi-1Yk+1Xʦ ʹ XRYk+1, MiX,  Mi-1X.  Yk+1RYi, YiRYi-1,  XRYi XRYi-1. YiǼ{Xʦ|XRYi-1, MiX, Mi-1X}йRļСԪì. M0Yk+1. Yk+1RY0ǾݷYk+1. ӶMk+2CʹMk+2RMk+1 Mk+2Yk+1. YʦʹYRYk+1, Mk+2Y, Mk+1Y. Yk+2ΪС(R)Y. ͸ Mk+2, Yk+2Ҷ nk+1 ,,۳.
3. ڦ(Aʵ)ϵRR-ع.
֤. ֻ֤ϵRļСԪ.ΪCΪϵRθڡR, ͬ.ǰ֣һ{A}ģM. һ֪еMC MRM. ϵRļСԪĴԼZornõ. 
3Լεķ
˵֪ʶ⦣ϵϵRӳûԦеļγ̶ȵıȽϣڸĽ˵ֱȽԽȫϸûõĻڸñȽϹϵR-عԽ.ر𣬵ֱȽϴﵽȫʱӦRΪһȫϵûõΨһһR-عûԦеȽʱӦRΪռûõȫR-ع.
2.ԣ RͬRΪϵϵRR, ôκΦĻRR-عȻǦĻRR-ع.
֤. һϵR-عĶ壬֤RRɣɶ3õ.
3. RΪռϣôκR-عΪRR-ع. 
֤. ֤κʵM, MMRMҽM(A)M(A).ʵϣݶ3MRMҽ XʦMXҷMXôYʦʹYRX,MYҷMY. RΪռYRXǲMRMҽXʦMXMXҽXʦMXMXM(A)M(A).
4. RΪȫϵʱĻϵR-عΨһ.
֤. ж3.Ϊ֤ΨһԣM,MΪAС(ڡR)ʵҪ֤M(A)=M(A). 򼯺(M(A)-M(A))(M(A)-M(A))ǿգRΪȫϵʵϣRΪϵΪRԣüдΨһһСԪZ. Z(M(A)-M(A))ʱMRMMRMӶMǼСԪìܣZ(M(A)-M(A))ʱMRMMRMӶMǼСԪì.
4һķ
ǿǻϵRR-عһƽʾ.κξӦg()ʾӦĸ¶. ʾɸ¶СȷľӼĶԪϵ={<,>|,Ǿg()<g()}.κμ˵Aæ*AʾAʵĻϵڦеƣR-عCAʱ*AΪ {A}.
4. κΦӼ,{CA}=*AȼڶоӦУʦҽ{A}{¡ʦ|g()<g()}.
֤. Ǽ覣CAԳ. Ϊ÷űʾϵ.ɦ*A壬*A=M(A){A}, MΪAĻڵһʵ.ڦAݣЩAӶ{A}=*Aȼڦ=M(A).ھӡʦҽ{A}{¡ʦ|g()<g()}ݡʵǼϦĹɶ壬ɼйعɶĶĦΨһ.ֻҪ֤M(A).覣M(A)*ΪСʹáʦM(A)ҽ{A}{¡ʦM(A)|g()<g()Ҧ¡ʦ}ݡľ.ΪM(A){A}ݣʦ*{A}{¡ʦM(A)|g()<g(*)}, M(A).M*Ϊ{A*}{¡ʦM(A)|g()<g(*)Ҧ¡ʦ}һģ.ô(M(A)-M(A))(M(A)-M(A))еģڹϵģСԪǦ**(M(A)-M(A)). 1֪M*MMM*Mǻڵʵì.
϶Ľ*AɼĶ.һ.
5. {n}nʦһļ˵УAķӣô
(lim{n}nʦ)*A=lim{n*A}nʦ
֤. ǹ֤κΦ¶ԣrʹæ(lim{n}nʦ)*A iff ʦn*Aκn>r.θӦκΦ¦϶ԳҪ֤ԾӦ϶Ҳ.
¦Ħֻ޸Ϊ0,,k. ÿi(ik)riʹæi(lim{n}nʦ)*A iff iʦn*Aκn>ri.r*Ϊri.У
{|¦,¡(lim{n}nʦ)*A}={|¦,¡ʦn*A}κn>r*.
Ӷκn>r* (lim{n}nʦ)*A iff {A}{|¦,¡(lim{n}nʦ)*A}ݣݶ4 iff {,A}{|¦,¡ʦn*A} iff ʦn*A (ݶ4.
ָ
1¶ӳʽʽϵĸԳ̶.Ϊ֪ʶ򣬷ӳȥԣ¶벢ȫӳ֪ʶĿŶȣø¶Ϊϵ.ʵϣϵֻûԼľ鲻ϵõ.ǣڵĽƹ㵽һ෶ΧϹĿϵȥ.κιʽ̣ΪһʵʾĿŶȣԽţ̣ԽС. ={,¡|,ǾҦ()<()}.κμ˵Aæ*AʾAʵĻϵ̡ڦеƣR-عAʱ*AΪ{A}.ôڶȫ㹫ʽԦϵʱ45ֱ*Ϊ*̣gΪ̣.
2Ӷ4ĵݹʽǿԵõRعһ㷨ȫһԷΧ֮ڣ㷨пɲģΪҪжһʽϿɷ.Ȼ֪ʶά˼޸ӵϸпɲ㷨ҵҲӦʹһЩʽģ˻ʽ㷨. 
Ĵӿ߼еģ۸ʵ˻R-عĸ.֮һµR-عR-عûĹ֪ʶ֪ʶʱ̻Ը֪ʶĺάͬʱӳûֿϵһ棬һµR-عʱ̫ȷͱʾR-عҪR-عٵö࣬R-ع.ϵͳظ˻R-عһЩҪʣɿԡԡԡԵ.ĽһĹЩʣǡR-عĽ.
õҡ߼ƻȻѧ(Ŀ 19601013)͹㶫ʡȻѧ(Ŀ 970376).
߼飺տ֣У19649ʿڣҪоΪѧ˹е߼㷨.
ߵλͷѧѧԺͷ515063
ο
1Alchourron C, Gadenfors P, Makison D. On the logic of theory change: Partial meet function for contraction and revision. Journal of Symbolic Logic,1985,50(2):510530
2Winslett M. Updating Logical Databases. Cambridge:Cambridge University Press, 1990
3Ginsberg M L. Counterfactual. Artificial Intelligence,1986,30(1):3579
4Li Wei. An introduction to open logic system. In: Proc of Int Conf for Young Computer Scientists.Beijing,1991.2128
5Williams M. Transmutations of knowledge system. In: Proc of KR-94. San Francisco:Morgan Kaufmann,1994.619629
6Lemann D. Belief revision, revised. In: Proc IJCAI-95. Montreal, 1995.15341540
7Bai S. Reasoning by Argueing: A game-theoretic approach.In: Proc of IFIP '92 Workshop on Automated Reasoning.New York: Elsevier Science Publisher B V,1992
8Li Wei. An open logic system. Science in China(Series A), 1993,(3):362375
9տ. ߼еR-ع. ѧͨ, 1994, 39(5):385387
(Su Kaile.R-reconstruction in open logic. Chinese Science Bulletin(in Chinese), 1994,39(5):385387)
10Li Wei. A logic framework for knowledge base maintenance. Journal of Computer Science and Technology, 1995,10(3):193201
11տ֣³ɣΰ. ߼еĺʵģ. ѧ 1994,17(5):361366
(Su Kaile,Ding Decheng,Sun Zhiwei et al.Classes of models for a rejection by reasonable facts.Chinese Journal of Computers(in Chinese),1994,17(5):361366)
12Su K, Ding D. On Etherington's procedures for generating extensions. Science in China(Series A), 1995,38(Supp):8190
ԭյڣ1997-07-30
޸ĸյڣ1998-05-22
