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



ȶ
¡١Ｊ
ժҪȶͱ߼ѧоͻͳһۣͳһһЩҪ.ΪŲֱͬ͸ǵ໥ϵ.ĸ֤ˣ߼䷨¶ǵȼ۵ģͬͳһ.,Ϊǰ;ıָһֵķ.
ؼʡ߼,ȶ,ϵͳ,,˵,֤
ͼšTP301
PROPER STABLE CLASS AND ARGUMENTATION SEMANTICS
CHEN Rong and SUN JiGui
(Department of Computer Science, Jilin University, Changchun 130023)
AbstractStable class and argumentation semantics are two outstanding unifying frameworks in the research of declarative semantics for logic programs, and they unify some very important semantics. Because they have different intuition and concepts, their relation is not clear yet. It is shown that their fundamental concepts are equivalent under normal logic programs, so they have the same unifying capability. Based on such a result, a constructive procedure is presented for computing the promising argumentation semantics.
Key wordslogic programming, stable class, argumentation system, abductive reasoning, declarative semantics, proof procedure
1
߼ϵͳУ޷֤һԭӣʧܼ(NAF)ϵͳԸԭΪٵж.NAFһҪȱʡģʽһǲҪʽ洢ĳԭΪٵϢӶݿĿռͬʱ˱㸴Լһƽ.ΪҪǣ߼һͻصǿͨNAFȻַ֧ǵ(abductive reasoning).
ǣ߼NAFݵѭʱֱTpǵģ1.ʹѰʵĳ˵塪׼ȷӳڳʶµֱۺüʮҪַǳ.еоǶNAFʶ.NAFĺкǿĹԣ԰硰pֿȱʡ֡(abducible).ֱڳоFittingģ͡ģ͡ȶģͺģͼȣ1.ڴԣȻֱۺǺϵģܿԹĳʹǲץסֱۺ1.ңͬķڲֱͬǰᣬʹ˲ͬ͸.ǵص໥ϵʱԻ.ˣоǵͳһ۱ΪҪϸַƣشٽĽ.
ȶ2ݺͱ3ͳһеٮٮߣнṹ򵥡ȫ͹㷺֮ص㣬ȻŲֱͬ͸.ȶĻ˼ǣGelfondLifschitz任ѳP任PIõFP2ȶ࣬ȶ.Ļǳϵͳ4,5ݣDungǰѳPΪһۿAP,H,HPĻֵȫ壬HһӼʾܵ򣨳Ϊ˵Ǽ˵Ĺϵ.ĳȶԵļ˵ǿɽܵģɽܼ˵ڼϰϵ¹һȫǵġνṹǳ.ֵעǣͳһиԵơȶĶʹòۣмϵƣ䣬֧.رǣȫķǵʽͳһڱϵͳ£5ݣӦ漰ϡ򡢹滮жۺݿ.
DungķҪĸǹϵͿɽ.Ϊ˵ռӴģж˵ǷɽʱҪü˵ݣ迼йļ˵԰ֱӹѵ.յУûͳһܵĽо˵ǰ.Ȼȶֻڲֱͬķͼ֤ڱͨ.״֤ǵǵȼ۵ģ㷨ġԵϡĵ.ʵַƻ໥øеĽ.
2﷨Լ
һ߼ľ䷨ƣԶ߼ĳԪʡνʡԭӡHerbrandHerbrandֵȵ.
ӾʽĹ

ԭ.ȱʡ.
޸Ӿļ.رǣm=0(1)ΪӾ䣻Ӿ伯Ϲ.
Pû滻еÿõпܵ򹹳P*.Herbrand۳˵壬ʧһԣٶ۵ĳ.ּٶһܰӾ.ôϲʧʲô1.
SһּΪд㣬Լ.TarskiṹHerbrand͢HerbrandһӼ϶ڢĻԭΪ.ᴩȫģСдĸa,b,cȱʾνʣPʾһ߼HBPHerbrandI,JPHerbrandͣHHBPһ˵hʡHBPһ.
Pһ˵Hݹ鶨ݹϵ
(1) PHa ҽʵӾaP.
(2) PHa ڳӾ(1)P.
֤Ҳ.֮ڼ˵ǵ.
PPСģ֧ͣӵСTPؿ̻.ȻһTPĺ壬ԭaΪͷӾĹI³ʱaڼTP(I).
3ȶ
Baralsubrahmanianף2жȶֻۣ߼µȶ.ĳI£Gelfond-Lifschitz任ǰѳPPIķ׼ȷ˵Ӿ, bnҽab1,, bn,c1, , cmP{c1, , cm}I={}
1. FPGL-ӣ.
֤FPģӦFPΣǵģС󲻶㶼ڣ2.
2. I,JPHerbrandͣRHerbrandͼĶԪϵR(I,J)ҽJ=FP(I).
32. S={Ii}ǳPһ޵HerbrandͼϣSPһȶ൱ҽS={FP(Ii)}.
42. SǳPһϸȶ൱ҽSķǿӼҲPһȶ.
5. S1S2Pȶ࣬S1S2ҽJS1IS2IJ.
ֱϣȶ෴ӳһGL-FPûв㣨㼯Χһ޵㼯һͣѭȷף2ʹϸȶ.ȶʣ2ݣ
(1) ȶģһԪصȶࣻ
(2) ģͶӦһܼСȶࣻ
(3) ȶĲҲһȶ.
ȻȶĲ̫Ľͣûʲô.Ƿ֣ʹһϸȶ࣬ҲܰһܴĻ֤{{a}, {a,b}, {b}, {b,c}, {c}, {c,a}}һϸȶ࣬Ϣʵ̫.бף2ݵĹΪӦʹ¶ȶ.
6. SǳPȶ൱ҽSǶԪϵRһԳƷձհ.
ȻȶеԪII=FP2(I).
7. PͼG=(V,E)һͼе㼯V=2HBEΪ߼ϣPHerbrandIJR(I,J)IJ.
1. P={1. pq 2. qp 3. rr 4. rq}.ͼΪ


ȻP3ȶ{{},{p,q,r}}{{p},{p,r}}{{q,r}}.ȶӦͼеһС2Ļ·.
ʹFP2ضģͣģʹΨһ1,2ݣǲѵõµĶ.
1. ÿһǿյȶ. 
4
Dungı3,4ĸǼ˵ĹϵͿɽܼ˵о.
83,4. H1H2P˵H1H2ΪHH2ڼ.
93,4. ĳhڼ˵Hǿɽܵģ˵H1ֻҪHH2.
104. Ƽ˵HûгͻڣABBA.
114. һ˵Hǿɽܼ˵ΪAHõ㣺 Hûгͻ ÿhHHɽ.
ɶ֪ûгͻļ˵ٲӦԼԼɽܼ˵ӦԹκιߵļ˵ǵֱ.ע⵽(HB,)һ걸ĶУذѼϰϵΪ˵ϵ.
123. ˵Hż˵ΪPHҽHǼɽܵ.
1. ˵HгͻҽPH.
֤. ()PHݣHHHгͻ.
ҪԣHгͻڣABBA.ʧһԣٶAB.Ǵ .Ϊݹϵڼ˵HǵģҲ..PH.
֤.
13. APǶڼ˵ռϵӳ䣬hHɽ}.
ȻAP(H)ȫڼ˵HĿɽܼ裬11еȼ.Ȼ.
2. APǵ.
14. Hȫ˵ΪCHҽ(1) PHݣ(2) H=AP(H).
15. Hǻ˵ΪGHҽHǼСȫ˵.
16. Hȶ˵ΪSHҽ(1)PHݵģ(2).
ȫ˵ͻ˵ǽ(skeptical)Ļ˵ӦųPģͣż˵ȶ˵ṩ˴(credulous reasoning)ģʽȶ˵ȶģӦ.һɽܼ˵HPHڬµȫݽһHerbrandģ(ǲֵģ˿ɽܼ˵루֣Herbrandģһµģ˵ż˵Ҳضģ͵ĸ.2˸ֿɽܼ˵Ĺϵ.
2. 1еĳP.8˵H0={}, H1={p}, H2={q}, H3={r}, H4={p,q}, H5={p,r}, H6={r,q}, H7={p,q,r}.ȻH0ȫ˵֤H1H2Ҳȫ˵H0ǻ˵H1ȶ˵,H2ż˵.ע⣬H3ǿɽܼ˵ΪH2H3H3H2.
2. ̺ʽ. 

֤. ݶ壬̺ʽ(1)(2)(3)(4)Ȼ.ֻ(5)(6)֤.
(5) ˵HΪSH֤HҲCH.HΪSHPH.ɶ16(2)֪ǿռ˵H1.ǵ1HCH.
(6) Ȼ(2)(5)ֻ֤SH㹻.÷֤.HH1H1ɽ.H1/Hǿգ.H1ɽܣH1HǵHH1H1гͻH1ǿɽܵģì.HǼ.
֤.
ݶ2PHSHGHCHγɳPΨһһȫ˵ĵȼ࣬ǳı.ȼеԪڼϰϵ¹һǡİ񣬶ռ˵Ȼƽļ˵õȼǿգȫ.ڣΪ׼ȷֱۺṩ˶ֿܵѡ.
Ȼ2APǵ.Dungָۿ޵ģAPһ˵APпǲĢ.ͨΪ˵ռӴģPܻ˵ĳ˵ܵĹҲεģжһ˵ǷɽʱҪԣҪЩгͻĹ˵ȻPǲݵģ԰APֱӹǺܸӵ.ȶǡⷽ.
5ȶ=
17. HPP˵IHȡH=HBHerbrandIHH.
17м˵H以HerbrandIH֮IHIҲĻϵ.ʱ׿FP(I)=ǳ.ȻAPǱȽϸӵģڳľ䷨£GL-FP2еĹϵ.
3. PHP˵.
֤. ֤(1).
hAP(H)(עʱh).ȿ˵H1P(H1h൱PûԡhΪͷĳӾ䣩P(HB/FP(IH))hҲhʡHB/FP2(IH)).һ£κμ˵H1ֻҪH1{h}HH1.ڿǼ˵(HB/FP(IH))HĹϵ
1衫(HB/FP(IH))ṥ{h}Pȡ(HB/FP(IH))hǲ.˳ǣԣô.hԣ(1)ʽ.
2ʧһԣ.ǣȻ⵼ì.
֤(2).hǡ(HB/FP2(IH))е裬ǡhFP2(IH).PûԡhΪͷĹô˵hܵhAP(H).H1ǿռ˵ǡhFP(IH).H1ǡ(HB/FP(IH))Ӽ.裬ǣFPķԣhFP(IH1)ʡhFP2(IH)ì.H-1=H1/((HB/FP(IH)))ǿ.ע⵽.H1ǿգٴһ裬ǡh1FP(IH)h1H1.H1{h}HH1.H1ԣhHɽܣhAP(H).hԣ(2)ʽ.
֤.
4. PһȶΪ{I,J}. (1) PHJݵ. (2) PHIǲݵ.
֤. (÷֤)
(1) ֪PHJǲݵ.ǣҽԭb㣬bHJ.׿.FP(I)=Jǵ.ǣì.˲ĻԭbҲ֤PHJݵ.
(2) ֪PHIݵ.ǣҽԭbͬʱ͡bHI.ǵͣһԭcJ/I.һһ.ȻIȡHI=HBcHI.˴ͬʱPHIc͡cHIԭcì.PHIǲݵ.
֤.
3ʹFP2ļ˵HIʽ(*)HI = AP(HI)֮(*)ʽFP2(I)=I.4һ֤Щʽ(*)ļ˵HIڳPǲݵģܳΪȫ˵ÿȶжΨһһȫ˵.ȷ3Ͷ4һǶȸжȫ˵ĺо.ȶͱ壬3Ͷ4ڸĸǵȼ۵ģͳһͬµĵȼ.ΪҵһֺĹ췽.
5. (1) Ԫصȶȶ˵֮Ȼ.
(2) _Сȶ˵֮Ȼ.
(3) _ȶż˵֮Ȼ
6㷨
Ϥ۵Ķ߶֪㶨ӦһԵϡĵ.FP2Сģͣ7ӷǿռʼԹ⣨ȶģͺģͣ.˵7Ѹ˱Ĺ㷨.
ٶֻĳP.HBԪظΪnPnԭӣʧһԣԭӿȻ1,,n.{i1,i2,,in}ǳPһHerbrandͣʧһԣټٶ.ȻPֻ2nͬHerbrand.ǿԸÿΨһһj֮һj (1j2n)ҲȷHerbrand.ʽ(2)׼ȷֹϵ.ǵ㷨ʹ(2)ʽ.{i1,,ij}ıΪ

㷨. ĵ㷨

㷨SĿޣѭĿϼ٣㷨һֹ.6жǷΪȶģͣ10жǷΪģͻģ.֤㷨ȷ.
ʹüϱŵ󣬼ȡڵȲ.磬֪ǪiS(i-b)=0 ҽbS.
7
ı嶨3Ҫȫ˵˵ȶ˵ż˵ӳ˳ʶнĺʹ󵨵ģʽ.岻ṹ򵥣ϵǵֱۣ߱ԣҵ֤ϵͳǷǵ߼һҪͳһۣ5.ȶҲˣеĽǵ߼2.ΪҵһڹĿɽ.
Ȼڹ߼ľ䷨£ȶͱ嶼ƹ.ΪֵоУ1Ѷƹ㵽չ࣬ڹȥ۶ߵĵȼ۹ϵǷԱȥ.2ǰѱĵĽӦõݿ⡢ϡ滮ͷȥ.
л رлߵĶ෽潨ָ.ִѧѧϵԶҵȫԱμ˱ĵۣڴ˱ʾл.
ĿõȻѧ(Ŀ69783009)
߼飺٣У1969ʿоҪ߼ǵо.ＪУʿڣҪ¶֤Զ߼Լȵо
ߵλ¡١Ｊ󡡼ִѧѧϵ130023)
ο
1Apt K R, Bol R. Logic programming and negation: A survey. J Logic Programming, 1994, 19/20(1): 971
2Baral C R, Subrahmanian V S. Stable and extension class theory for logic programs and default logics. J Automated Reasoning, 1992, 8(3): 345366
3Dung P M. An argumentation-theoretic foundation for logic programming, J Logic Programming, 1995, 22(2): 51177
4Dung P M. On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and N-person games. Artificial Intelligence, 1995, 77(3): 321357
5Bondarenko A, Dung P M, Kowalski R A et al. An abstract, argumentation-theoretic approach to default reasoning. Artificial Intelligence, 1997, 93(1): 63101
6Dung P M. An argumentation semantics for logic programming with explicit negation. In: Warren D S, Szeredi P eds. Proceedings of the 10th International Conference on Logic Programming. MA: MIT Press, 1993. 616630
յڣ1998-04-28
޸ڣ1998-12-14
