ѧ
JOURNAL OF SOFTWARE
1999 4 10 Vol.10 No.4 1999



òӾ߼ݵPetriģ
֡⽨ƽ
ժҪоӾ߼ݵPetriģͱʾͲⷽ.ֵ߼ͳͻǨĸ,HornӾPetriģͷHornӾPetriģ.߼ݵĻ֮һѰ߼ֵĲ.ʾһֻPetriģ͵Ӿ߼㷨,㷨ΪЧ.
ؼʡ߼,Ӿ,Petri,,ֵ߼.
ͼšTP301
Logical Inference of Clauses in Petri Net Models Using Fixpoint
LIN Chuang1 WU Jian-ping2
1 (Information Science InstituteState Information Center Beijing 100045)
2(Department of Computer Science and Technology Tsinghua University Beijing 100084)
Abstract The Petri net models of the clauses for logical inference using fixpoint are studied and the four-valued logic and the conflict transition concept are introduced. The authors can construct the Petri net models of non-Horn clauses based on the models of Horn clauses. Finding the fixpoint of logical values is one of the fundamental methods for logical inference. In this paper, an algorithm for the fixpoint based on the Petri net models of values is presented, and it is more efficient than the previous ones.
Key wordsLogical inference, clauses, Petri net, fixpoint, four-valued logic.
߼˹ܵĻ֮һ,ݹ̾ȷһǷռһʵӾ̺.о,жģͷʾ֪ʶ.Petri֮Աѡģ߼,ΪPetriкܺõģ̬Ͷ̬ԡкͳͻ,ҲΪPetriкܺõѧ,Ը㷨.߼תPetriģ,Petriеķȥ߼,ǿòͬЧķĻ.
PetriѱHornӾ߼ݣ1,2ԼһӾĲһԵļ3.Murataˣ4Ѿ˴һHornӾתһPetriģ͵㷨,ҽһHornӾ䲻һµıҪͳ.ǸHornӾ߼Petriģ͵Ĳ㷨1.
ף5,PetriڷHornӾ߼ģ,ûṩЧ㷨,ԸıʾҲȷ.ڱ,ҪHornӾPetriģ͵ıʾ,ʹ֮ӦHornӾģ͵ıʾ.ǵķǵ߼ģ͵Ĺ6,ֵ߼,Ƿ4ֲͬɫԱĲֵͬ.ͻǨĸ,ԽȡӾ(ʽ)ģͱʾ.ĸ߼ݵоҪ,߼ݵĹ̿Կǲγɹ.߼۵ıʾ巽.Petri߼ģ,ĳʶʾ,ⲻͱʶֵ.
1:Ӿֵ
һڽPetriӾֵ߼ظ.
1.1Petri
ǽʽPetriһصĸ,йPetriĶɲμף7.
PetriλúͱǨ㹹.֮,Ȩ߼ģΪ1,λеķֲγɱʶ.һǨλжٱһǵ,ʵʩ.Ǩʵʩ,ʹλжһ,ʹλжһ.
Ǩʵʩ±ʶı仯,һʶﵽһ̱ʶ.ʶֱ仯ҲĹC.CֿɷֱIOʾ.Ԫÿλù,ԪÿǨ.ھI,λPjǨTiл,IijԪΪ,Ϊ.ھO,ǨTiλPjл,OijԪΪ,Ϊ.C=O-I.CtǨtص,һǨtڱʶMʵʩﵽ̱ʶMɱΪM=M+Ct,M=M+Ot-It.Petriͼαʾ,߶αʾǨ,Բʾλ,λеĺڵʾǣtoken).
1.2ӡ
һ߼о,һӾ䶨(wff)ʽ:
B1,...,BqA1,...,Ap, A1...ApB1...Bq,
AiBiԭӹʽ,ʾ̺,p0,q0.Ӿζ,A1...Ap,ô,B1...BpΪ.
һHornӾҪ:q=1q=0Ai(1ip)B1УǷǸʽ.һӾû.
߼ݾȷһĹʽǷһӾ̺.߼ݵ֤һַ:
(1) ƲһӾ伯LǷ̺QͼL Qһ,һ,֤L̺Q;,LͲ̺QַӦϸ.
(2) ʹ庯,߼ݿӳʼʽֵ״̬,ͨӾ򲻶ϸֵĹ,༴,֪ʶӵĹ,ﵽһֵ,а̺Ϣ.
1.3ֵ߼
ǲSandewellֵ߼ļǺź8.ٶһ4ֵļJ={u,t,f,k},Ҿƫϵ,ͼ1ʾ.

ͼ1 ֵֵɵĸ
ǿ:һԼL,Ԫǹʽ;һֵJ.ֵV:LJһӵĺ,Ҳƫϵ,:

һֵԱʾΪ֪ʶһ״̬,״̬,(t)(f)֪(u)ì(k).״ֵ̬֮ƫϵ״̬֮ϢĶ.VVͱʾ x)V(x)=uңV(x)=t)(V(x)=f)(x)V(x)V(x),༴,һЩ֪Ϊ֪(tf).
߼ݹ,֪ʶ״̬ĺϲӦ4ֵСϽ.СϽζ:һⱻĳֵΪu,ֵΪt(f).ô,ͱֵΪt(f),༴,ĿȡֱϽֵ.ڱĲһӾìܵ,Petri߼ģнǱǵ{u,t,f}3ֵӳ.
2ӾPetriģ
ף2,4ѾνһHornӾתPetriģ͵㷨.ף3,5Ҳ˻ֵ߼Petriģ.ڸһӾתPetriģ͵Ĺ.
ӾıʽΪ
A1...ApB1...Bq.(1)

ʽ1󲿳Ϊǰ,ҲΪ.p=0ʱ,ҲΪʵ;q=0ʱ,󲿱Ϊ֤̺Ĺʽ.
ǷӾPetriת.
(1) q1ʱ,ʹйӾPetriģ͵ת:
.һǨʾһӾ;ʵʾΪԴǨûλõıǨ;
.һͬʹһͬλʾ;
.ǰʾΪǨλ,ʾΪǨλ;
.λĻ,עΪt;븺λĻ,עΪf.
1:һӾL:

ǿɵLPetriģͺ,ͼ2ʾ.

ͼ2 1ӾӦPetriģͺ
ӾӦPetriģ,仡tfԱʾӦɫǵ,űֵɫ.λûñʱ,ͼٶλðɫΪuı.ǨʵʩҪλð뻡Ӧֵı,ǨʵʩӦֵı.ڼٶìܵ,ʵʩͬλеԭб޹.
(2) q1ʱ,Ӿжȡʱ,ÿȡ3﷽ʽ.һӼ˵,һӾ:
ABCD.
ܰ3ֱ:
(a) ABD/Cͬ;
(b) ABDC룩;
(c) ABD or C.
ǰֱʽ,ǵϵͳеÿһӾԿӾ,ֱABCABD,ǿǰķתPetriģ.ںһ,CDͬʱ,Ǵڳͻ,һжλúͻǨʾӾ,ͼ3ʾ.

ͼ3 һӾPetriģ
ͼ3,λXΪ߼жλ,ǨΪ߼ͻǨ,t2t3Զ߼ͻ,༴,һһǨѡʵʩ,߼ͻеǨٱʵʩ.ֶ߼ͻǨһPetriͻǨĶ岻ͬ.һPetriģ,ͻǴ,ͻǨԶͻ.Ϊ˱ʾֳͻ,ģа໥߼ͻǨʱ,ǿɽֽɶ໥߼ͻǨģ,Ҳ,ÿģеÿһͻǨнѡһǨ,ɾǨԼӻ.ÿģ͵߼ݽΪϵ.
,q1ʱ,ֻҪӾÿȡ֮Ĺϵȷ,ǾͿͨӾķ߼жλü߼ͻǨӾPetriģ͵ת.
2:һӾL:

ת,Ӿ伯LдӾ伯L:

X߼ж.
LӦPetriģͿɷֽɲ໥ͻǨPetriģ,ͼ4ʾ.

ͼ42Ӿ伯Petriģ
3Ӿģ߼ݵĲ
ӾPetriģ,Ϣ״̬Ӧһʶ,һθֵԺͱǨһʵʩӦ,һݹϵӦʶ֮һֿɴϵ.߼,ĸֵֻ;Petri,λõıǼȿֿɼ,,ǵӾPetriģ,ʶ֮ĿɴϵΪ
MtiMM=Max(M,Oti).(2)

ʵ,ʽ2ֱӿɴϵһPetriеֱӿɴϵ.ΪӾPetriģͳʼʶΪ0,ʵǨɵ.һλеıǵöʧ,ʵǨԼǨʵʩʧȥ.ӿɴѹΪֱӿɴ,Լ򻯱ʶļ.
ӾPetriģ͵Ŀɴ㷨,༴,߼ݲļ㷽.
1 ģв໥߼ͻǨʱ,㷨.
㷨1.
:һû໥߼ͻǨӾPetriģ.
:ģͿɴʶĲ.
Begin
ʼNewnodeΪ0{ÿΪu};
Repeat
Currentnode:=Newnode;
ForÿһCurrentnodeʵʩti;
Begin
ʵʩtiҲֱӺ̱ʶMi;
Newnode:=Max(Newnode,Mi);
End;
Until(Currentnode=Newnode);
return(Currentnode);
End.
Ǿһʾ㷨.
3:ͼ2еPetriģ,ɴʶĲ:

ɴʶΪģͱʶĲ.
1. 㷨1õģɴʶ,ΪģͶӦӾ伯L߼ݵĲ.
֤:ΪMtiMM=Max(M,Oti),ΪMtiMMtjMNewnode=Max(M,M),,MNewnodeĿɴϵ߼ݹϵ.
M0=0ʵǨԴǨ,ʵ״̬ɴ.
㷨1,NewnodeֵпܷǨʵʩ²,Currentnode=Newnode,༴,CurrentnodeΪ߼ݵĲ.
ֶ㷨1ĸԽз.ٶPetriģnǨmλ,ô,ÿһʶСϽļΪm,ÿʶnǨʵʩ.ɴＯnʶ,,㷨1ļ㸴ΪO(n2*m).
Ϊ˽һ㷨Ч,ǿԸĽ㷨1.Ӿ伯ϱìʱ,һֵͲٸı.仰˵,ǵӾPetriģ͵,һǨһʵʩ͹̶λֵ,Ժвٸı.,ڹ̶,ÿһǨʵʩ,ͿɴӱǨTɾ.
㷨2.
:һû໥߼ͻìܵӾPetriģ.
:ģͿɴʶĲ.
Begin
ʼNewnodeΪ0{ÿΪu};
Repeat
Currentnode:=Newnode;
ForÿһCurrentnodeʵʩtiT;
Begin
ʵʩtiҲֱӺ̱ʶMi;
T:=T-ti;
Netwnode:=Max(Newmode,Mi);
End;
Until(Currentnode=Newnode);
Return(Currentnode);
End.
㷨2ĸԿɽΪO(n*m),Onaga˵ӱʶɴ㷨㷨ΪO(m*2n)O(m2*n))9,õϢ,㷨Ϊ.
3ļ̿ɼΪ:

2 ģа໥߼ͻǨʱ,ǿɽģͷֽɶ໥߼ͻǨģ,Ȼʹ㷨1㷨2ģͱʶĲ.
4:ͼ4ֽPetriģ,ǵĲ:

ⲻĹ,ǲõǰ㷨,ӳʼʶM0=0,ƳʶĲ.ҲԵߵPetriģлķ,֤Ŀλñֵ,Ȼͬ㷨ģ͵Ĳ.õĲйʵĸֵ֪ʵֵƫϵСڵֵ֪ʱ,Ŀ֤,,Ŀ겻.
5:ͼ2ӾPetriģ͵ģͼ̿ͼ5ʾ.

ͼ5
õĲеAB⸳ֵ֪ʵֵͬ,˽D֤.
һ,ݱǰݸЧ.ϵͳȽϾ޴͸ʱ,༴ʵȽ϶ʱ,ֲ͸.ԭ,ǰ,ǰǲ֪Щʵ͹й,ֻܴӴΧʵ,Ʊ;,ԴصĿ,޹صݹʵ,ԼٲҪļ.仰˵,ǰäĿԴ,Ŀǿ.
4 
չʾӾPetriģͱʾ߼ݲִз:ǰݺԼǵ㷨.ף1HornӾPetriģ߼ݹļ,Ҫ:1 ṩӾPetriģ߼ݵĲ㷽;2 ṩ˲Ч㷨;3 ǰݺݵģͱʾݷ.ĵоɹһν߼Ҳõ,ƪ,ﲻټ.
*оõȻѧ.
ͨѶϵ:ִ, 100045,·58ŹϢľ뼼о
߼顡ִ,1948,ʿ,оԱ,ҪоΪϵͳ,Petri,,߼.
⽨ƽ,1953,ʿ,,ʿʦ,ҪоΪЭ,Internet.
ߵλִ(Ϣľ뼼о  100045)
⽨ƽ(廪ѧѧ뼼ϵ  100084)
ο
1Lin C, Chandhury A, Whinston A B et al. Logical inference of Horn clauses in Petri net models. IEEE Transactions on Knowledge and Data Engineering, 1993,5(3):416425
2 ִ.PetriHornӾ߼.ѧ,1993,4(4):3237
(Lin Chuang. Application of Petri nets to logical inference of Horn clauses. Journal of Software, 1993,4(4):3237)
3 Murata T, Subrahmanian V S, Wakayama T. A Petri net model for reasoning in the presence of inconsistency. IEEE Transactions on Knowledge and Data Engineering, 1991,3(3):281292
4 Peterka G, Murata T. Proof procedure and answer extraction in Petri net model of logic programs. IEEE Transactions on Software Engineering, 1989,15(2):209217
5 Chardhury A, Marinescu D C, Whinston A B. Net-based computational models of knowledge processing systems. IEEE Expert, April 1993. 7986
6 Lin C, Murata T. A Petri net model for nonmonotonic reasoning based on annofafed logic programs. EIECE Transactions on Fundamentals, 1994,E77-A(10):15791587
7 Murata T. Petri nets: proPetries, analysis and applications. Proceedings of the IEEE, 1989,77(4):541580
8 Sandewell E. A functional approach to non-monotonic logic. Computer Intelligence, 1985,(1):8087
9 Watanabe T, Mizobata Y, Onata K. A Petri net-based algorithm for proofs in Horn clause prepositional logic. In: Proceedings of the ISCAS'90. May 1990
1997-04-14յԭ,1998-03-16յ޸ĸ
