19.4 一个电话系统的描述实例
本章目录 · 1 节
本章导读
【19.4 用集合、关系和逻辑描述电话系统】本节保留原书的电话交换系统实例,用状态、不变量、操作前后关系说明形式化需求分析。它是简化模型,不直接冒充完整的现代电话协议。图的“无呼叫记录”是线路进入前或释放后的外部情形,不是State中的第八个状态。
两图合起来表示原图全部15条边。LiftFree:拿起听筒;Dial:每次拨一位;Relift:受话方接听;Clear、ClearLine、ClearConnect:呼叫方在相应阶段放弃;Sy1—Sy4为系统转接。dialing的Dial自环不可漏掉。释放边表示移除该呼叫记录,不是回到seize状态。
【集合与类型】数字集D={0,…,9},S=D*为所有有限数字串,含空串λ,S可数。Subs⊆S为已分配号码;采用实际号码非空且Subs非空的条件,保证λ∈Valid而λ∉Subs。Free、Bad、Busy两两不交且并为Subs,分别待用、失效、占线;允许某类为空,应称“允许空类的分类”,不同于第2章要求非空块的严格划分。
Valid={n∈S|存在s∈Subs使n为s的前缀},包括完整号码及其所有前缀,Subs⊆Valid。State={seize,dialing,connecting,engaged,unobtainable,ringing,speech};Connect={ringing,speech};Link=Connect∪{connecting,engaged}。
【呼叫记录与投影】Subrec是满足下列约束的(s,n)∈State×S:
st:Subrec→State,st(s,n)=s;num:Subrec→S,num(s,n)=n。因此每个记录r=(st(r),num(r))。不同线路可能同处一个状态,所以Subrec是关系,不能把它理解成“每种状态只对应一个号码”的函数。
【命题19.4.1】(dialing,n)∈Subrec当且仅当n∈Valid−Subs−{λ}。证明:dialing≠seize,故n≠λ;dialing≠unobtainable,故n∈Valid;dialing∉Link,故n∉Subs。三条件同时满足也使原来的三个双条件均真。
【部分函数与右复合】call:Subs⇀Subrec为部分函数,call(u)=(s,n)表示呼叫方u当前记录;没有正在发起呼叫的用户不在dom(call)中。本书○为右复合:先call再st,所以(call○st)(u)=st(call(u)),先call再num同理。不要用常见左复合习惯颠倒顺序。
定义域限制A◁R={(x,y)∈R|x∈A},值域限制R▷B={(x,y)∈R|y∈B}。原书前文也写R◁A表示定义域限制,本节统一使用A◁R并给出集合定义,避免两种位置混用。于是Callers=dom((call○st)▷Connect),connected=Callers◁(call○num)。
【命题19.4.2】Callers⊆dom(call○st)⊆dom(call)⊆Subs。又当u∈Callers时其状态属于Connect⊆Link,由Subrec约束num(call(u))∈Subs,故connected:Subs⇀Subs。
【补足原模型的单射条件】仅证明定义域、值域包含于Subs,只能证明connected是部分函数,不能证明单射。反例:两个不同用户u、v都记录(ringing,w),则都连向w,原来的记录类型、分类仍可满足,但connected不是单射。若系统禁止同一被叫方同时被两条接通线路占用,必须另加不变量:u,v∈Callers且num(call(u))=num(call(v))⇒u=v。加入它才能写“单射部分函数”;不能从两个包含式凭空推出。
【系统不变量】每时刻t,Busyₜ=dom(callₜ)∪ran(connectedₜ),Freeₜ、Badₜ、Busyₜ两两不交且并为Subs;并保持上述call类型、Callers定义、connected定义及单射条件。若要求禁止自呼叫、号码前缀无歧义等,还需另设相应业务约束,原书并未以集合类型自动证明这些性质。
【命题19.4.3、推论19.4.1】从Freeₜ∩Busyₜ=∅及交对并分配,得到Freeₜ∩dom(callₜ)=∅、Freeₜ∩ran(connectedₜ)=∅;因Callersₜ⊆dom(callₜ),又得Freeₜ∩Callersₜ=∅。
【命题19.4.4 初始状态存在】取Free₀=Subs、Bad₀=∅、call₀=∅;代入Callers₀定义,空关系右复合仍为空,限制后仍为空,故Callers₀=∅;再代入connected₀=∅◁(∅○num)=∅。类型检查:Subs、∅均为Subs子集;空关系是所需部分函数且单射;Busy₀=∅,允许空类的分类成立。因此确实存在满足全部不变量的初始状态。
这依次对应原式19.4.1—19.4.8的集合类型、call类型、connected类型、Free₀与Bad₀、call₀、分类、Callers₀、connected₀八组条件。代入已定义量再消去恒真的约束,可将存在性证明化为这些直接成立的条件,而不是删除尚未证明的条件。
【LiftFree操作】输入s?∈Subs,前置条件s?∈Free。后态用′:Free′=Free−{s?},Bad′=Bad,call′=call∪{(s?,(seize,λ))};Callers′、connected′由其定义计算。问号仅表示输入变量,不是逻辑问句。
【命题19.4.5】Callers′=Callers且connected′=connected。证明:新记录状态seize∉Connect,在(call′○st)▷Connect中被过滤,原记录不变,故Callers不变;s?∈Free且Free∩Callers=∅,所以定义域限制Callers◁{(s?,λ)}为空,新号码投影也被过滤,connected不变。不能只检查st而忘记num。
【命题19.4.6 前置条件充分且必要】s?∈Free使s?∉dom(call),所以新旧定义域不交,call′仍为部分函数;(seize,λ)满足Subrec约束。Busy′=Busy∪{s?},从Free删去同一s?并加进Busy,Bad不变,分类保持;connected不变,单射也保持。反过来该操作明确要求输入原本待用,否则不满足操作的启用条件。原式19.4.9—19.4.18依次检查后态集合、函数类型、分类与定义、输入和三条赋值;代入这些定义后,剩下的正是s?∈Free。
Clear输入须在dom(call)且状态为seize、dialing、engaged、connecting、unobtainable之一;ClearLine仅ringing;ClearConnect仅speech。实际定义释放操作时还应移除相应call记录,按后态connected重新计算占线集合,不能简单把仍参与其他呼叫的号码加入Free。表列的是原书的启用条件,不伪装成已经给出了所有操作的完整实现。
