ѧ
Journal of Software
2000 Vol.11 No.1 P.116-121



߼һ֤
ɾꪡ»
ժҪDC/P(duration calculus prover)һʵʱ߼ĸ֤.GentzenʽΪ֤ϵͳ,дԶж㷨ȼ֤Զ.ĽDC/P뷽õʽ֤ϵͳʵּ,Ӧʵ.
ؼʡ߼,ʱ߼,ֵ,ʱ,ʽ,֤.
ͼšTP301
A Proof Assistant for Interval Logics
HU Cheng-junWANG JiCHEN Huo-wang
(School of ComputerNational University of Defense TechnologyChangsha410073)
AbstractDC/P (duration calculus prover) is a proof assistant for a family of interval logics. It adopts the Gentzen-style sequent calculus as its basic proof system. The techniques such as term rewriting and automatic decision procedure are integrated to automate many trivial proof steps. In this paper, the authors briefly describe the semantic encoding approach, and the sequent calculus, as well as the related implementation techniques of the DC/P.
Key wordsNeighbourhood logic, interval temporal logic, mean calculus, duration calculus, sequent calculus, theorem proving.
Ϊһʵʱ߼,߼ǿӦӲ·ʵʱϵͳ1,2.߼ڵʽ߼(point based temporal logic)ĸǹʽ,ʱ.ĳЩ,,AһlĹ۲Ϊ桱,ʹ߼Ƶ㡢Ȼ.
Ľǿʱ㶨֤(duration calculus prover,DC/P)(DC/P汾1.0ɴhttp://www.iist.unu.edu/hcj,ҪҲϵ).Ϊ߼һ֤,DC/PĿǽƵ̻е()Զ,ʹǴӿ׷ֹƵнѳ.DC/Pʵְ֧߼3(neighbourhood logic,NL)ʱ߼4,5(interval temporal logic,ITL)ֵ6(mean calculus,MC)ʱ7(duration calculus,DC)ڵһʵʱ߼ĸ֤.֮ǰ,SkakkebkPC/DC8֪Ψһʱ㸨֤.PC/DCһɫĹ,ȱǽ֧DCҺѱû(PC/DCνġParser/Unparser,һʵƽ̨ضܶά).DC/PPC/DCһЩŵ,ڴ˻һЩĽ.DC/Pǽʽ,Gentzenʽ(sequent calculus)Ϊ֤ϵͳ,ͬʱҲдԶж㷨ȼ,ûֻڸ߲һЩ,ϸDC/PԶ.
DC/Pʵƽ̨SRI˾ԭ֤ϵͳPVS9.ʵDC/Pʱ,ǲ뼼.뼼Ǵͷһȫ¶֤ߵҪԭ,һǿԽϿصõһɿбϵԭϵͳ,һǿԽעط߼֤ϵͳԶ.DC/Pʵַ߼֤ߵʵ־вο.
1
ǲõף10ݵĻ˽ϴĶõ.,״̬ʽȱ.
ǲPVSrealʾʱ.ʱʾ

״̬ͨʾΪʱ򵽲еĺ.Ȼ,״̬Ԫ(ʽ)ڻ
,ͨٶ״̬Ԫɱ(finite variability)ʹֺ.һ
ԼPVSν£

,TΪһͲ.Finite-Variability(f)һݹ鶨ĸ߽ν,京,
һ,ܴһȻnʹúfǡn.
ǿ״̬ʩӸ֡͡Եõ״̬ʽ.״̬ӿɡķ.F1,F2Ϊboolstate,tΪһTimeͱԪ,̺ӿɶΪ
=(F1,F2):boolstate=(LAMBDA t:F1(t) IMPLIES F2(t));
߼ȫֱԪʱԪ.,ǰ״̬ʽĻ(ֵ)ΪʱԪ,ϢȫֱԪʱԪ.

ȫֱԪʵͳʱ,ʹǿ(type coercion).iΪInterval,ת£
n(t:T):IntervalT=LAMBDA i:t;CONVERSION n;
תnǶ̬,ԽһTתΪһͣIntervalT,ʵӲ͵ʽ.PVSͼϵͳԶԵûתԻƥ,,ڹ淶,Կó淽ʽдֱʽ,l+0,gx*5.
Ʒ,ʵͨ.ϵĳ˷㶨Ϊ
*(t1,t2):Term=(LAMBDA i:t1(i)*t2(i));
DC/P,ûаReimanĻ۱뵽Ԫ߼,ǽӽΪδ庯,һ鹫̻.ף11Ѿ֤ù걸.Ӽֵ£

߼ĹʽǴ䵽ĺForm:TYPE=Intervalbool.ͬ,ͨķ,ǿԵõĹϵӡӴʼ.磺
>=(t1,t2):Form=(LAMBDA i:t1(i)>=t2(i));
/(A,B):Form=(LAMBDA i:A(i) OR B(i));
every(L:TForm):Form=(LAMBDA i:(FORALL gx: L(gx)(i))).
NLģ̬ʡlITLġchopģ̬ʡ,͡£

߼Ĺʽ԰ͳһʽ뵽Ԫ߼.ֱϽ,ʽAiΪ浱ҽA(i)ȼʽtrueʽAΪ浱ҽA(i)iΪ.Դ˿Ա£

2Gentzen֤ϵͳ
,ԭϿͨչӵĶԪ߼֤߼Ķ.һ,һ֤ߵûϤϸڣһ֤ûзӳ߼ε˼ά,յõ֤.Ϊ˷ȱ,ǿһGentzen֤ϵͳ.
2.1Ƶ
DC/P֤ϵͳһ߼Gentzenʽй,ĹDutertreĹϵͳS5Լף12DCϵͳʽĶӦ.ƪ,ڽг롰chopӡŦɵصĲֹDCĹɹ.


,DC/Pл๦ǿ.Щʹ֤ʱܹýϴ֤,Ӷʹ֤.֤,ӵĶʱ,Ӧģ̬߼S4¹Ϊ.

,()ʾʽ,ÿһʽǸ(rigid),ʱԪɺģ̬ʣǡ()ʽ,(...)((...))Ĺʽ.
Ķ13ݸõʽĿɿԼ걸ԵĽ.
1. ʽDC/PĶ,ڱ׼ģ.
2. ʽ´һHilbert֤,DC/PĶ.
2.2
轫ʽ뵽Ԫ߼.ʽiΪĺǣڹʽAʦ,A(i)Ϊ,Bʦ,B(i)Ϊ.ʽ϶Ϊ,ʽ.Gamma,DeltaΪForm,ʽ£
seq(Gamma,Delta):bool=(GammaDelta)
ʽͨöٳԱķʾ.ӹ
emptyconsequent:Form=ff;emptyantecedent:Form=tt;
*(Gamma,X):Form=GammaX;+(Delta,X):Form=DeltaܣX;
,+,*еĸԱ,ͬ߼еļӳ.,ʽ{A,B}{C,D,E}ڪDC/PڲʵʱʾΪԪ߼ʽseq(enptyantdcedent * A * B,enptyconsequent+C+D+E).޸PVSĽӿ,û͸.ӵĶ,DC/PƵ򼰹ͿԱΪԪ߼Ĺʽ.ǿɿ,ǻӦÿ֤Ԫ߼Ķ.ԡchop󵥵Թ(ILR3a)Ϊ,Ա£
ILR3a:THEOREM seq(Gamma*(A^B),Delta) AND seq(Gamma,Delta+ۣ(C=A))
IMPLIES seq(Gamma*(C^B),Delta)
2.3֤
DC/Pֱûһ֤.֤;ѡӦĹڵǰ֤Ŀ,õһ򻯵Ŀ֤.֤ͨӦ1Ƶ,ΪһЩܡĺ.֮,֤նչΪһPVS֤.ʵַʽȷ˵ʱӰϵͳĿɿ.
DC/PĻ֤նͨĹʵʵֵ.ԡchop󵥵MONO-CHOPΪ,DC/Pȶû,ĹILR3aǰƥ,ʧ,ʾϢ˳ҵGamma,Delta,A,B,CĴ,ʵĹ򲢽л,ӶǰʽԼΪILR3aĽ.DC/PĴ󲿷֤Ӧڶ,NFLATTEN,NSPLITֱӦ߼вһĿꡢĿĹ.ʵЩʱҪԶһһƥ.
PVSṩ˳ظȽṹ϶.NPROP֤߼,ͨд֤ĿϷӦNFLATTENNSPLITʵֵ.NPROPΪ
(TRY (NFLATTEN) (NPROP)(TRY (NSPLIT) (NPROP) (SKIP)).
,TRY൱IF...THEN...ELSE...ṹ.ʽȵNFLATTEN,Ŀ,ݹ,һTRY.
֤ͨ²ʵ֣ɨǰ֤Ŀ,жӦõĹȻҪԴ֤ĿһЩ任,ƵʾĶʵĿ.¼򵥶

д֤ʱ,֤,׳ֱԵĵط.ϸʽ֤̲Ӧúκϸ,ͨϣġԶ׼Ķɸ֤Զ.DC/P,ʹû,һܵƵд֤

,Exist-introDC/P֤().Exist-introĹΪʱԪskolemx,y.Chop-monoǡchopӵĵԹ,ILR3.Rigid-outиԹʽƳchopӵϽ.,Nassertһӵ,ȶԵǰĿһ任,ȻʵԶж.֤ҲDC/PDur-chopԶ.Dur-chopһӵDC/P֤,һϵд֤гֹ,ɴĹ.,Dur-chopɨ赱ǰʽ,Ѱһp(s)q(s)ǰʽʽ,,p(s)q(s)ǹڡs(俴Ԫ)ʵʽ.Ȼ,Exist-introִskolem,ͨChop-monoRigid-out,ʽתտֱӦDC5ʽ,ͨʵԶж㷨֤ǰĿ.DC/P,вƵĸ.ЩĴ,ʹô֤Լ.
3Ӧʵ
һܻᷢй©úȼ¯7,ϣ㰲ȫʣκδ1ӵĹ۲,©ʱ䲻۲5%.淶ʱ㹫ʽ£.Ϊһ,ԱҪһЩ.,ݾ,ú¯ϵͳ㣺(1) κһ©¼1ڼ⵽(2) һ©,ú¯ķŽر,ٵȴ30sŻ´,֪Ƶú¯ȫԵ.ƲԿDCʽ£

Ϊ֤ƷϹ淶,֤DCĶ.DC/P,һʽ֤̱е.֤̳ɹʱ,ȷƵȷ.ʽDC/P£

һиļ򵥶ú¯һ.ǸDC/Pе֤
,ԸһЩӡ.

4
ʵʱ߼һ֤DC/P.DC/PҪŵ¼㣺
.ʽΪ֤ϵͳ,һ߼ֵ֤ں̶ܴϱԶ
.дʵж㷨Ӧ,֤ܶ򻯣
.һʱӼԶж̣
.PC/DC,DC/Pױû,µ߼ӡ֤ĶƵ.
Ŀǰ,ڳDC/PǶһǵʽ.,һ֪ʶָ֤,Ӷһ֤Զ̶.
лDimitar P.GelevʿϸУӢĸ,ĲʿDang Van HungʿܳڼDeTfoRsԱڶ潨,ڴ˱ʾл!
оõȻѧ(No.6960301069873045)863߿ƼĿ(No.863-306-ZT06-04-1)UNU/IIST(International Institute for Software Technology, United Nations University)Ŀ.
ɾѧѧѧԺɳ410073
ꪣѧѧѧԺɳ410073
»ѧѧѧԺɳ410073
ο
1Hansen M R, Zhou Chao-chen, Stauntrup J. A real-time duration semantics for circuits. In: TAU 1992 ACM/SIGDA Workshop on Timing Issues in the Specification and Synthesis of Digital Systems. Princeton, NJ, 1992
2Ravn A P, Rischel H, Hansen K M. Specifying and verifying requirements of real-time systems. IEEE Transactions on Software Engineering, 1993,19(1):4155
3Zhou Chao-chen, Hansen M R. An adequate first order interval logic. In: de Roever W P, Langmaack H, Pnueli A eds. International Symposium on Compositionalitythe Significant Difference (COMPOS'97). Germany: Malente/Holstein, 1997
4Moszkowski B. A temporal logic for multilevel reasoning about hardware. IEEE Computer, 1985,18(2):1019
5Dutertre Bruno. On first order interval temporal logic. Technical Report, No.CSD-TR-94-3, Department of Computer Science, Royal Holloway University of London, 1995
6Zhou Chao-chen, Li Xiao-shan. A mean value calculus of durations. In: Roscoe A W ed. A Classical Mind: Essays in Honor of C. A. R. Hoare. Englewood Cliffs, NJ: Prentice Hall International, 1994.431451
7Zhou Chao-chen, Hoare C A R, Ravn A P. A calculus of durations. Information Processing Letters, 1991,40(5):269276
8Skakkebk J U, Shankar N. Towards a duration calculus proof assistant in PVS. In: Langmack H, de Roever W P, Vytopil J eds. Formal Techniques in Real-Time and Fault-Tolerant Systems. LNCS 863, Mook, the Netherlands: Springer-Verlag, 1994. 660679
9Shankar N, Owre S, Rushby J M. The PVS Proof Checker: a Reference Manual (Beta Release). Computer Science Laboratory, Menlo Park, CA: SRI International, 1993
10Mao Xiao-guang, Xu Qi-wen, Wang Ji. Towards a proof assistant for interval logics. Technical report, International Institute for Software Technology, United Nations University. 1996
11Hansen M R, Zhou Chao-chen. Semantics and completeness of duration calculus. In: de Roever W P, de Bakker J W, Huizing C eds. Real-Time: Theory in Practice, REX Workshop. LNCS 600, Mook, the Netherlands: Springer-Verlag, 1992. 209225
12Hansen M R, Zhou Chao-chen. Duration calculus: logical foundations. Formal Aspects of Computing, 1997,9(3):283330
13Hu Cheng-jun. DC/P: a proof assistant for interval logics. Technical Report, International Institute for Software Technology, United Nations University, 1999
1998-10-22ո
1999-01-22޸
