1、軟件工程形式化方法,第5章 形式化開發(fā)方法(1),-3-,內(nèi)容安排,軟件開發(fā)的形式化方法 形式化開發(fā)方法(1) Petri網(wǎng) 形式化開發(fā)方法(2) 時(shí)態(tài)邏輯 形式化開發(fā)方法(3) Z方法,-4-,軟件開發(fā)的形式化方法,軟件開發(fā)的形式化方法定義 軟件開發(fā)的形式化方法（formal methods）是建立在嚴(yán)格數(shù)學(xué)基礎(chǔ)上，具有精確數(shù)學(xué)語義的開發(fā)方法 簡單地說，凡在系統(tǒng)研究中，應(yīng)用了數(shù)學(xué)的方法，都是形式化方法 本章所介紹的形式化開發(fā)方法是指軟件規(guī)格說明數(shù)學(xué)建模、數(shù)學(xué)驗(yàn)證和數(shù)學(xué)程序求精,-5-,形式化方法與結(jié)構(gòu)化和OO方法區(qū)別,結(jié)構(gòu)化和OO方法 使用了大量的自然語言。自然語言的二義性、不完整和抽象層次

2、的混雜等問題的解決，必然使開發(fā)系統(tǒng)的質(zhì)量不高、成本增加和進(jìn)度拖長；尤其對(duì)安全性或其他質(zhì)量因素要求極高的軟件，任何微小的錯(cuò)誤都可能帶來災(zāi)難性的后果 形式化的方法 可以幫助軟件開發(fā)人員開發(fā)出更為無二義性、完整的和準(zhǔn)確的需求規(guī)格說明，進(jìn)而通過嚴(yán)格的驗(yàn)證發(fā)現(xiàn)問題，以達(dá)到對(duì)軟件質(zhì)量、開發(fā)成本和開發(fā)進(jìn)度的有效控制,-6-,形式化開發(fā)方法發(fā)展歷史,20世紀(jì)60年代末 形式化方法與非形式化大致同步 都是為解決當(dāng)時(shí)出現(xiàn)的“軟件危機(jī)”提出 一般認(rèn)為是Floyd、Hoare和Manna等在程序正確性證明方面的研究。但由于這些方法受程序規(guī)模的限制而未能應(yīng)用 20世紀(jì)80年代末 在硬件設(shè)計(jì)領(lǐng)域形式化方法的工業(yè)應(yīng)用結(jié)果，

3、又掀起了軟件形式化開發(fā)方法的學(xué)術(shù)研究和工業(yè)應(yīng)用的熱潮，建立了一些較為成熟的方法和語言 如Petri網(wǎng)、statecharts、通信順序過程、通信系統(tǒng)演算、程序正確性證明、時(shí)態(tài)邏輯、模型驗(yàn)證、Z語言、 VDM及Larch等,-7-,目前流行的形式化開發(fā)方法,形式化規(guī)格說明建模 形式化驗(yàn)證 形式化程序求精,-8-,形式化規(guī)格說明建模,操作類 基于狀態(tài)和轉(zhuǎn)移 Petri網(wǎng)、有限狀態(tài)機(jī)和狀態(tài)圖 描述類 基于數(shù)學(xué)公理和概念 基于邏輯的描述方法：命題線性時(shí)態(tài)邏輯（PLTL）、一階線性時(shí)態(tài)邏輯（FOLTL）、計(jì)算樹邏輯（CTL） 基于代數(shù)的描述方法：Z語言、VDM和Larch 雙重類 兼有操作類和描述類兩者

4、的特點(diǎn) 擴(kuò)展?fàn)顟B(tài)機(jī)（ESM）、實(shí)時(shí)時(shí)態(tài)邏輯（RTTL）,-9-,形式化驗(yàn)證,模型驗(yàn)證和定理證明 模型驗(yàn)證是對(duì)規(guī)格說明所建立起來的模型狀態(tài)空間進(jìn)行搜索，以確認(rèn)該系統(tǒng)模型是否具有所期望的某些性質(zhì) 定理證明是以邏輯公式作為系統(tǒng)及其性能的規(guī)格說明，其中邏輯由一個(gè)具有公理和推理規(guī)則的形式化系統(tǒng)給出。進(jìn)行定理證明的過程就是應(yīng)用這些公理或推理規(guī)則來證明系統(tǒng)是否具有所期望的性質(zhì),-10-,形式化程序求精,形式化程序求精就是將自動(dòng)推理與形式化規(guī)格說明相結(jié)合而形成的一門技術(shù) 研究如何從形式化的規(guī)格說明推演出具體的面向計(jì)算機(jī)的程序代碼的全過程 基本思想就是用一個(gè)抽象程度低和過程性強(qiáng)的程序，去代替一個(gè)抽象程度高和過程

5、性弱的程序，并保證它們的功能和性質(zhì)完全一致 形式化程序求精與形式化規(guī)格說明和形式化驗(yàn)證三者是緊密聯(lián)系和相輔相成,-11-,形式化開發(fā)方法主要問題,對(duì)軟件開發(fā)人員（包括管理人員和用戶）的數(shù)學(xué)素質(zhì)有較高的要求 主要是離散數(shù)學(xué)中的集合、代數(shù)結(jié)構(gòu)、數(shù)理邏輯等基礎(chǔ)內(nèi)容在軟件工程中的具體應(yīng)用 對(duì)于原來一些數(shù)學(xué)背景較差的工程人員要花許多時(shí)間去學(xué)習(xí)和掌握。有的甚至還要克服對(duì)數(shù)學(xué)的畏懼心理 在選擇和應(yīng)用形式化開發(fā)方法時(shí)應(yīng)注意的問題 Bowan和Hinchley提出了“形式化法方法的十條戒律”,-12-,形式化開發(fā)方法(1) Petri網(wǎng),-13-,什么是Petri網(wǎng) Petri網(wǎng)是一種網(wǎng)狀結(jié)構(gòu)的系統(tǒng)的描述和分析

6、工具 對(duì)于具有并發(fā)、異步、分布、并行、不確定性或隨機(jī)性的信息系統(tǒng)，都可以利用這種工具構(gòu)造出要開發(fā)的Petri網(wǎng)模型。然后對(duì)其進(jìn)行分析，即可得到有關(guān)系統(tǒng)結(jié)構(gòu)和動(dòng)態(tài)行為方面的信息。根據(jù)這些信息就可以對(duì)要開發(fā)的系統(tǒng)進(jìn)行評(píng)價(jià)和改進(jìn) Petri網(wǎng)的提出 由德國C.A. Petri在他的62年博士論文“Communication with automata”中提出 當(dāng)時(shí)引起一些歐美科學(xué)家的重視。他們?cè)谝眠@種網(wǎng)狀結(jié) 構(gòu)模擬和分析并行系統(tǒng)中稱它為“Petri Nets”。從此以后大家都稱它為Petri網(wǎng),-14-,Petri網(wǎng)介紹的內(nèi)容,示例-四季系統(tǒng) Petri網(wǎng)的定義 Petri網(wǎng)的基本原理-靜態(tài)結(jié)構(gòu)

7、Petri網(wǎng)的基本原理-動(dòng)態(tài)特征 建模實(shí)例 特性分析 Petri網(wǎng)的特性分析方法 改進(jìn)Petri網(wǎng)及其應(yīng)用 時(shí)間網(wǎng)和隨機(jī)網(wǎng) 從Petri網(wǎng)到程序結(jié)構(gòu)的轉(zhuǎn)換,-15-,示例：四季系統(tǒng),一年有四季，四季氣候的變化,該系統(tǒng)可以由圖形表示,-16-,系統(tǒng)的Petri網(wǎng)圖形表示,-17-,系統(tǒng)的Petri網(wǎng)數(shù)學(xué)表示,=（P，T；F，M0） P=p1, p2, p3, p4 T=t1, t2, t3, t4 F=（p1, t1）, （t1, p2）, （p2, t2）, （t2, p3）, （p3, t3）, （t3, p4）, （p4, t4）, （t4, p1） M0=（0, 0, 0, 1）,-18

8、-,Petri網(wǎng)描述系統(tǒng)的特點(diǎn),從四季系統(tǒng)中，可以看出這種利用事物的因果關(guān)系對(duì)系統(tǒng)進(jìn)行網(wǎng)狀結(jié)構(gòu)的描述，有以下特點(diǎn) 自然 沒有任何不必要的人為控制，完全反映了現(xiàn)實(shí)世界的真實(shí)情況 局部確定原理 因?yàn)槭录蜣D(zhuǎn)移的發(fā)生和結(jié)果都由局部狀態(tài)決定 既有系統(tǒng)靜態(tài)結(jié)構(gòu)，又有動(dòng)態(tài)行為方面的信息 既有圖形工具，又有數(shù)學(xué)工具 圖形工具和數(shù)學(xué)工具完全等價(jià) 圖形工具直觀、形象、易懂、易學(xué)；數(shù)學(xué)工具嚴(yán)謹(jǐn)，既便于計(jì)算，又便于驗(yàn)證,-19-,Petri網(wǎng)的基本原理：靜態(tài)結(jié)構(gòu),任何系統(tǒng)都有兩類元素組成：表示狀態(tài)的元素和表示狀態(tài)變化的元素 Petri網(wǎng) 位置（place）：狀態(tài) 轉(zhuǎn)移（transition）：改變狀態(tài) 兩者之間的依

9、賴關(guān)系用弧（箭頭）表示,-20-,Petri網(wǎng)的基本成分（1）,-21-,Petri網(wǎng)的基本成分（2）,其中： P=（p1,p2, ,pm）是N的有窮位置集合, T=（t1,t2,tn ）是N的有窮轉(zhuǎn)移集合, F是由N中一個(gè)P元素和一個(gè)T元素組成的有序偶的集合，F(xiàn)稱為流關(guān)系。（PT）和（TP）中的“ ”為笛卡爾乘積。 DOM（F）=x y：（x,y） F，COD（F）= x y：（y，x F分別為F所含的有偶序偶的第一個(gè)元素組成的集合和第二個(gè)元素組成的集合。,-22-,Petri網(wǎng)的基本成分（3）,由上可以說明 N=（P,T；F）是位置集合P和轉(zhuǎn)移集合T構(gòu)造Petri網(wǎng)的兩個(gè)基本成分,P與T兩

10、者間的流關(guān)系F是從它們構(gòu)造出來的。所以在P、T之后的F用分號(hào)“；”隔開來 PT 說明網(wǎng)中至少要有一個(gè)元素,PT= 說明P和T為兩類不同的元素,兩者不能有交 F （PT） （TP）說明一個(gè)P元素代表一個(gè)資源,其流動(dòng)由F關(guān)系規(guī)定。所以,轉(zhuǎn)移T只能與位置有直接的流關(guān)系,不是從PT,就是從T P。而不參與任何轉(zhuǎn)移的資源為孤立的P,不引起資源流動(dòng)的轉(zhuǎn)移為孤立的T。所以DOM（F） COD（F）=P T說明網(wǎng)中不能有孤立的元素P或T,-23-,前集、后集、子網(wǎng),設(shè) ，令 *x=y|（y, x）F, x*=y|（x, y）F *x被稱為x的前集或輸入集。 x*被稱為x的后集或輸出集。 在N1=（P1,T1;

11、F1）和N2=（P2,T2;F2）中， 如果 , , 且 , 則稱N1是N2的子網(wǎng)。,-24-,純網(wǎng),在N=（P,T；F）中,如果對(duì)似有xPT,都有*x x*= ,則稱N為純網(wǎng)（pure net） 純網(wǎng)中無公共前后集（環(huán)）,-25-,簡單網(wǎng),如果對(duì)所有x,yPT,都有（*x= *y） （x*=y*） x=y,則稱N為簡單網(wǎng)（simple net） 簡單網(wǎng)中無相同的前后集,-26-,Petri網(wǎng)的基本原理：動(dòng)態(tài)特征（1）,Petri網(wǎng)作為系統(tǒng)的建模工具,除具有上述描述的靜態(tài)結(jié)構(gòu)外,還應(yīng)包括位置的容量和轉(zhuǎn)移發(fā)生對(duì)位置容量的影響信息。有限容量可用大于零的整數(shù)表示,轉(zhuǎn)移發(fā)生對(duì)位置中標(biāo)記數(shù)的影響用孤上的

12、整數(shù)表示。于是,具有動(dòng)態(tài)特征的Petri網(wǎng)可表示為六元組：,-27-,Petri網(wǎng)的基本原理：動(dòng)態(tài)特征（2）,Petri網(wǎng)的六元組： 其中： （P,T；F）含義同前 K：PN 是位置上的容量函數(shù),N= 0,1,2,3, ,若K（p）= ,表示位置中的容量為無窮 W：F N是孤集合上的孤函數(shù) M：P N0是Petri網(wǎng)的標(biāo)識(shí)（marking）。M0為初始標(biāo)識(shí), N0=0,1,2,3, , pP,必須滿足M（p） K（p） 在Petri網(wǎng)的圖形表示中,M（p）不是用數(shù)字,而是用實(shí)圓點(diǎn)表示。每個(gè)實(shí)圓點(diǎn)為一個(gè)標(biāo)記,同一個(gè)位置中的諸多標(biāo)記代表同一類完全等價(jià)的個(gè)體?；。▁,y）上的W值標(biāo)注在孤（x,y）上

13、,-28-,轉(zhuǎn)移發(fā)生規(guī)則（1）,Petri網(wǎng)的動(dòng)態(tài)行為是通過轉(zhuǎn)移發(fā)生引起標(biāo)識(shí)改變來體現(xiàn)的 轉(zhuǎn)移可發(fā)生的條件和發(fā)生規(guī)則 轉(zhuǎn)移t 可發(fā)生的條件 若在標(biāo)識(shí)M下, p1, p1*t M（p1） （p1,t）, 且p2, p2 t* M（p2）+W（t, p2） K（p2）+W（t, p2） K（p2）,此時(shí)稱t在M 下可發(fā)生,記為M t 轉(zhuǎn)移t發(fā)生的結(jié)果 若t在M下可發(fā)生, 就可以發(fā)生, 發(fā)生后將M 變成新標(biāo)識(shí)M,出視方出記為MtM 或M M,并稱M 為M 的后繼標(biāo)識(shí) 對(duì)p P, M（p）=M（p）W（p,t） 當(dāng)p* t t * =M（p）W（t,p） 當(dāng)pt * * t =M（p） W（p,t）

14、W（t,p） 當(dāng)p * t t * =M（p） 當(dāng)pt * * t,-29-,轉(zhuǎn)移發(fā)生規(guī)則（2）,注意 一個(gè)沒有任何輸入位置的轉(zhuǎn)移叫源轉(zhuǎn)移,一個(gè)源轉(zhuǎn)移的可發(fā)生是無條件的。一個(gè)源轉(zhuǎn)移的發(fā)生只會(huì)產(chǎn)生標(biāo)記,而不消耗任何標(biāo)記 一個(gè)沒有任何輸出位置的轉(zhuǎn)移叫潭轉(zhuǎn)移,一個(gè)潭轉(zhuǎn)移的發(fā)生將消耗標(biāo)記,而不產(chǎn)生任何標(biāo)記,-30-,示例：轉(zhuǎn)移發(fā)生規(guī)則,以本例來說明網(wǎng)論中的轉(zhuǎn)移發(fā)生規(guī)則，以及網(wǎng)論中的沖突（conflict）、并發(fā)（concurrent）和碰撞（contact）現(xiàn)象 有時(shí)，一個(gè)Petri網(wǎng)中同時(shí)存在并發(fā)和沖突，而且并發(fā)的發(fā)生會(huì)引起沖突的消失或出現(xiàn)。網(wǎng)論中稱這種現(xiàn)象為混惑（confusion）,-31-,并

15、發(fā)和沖突概念的完整描述,并發(fā) 設(shè)M 為Petri網(wǎng)的一個(gè)標(biāo)識(shí)，若存在t1和t2使得M t1 和M t2 ，并滿足 ，且則稱t1和t2 在M 下并發(fā) 沖突 設(shè)M 為Petri網(wǎng)的一個(gè)標(biāo)識(shí)，若存在t1和t2使得M t1 和M t2 ，并滿足 ，且則稱t1 和t2 在M 下沖突,-32-,網(wǎng)系統(tǒng)分類,根據(jù)Petri網(wǎng)系統(tǒng)中容量函數(shù)K和權(quán)函數(shù)W的不同可分為三種情況 K1，W1 為基本網(wǎng)（elementary net,EN）系統(tǒng) 這種網(wǎng)系統(tǒng)位置p 中，只有有標(biāo)記和無標(biāo)記兩種狀態(tài)。習(xí)慣上把這種網(wǎng)稱為條件/ 轉(zhuǎn)移網(wǎng)系統(tǒng) K，W1 為P/T（place/transition）網(wǎng) K和W為任意函效 為P/T系統(tǒng)

16、 P/T網(wǎng)和P/T系統(tǒng)中都是物質(zhì)資源，它們與EN系統(tǒng)有本質(zhì)的不同。所以，EN系統(tǒng)又叫做條件/事件網(wǎng)系統(tǒng)。 P/T網(wǎng)和P/T系統(tǒng)也有區(qū)別。K（p）（位置容量）是其能容納此類資源的能力，也稱空間資源。而W（p,t）和W（t,p）分別是轉(zhuǎn)移t 發(fā)生時(shí)釋放和占用此類空間資源的數(shù)量。P/T網(wǎng)的位置p 容量足夠大，所以不會(huì)發(fā)生碰撞。而P/T系統(tǒng)，如果位置p 容量有限，且不進(jìn)行技術(shù)處理，則有可能發(fā)生碰撞,-33-,Petri網(wǎng)轉(zhuǎn)移發(fā)生規(guī)則的簡化,對(duì)Petri網(wǎng)簡化的原因是為了對(duì)Petri網(wǎng)進(jìn)行理論上研究的方便 通過上面討論可以看出，對(duì)于簡單的Petri網(wǎng)，由于K和W已無任何限制作用。所以，一般把這種Petr

17、i網(wǎng)系統(tǒng)記為：=（N,M）=（P,T;F,M）。這種Petri網(wǎng)系統(tǒng)的轉(zhuǎn)移發(fā)生規(guī)則，可以簡化為： 若Mt，當(dāng)且僅當(dāng)p p，M （p） 1，t 發(fā)生后，Mt M M （p）=M （p） 1 當(dāng) p * t t * =M （p） 1 當(dāng) p t * * t =M （p） 其它 網(wǎng)論可以證明，經(jīng)過適當(dāng)加技術(shù)處理，都可以把K、W任意的P/T網(wǎng)或P/T系統(tǒng)改造為K ,W 1的Petri網(wǎng) M（p）=M（p） 1 當(dāng)p * t t * =M（p） 1 當(dāng)p t * * t =M（p） 其它,-34-,建模實(shí)例：有限狀態(tài)機(jī),-35-,建模實(shí)例：并行活動(dòng),-36-,建模實(shí)例：數(shù)據(jù)流計(jì)算,-37-,建模實(shí)例：通

18、信協(xié)議,-38-,建模實(shí)例：同步控制,-39-,建模實(shí)例：生產(chǎn)者/消費(fèi)者系統(tǒng)（1）,-40-,建模實(shí)例：生產(chǎn)者/消費(fèi)者系統(tǒng)（2）,抑制弧,-41-,建模實(shí)例：形式語言,-42-,建模實(shí)例：機(jī)械加工（1）,-43-,建模實(shí)例：機(jī)械加工（2）,-44-,建模實(shí)例：機(jī)械加工（3）,-45-,建模實(shí)例：機(jī)械加工（4）,-46-,建模實(shí)例：機(jī)械加工（5）,-47-,特性分析,Pretri網(wǎng)的特性主要包括 可達(dá)性（Reachability） 有界性（Boundedness） 活性（Liveness） 可逆性（Reversibility） 可覆蓋性（Coverability） 持久性（Persistence

19、） 同步距離（Synchronic Distance） 公平性（Fairness）,-48-,特性分析-可達(dá)性,對(duì)Petri網(wǎng)（N，M0），如果存在一個(gè)從M0到Mn的發(fā)生序列，則稱標(biāo)識(shí)Mn是從M0可達(dá)的。發(fā)生序列表示為= M0t1M1t2M2t3M3tnMn，或簡化為 =t1t2tn。 可用M0 Mn 表示三者間的關(guān)系。在Petri網(wǎng)（N,M）中所有從標(biāo)識(shí)M0可達(dá)的標(biāo)識(shí)集合，可表示為R（N，M0）或個(gè)簡化為R（M0）。從M0出發(fā)的所有可能發(fā)生序列的集合，可表示為L（N,M0）或簡化為L（M0）。 這樣,Petri網(wǎng)的可達(dá)性問題就轉(zhuǎn)換為對(duì)于Petri網(wǎng)（N,M）和給定標(biāo)識(shí)M0,尋找是存在M0 R

20、（M0） 可達(dá)性是研究任何系統(tǒng)動(dòng)態(tài)特性而與基礎(chǔ),-49-,特性分析-有界性,對(duì)Petri網(wǎng)（N,M），若存在一個(gè)非負(fù)整數(shù)K，使得M0的任何一個(gè)可達(dá)標(biāo)識(shí)的每個(gè)位置中的標(biāo)記數(shù)都不超過K，即對(duì)每個(gè)標(biāo)識(shí)MR（M0）和每個(gè)位置p,M （p） K 均成立，則稱Petri網(wǎng)（N,M0）為K有界，或簡稱有界 若Petri網(wǎng)（N,M0）為1有界，則稱此Petri網(wǎng)為安全的。這種網(wǎng)的每一個(gè)位置要么有一個(gè)標(biāo)記，要么沒有標(biāo)記 通常用Petri網(wǎng)中的位置表示實(shí)際系統(tǒng)中存儲(chǔ)數(shù)據(jù)的緩沖區(qū)和寄存器。通過分析網(wǎng)的有界性或安全性，就可以考察實(shí)際系統(tǒng)中緩沖區(qū)或寄存器是否會(huì)溢出,-50-,特性分析-活性,一個(gè)Petri網(wǎng)（N,M）被

21、稱為活的或稱M0是網(wǎng)N的一個(gè)活標(biāo)識(shí)，僅當(dāng)從M0可達(dá)的任一標(biāo)識(shí)出發(fā)都可以通過執(zhí)行某一轉(zhuǎn)移序列而最終發(fā)生任一轉(zhuǎn)移。這意味著，無論選擇什么樣的發(fā)生序列，一個(gè)活的Petri網(wǎng)都可以保證無死鎖操作?；钚允窃S多系統(tǒng)的理想特性。但這是不現(xiàn)實(shí)現(xiàn)的，也是不必要的 對(duì)于Petri網(wǎng)（N，M0）中的一個(gè)轉(zhuǎn)移t，實(shí)際上可能屬于以下情況： L0級(jí)活（死的）：僅當(dāng)t在L（M0）中任何發(fā)生序列中都無法發(fā)生 L1級(jí)活（可能能發(fā)生）：僅當(dāng)t 在L（M0）中的一些發(fā)生序列中至少可發(fā)生一次 L2級(jí)活：已知任一正整數(shù)k，僅當(dāng)t 在L（M0）中的一些發(fā)生序列至少可發(fā)生k 次 L3級(jí)活：僅當(dāng)t 在L（M0）中的一些發(fā)生序列中可以無限制的

22、發(fā)生 L4級(jí)活（活的）：僅當(dāng)t 在R（M0）中的每個(gè)標(biāo)識(shí)是L1活的,-51-,特性分析-可逆性,一個(gè)Petri網(wǎng)（N,M0）稱為可逆的，僅當(dāng)對(duì)R （M0）中每個(gè)標(biāo)識(shí)M,M0都是從M可達(dá)的。因此，一個(gè)可逆網(wǎng)可以返回到初始標(biāo)識(shí)或初始狀態(tài)。在很多名小應(yīng)用中只要求系統(tǒng)回到某個(gè)特定狀態(tài)而無需回到初始狀聲在態(tài)我們稱這個(gè)特定狀態(tài)為主（home）狀態(tài)即對(duì)于R（M0）的每個(gè)標(biāo)識(shí)M,主狀態(tài)M 都是可達(dá)的 有界性、活性和可逆性是三種相互獨(dú)立的特性,-52-,特性分析-可覆蓋性,一個(gè)Petri網(wǎng)（N,M0）中一個(gè)標(biāo)識(shí)M稱做可覆蓋的，僅當(dāng)在R （M0）中存在一個(gè)標(biāo)識(shí)M，使得對(duì)網(wǎng)中的每個(gè)位置M（p） M（p）成立 可覆蓋

23、性與L1活（潛在的可發(fā)生性）緊密相關(guān)。設(shè)M是轉(zhuǎn)移t發(fā)生所必需的最小標(biāo)識(shí)。那么，當(dāng)且僅當(dāng)M是不可覆蓋的，t是死的（非L1活）。也就是說，t是L1活，當(dāng)且僅當(dāng)M是可覆蓋的,-53-,特性分析-持久性,一個(gè)Petri網(wǎng)（N,M0）稱為持久的，僅當(dāng)對(duì)于任意兩個(gè)可發(fā)生轉(zhuǎn)移，其中一個(gè)轉(zhuǎn)移的發(fā)生不會(huì)使另一個(gè)轉(zhuǎn)移不發(fā)生。就是說，持久網(wǎng)中的一個(gè)轉(zhuǎn)移一旦可發(fā)生，將保持這種可發(fā)生性直至它發(fā)生為止 所有位置都只有一條輸入孤和一條輸出弧的Petri網(wǎng)（標(biāo)識(shí)圖）具有持久性,-54-,特性分析-同步距離,同步距離是條件/事件系統(tǒng)中兩個(gè) 事件間相互獨(dú)立程度緊密相關(guān)的 一種量度。我們用 來定義Petri網(wǎng)（N,M0）中兩個(gè)轉(zhuǎn)移

24、 t1 和t2 間的同步距離。其中 是起始于R （M0） 中的任何標(biāo)識(shí)M 的一個(gè)發(fā)生序列，（t i ）是轉(zhuǎn)移 t i （ I = 1,2, ）在 中發(fā)生的次數(shù)。 右圖們?nèi)运綪etri網(wǎng)中 d12=1,d34=1,d13= 同步有不同的形式（見例1例5）,-55-,同步形式（1）,它們共同執(zhí)行一個(gè)任務(wù)，只有p1、p2中的標(biāo)記同時(shí)到達(dá)時(shí)才能同步,-56-,同步形式（2）,這是一個(gè)順序系統(tǒng)，t1, t2為同步。但它們交替發(fā)生，t1與t2的關(guān)系為11,-57-,同步形式（3）,這是一個(gè)并發(fā)系統(tǒng)，t1、t2發(fā)生的關(guān)系也為11。但它們不是交替發(fā)生，而可同時(shí)發(fā)生，也可一先一后發(fā)生,-58-,同步形式（4）

25、,本例中，t2不能先發(fā)生，只有t1可以發(fā)生。這也就是說，只有t1發(fā)生后，t2才能發(fā)生。這時(shí)，仍只有t1能夠發(fā)生。即t1第二次發(fā)生后，t2才能發(fā)生。由此可見t1與t2也為順序關(guān)系，但它們的關(guān)系為21,-59-,同步形式（5）,本例中，t1與t2的關(guān)系為1或1，這就等于無同步可言,-60-,同步距離刻畫事件間的同步關(guān)系,d12= 兩組事件不同步，即異步 d12 兩組事件以d12為距離相互同步 d12=0 兩組事件在時(shí)間和空間上一起發(fā)生，網(wǎng)論中將它們當(dāng)做一個(gè)事件 d12=1 兩組事件必須交替發(fā)生,-61-,特性分析-公平性,兩種基本公平性 有界公平性 對(duì)于兩個(gè)轉(zhuǎn)移，若不發(fā)生其中一個(gè)轉(zhuǎn)移另一個(gè)轉(zhuǎn)移可以

26、發(fā)生的最大次數(shù)是有界的，則稱兩個(gè)轉(zhuǎn)移為有界-公平（或-公平）關(guān)系。若Petri網(wǎng)（N,M0）中每對(duì)轉(zhuǎn)移都是-公平關(guān)系，則外該網(wǎng)為-公平網(wǎng) 無條件（全局）公平性 對(duì)于一個(gè)發(fā)生序列 ，若它為有限的或網(wǎng)中每個(gè)轉(zhuǎn)移在中無限次出現(xiàn)，則稱 為無條件（全局）公平的。 若從R（M0）中某個(gè)M開始的每個(gè)發(fā)生序列 都是無條公平的，則稱Petri網(wǎng)（N,M0）為無條件公平網(wǎng) 兩種類型公平性之間的關(guān)系 每個(gè)-公平網(wǎng)都是無條件公平網(wǎng)每個(gè)有界的無條件公平網(wǎng)都是-公平網(wǎng),-62-,Petri網(wǎng)的特性分析方法,分層或化簡 可覆蓋性（可達(dá)性）樹 不變量、關(guān)聯(lián)矩陣和狀態(tài)方程,-63-,Petri網(wǎng)的分層,Petri網(wǎng)分層的方法

27、自頂向下（一個(gè)子網(wǎng)替代一個(gè)結(jié)點(diǎn)） 自底向上（一個(gè)結(jié)點(diǎn)替代一個(gè)子網(wǎng)） 結(jié)點(diǎn)的選擇 一般以轉(zhuǎn)移t為結(jié)點(diǎn)，也可以位置p為結(jié)點(diǎn) 子網(wǎng)結(jié)構(gòu)的限制 這是由于Petri網(wǎng)的異步并發(fā)性質(zhì)決定的 解決的方法有：基于基本網(wǎng)和高級(jí)網(wǎng)的，有基于網(wǎng)的靜態(tài)結(jié)構(gòu)和動(dòng)態(tài)行為的，也有基于形式化和非形式化的，還有基于網(wǎng)的靜態(tài)結(jié)構(gòu)的圖論觀點(diǎn)的,-64-,示例：Petri網(wǎng)的分層概念,與DFD分層相似。Petri網(wǎng)分層時(shí)，以作為分層的結(jié)點(diǎn)。不僅要保證父子層的I/O一致，還要保證它們的性質(zhì)不變（因?yàn)镻etri網(wǎng)主要用于并發(fā)系統(tǒng)的特性分析）,-65-,示例：基于網(wǎng)的靜態(tài)結(jié)構(gòu)的圖論觀點(diǎn),圖中p1和p2分別為子網(wǎng)G的輸入門和輸出門。t1和t

28、2則分別分子網(wǎng)G”的輸入門和輸出門。G是一個(gè)位置子網(wǎng)，G”是一個(gè)轉(zhuǎn)移子網(wǎng)。同時(shí)，它們的輸入度（輸入孤的數(shù)目）和輸出度（輸出弧的數(shù)目）均為1。有了這些概念就可以定義出如下化簡子網(wǎng)的條件： 1，構(gòu)成一條只有一個(gè)輸 入門和一個(gè)輸出門的直接路 經(jīng) 2，輸入門的輸入度和輸 出門的輸出度分別為1 只有這樣，才能保證原網(wǎng) 的特性（如活性、有界性等） 不變,-66-,Petri網(wǎng)的化簡,與分層一樣，是一種處理復(fù)雜問題的方法 化簡的基本原則 在保持所有要求的性質(zhì)不變的情況下，將多個(gè)不同位置或轉(zhuǎn)移抽象為單個(gè)位置和轉(zhuǎn)移 化簡的方法 折疊（將結(jié)點(diǎn)多的基本網(wǎng)轉(zhuǎn)換為結(jié)點(diǎn)少的高級(jí)網(wǎng)） 刪減（將冗余或等價(jià)例位置或轉(zhuǎn)移刪除或合

29、并）,-67-,Petri網(wǎng)的化簡：折疊-著色網(wǎng),這種方法是用顏色把標(biāo)記分開 示例,-68-,Petri網(wǎng)的化簡：折疊-謂詞/轉(zhuǎn)移網(wǎng),這種方法與著色網(wǎng)不同，它用字符串來表示標(biāo)記。然后，把轉(zhuǎn)移與謂詞（刻畫標(biāo)記的性質(zhì)）聯(lián)系起來，用來控制轉(zhuǎn)移是否可發(fā)生 示例,-69-,高級(jí)網(wǎng)到基本網(wǎng),高級(jí)網(wǎng)也可以展開為基本網(wǎng) 示例,-70-,Petri網(wǎng)的化簡：刪減,設(shè)（N,M）和（N,M）分別為化簡前后的網(wǎng)，運(yùn)用以下化簡規(guī)則，當(dāng)且僅當(dāng)（N,M）是活的、安全的和有界的，則（N,M）是活的、安全的和有界的 串行位置的合并 串行轉(zhuǎn)移的合并 并行位置的合并 并行轉(zhuǎn)移的合并 自循環(huán)位置的消除 自循環(huán)轉(zhuǎn)移的消除,-71-,串

30、行位置和轉(zhuǎn)移的合并,-72-,并行位置和轉(zhuǎn)移的合并,-73-,自循環(huán)位置和轉(zhuǎn)移的消除,-74-,刪減的示例,從圖（a）發(fā)生t2,移去p1中標(biāo)記,合并t1和t2為t12,合并t3和t4為t34,從而得出圖（b）所示的Petri網(wǎng)。從圖（b）中消去自循環(huán)轉(zhuǎn)移t12和自循環(huán)位置p3,又可得以得出圖（c ）所示的Petri網(wǎng)。所有這三個(gè)網(wǎng)都是有界 的,非活的和安全 的,并且都是不可 逆的,-75-,可覆蓋性（可達(dá)性）樹,可覆蓋性或可達(dá)性樹用標(biāo)識(shí)樹來實(shí)現(xiàn) 標(biāo)識(shí)樹的實(shí)現(xiàn) 利用一個(gè)給定的Petri網(wǎng)（N,M0），從M0開始可以得數(shù)量與可發(fā)生轉(zhuǎn)移一樣多的許多“新的”標(biāo)識(shí)。從各個(gè)新的標(biāo)識(shí)可以再到達(dá)更多的標(biāo)識(shí)?？?/p>

31、用標(biāo)識(shí)樹表示以上過程，以初始標(biāo)識(shí)M0作樹根，可由M0到達(dá)的標(biāo)識(shí)作樹的后繼結(jié)點(diǎn)。每條連接結(jié)點(diǎn)的弧表示一個(gè)轉(zhuǎn)移的發(fā)生，它將一個(gè)標(biāo)識(shí)變換到另一個(gè)標(biāo)識(shí) 標(biāo)識(shí)樹中的特殊符號(hào) 如果Petri網(wǎng)無界，則所構(gòu)造的標(biāo)識(shí)樹將生長為無限。如果Petri網(wǎng)有界，所構(gòu)造制標(biāo)識(shí)樹也可能為無限。另為了保持標(biāo)識(shí)樹的有限，我們引入一個(gè)特殊符號(hào)，可以把它想像為“無限”。 具有這樣的性質(zhì)： 對(duì)每個(gè)整數(shù)n： n， n= ， ,-76-,可覆蓋性（可達(dá)性）樹的構(gòu)造過程,1. 把初始標(biāo)識(shí)M0當(dāng)作根，并加上“新的”標(biāo)志； 2. 當(dāng)具有“新的”標(biāo)志的標(biāo)識(shí)存在時(shí)，重復(fù)以下步驟： （1）選擇一個(gè)“新的”標(biāo)識(shí)M； （2）如果M與從根到M 路徑上的

32、一個(gè)標(biāo)識(shí)相同，則對(duì)M 加上“老的” 標(biāo)志，然后轉(zhuǎn)向另一個(gè)“新的”標(biāo)識(shí)； （3）如果M 中沒有轉(zhuǎn)移可以啟動(dòng)，對(duì)M 加上“死的”標(biāo)志；為 （4）當(dāng)M 中存在有效的轉(zhuǎn)移時(shí)，對(duì)M 的每個(gè)轉(zhuǎn)移t 做以下各步： a，從M 發(fā)生t 的結(jié)果獲得標(biāo)識(shí)M b，若M（p）= ，則M（p）= c，在從根到M 的路徑上，如果存在一個(gè)標(biāo)識(shí)M”，使得每個(gè)位置p 存在 M（p） M（p）,并且M M,即M” 是可覆蓋的。那么，對(duì)其中滿足 M（p）M（p） 的每個(gè)位置p，用重置M（p） d. 引入M 作為樹的一個(gè)結(jié)點(diǎn)，從M 向M 畫用t 標(biāo)注的弧，并對(duì)M 加上 “新的”標(biāo)志。,-77-,從Petri網(wǎng)獲得可覆蓋性樹,-78-,

33、使用可覆蓋性樹可研究Petri網(wǎng)的特性（1）,對(duì)于一個(gè)Petri網(wǎng)（N, M0），且因此R（M0）是通過使用可覆蓋性樹可以研究以下特性 一個(gè)網(wǎng)（N, M0）是有界的，且因此R（M0）是有限的，當(dāng)且僅當(dāng)不會(huì)出現(xiàn)在可覆蓋性樹中的任一結(jié)點(diǎn)標(biāo)注中 一個(gè)網(wǎng)（N, M0）是安全的，當(dāng)且僅當(dāng)只有“0”和“1”出現(xiàn)在可覆蓋性樹的結(jié)點(diǎn)標(biāo)注中 一個(gè)轉(zhuǎn)移t 是死的，當(dāng)且僅當(dāng)t 不出現(xiàn)在可覆蓋性樹的任一弧的標(biāo)注中 如果M從M0可達(dá)，則存在一個(gè)標(biāo)注M的結(jié)點(diǎn)，使得M M,-79-,使用可覆蓋性樹可研究Petri網(wǎng)的特性（2）,對(duì)于一個(gè)有界的Petri網(wǎng)，其可覆蓋性樹被稱為可達(dá)性樹。這是因?yàn)樗ㄋ锌赡艿竭_(dá)的標(biāo)識(shí)。在這種

34、情況下，前面計(jì)討論的所有行為特性的分析問題都可以通過可達(dá)性樹來解決，這是一種窮舉法 但在通常情況下，由于使用符號(hào)會(huì)使一些信息丟失，所以可達(dá)性和活性問題不可能單單利用可覆蓋性樹方法來解決。我們可看下頁所示的兩個(gè)不同的Petri網(wǎng)，它們有相同的可覆蓋性樹。但其中一個(gè)是活的Petri網(wǎng)，而另一個(gè)不是活的，因?yàn)樵摼W(wǎng)在發(fā)生t1、t2和t3以后再也沒有可發(fā)生的轉(zhuǎn)移,-80-,使用可覆蓋性樹可研究Petri網(wǎng)的特性（3）,兩個(gè)不同的Petri網(wǎng) 一個(gè)活的Petri網(wǎng) 一個(gè)不活的Petri網(wǎng),-81-,使用可覆蓋性樹可研究Petri網(wǎng)的特性（4）,相同的可覆蓋性樹,-82-,使用可覆蓋性樹可研究Petri網(wǎng)的

35、特性（5）,不同的可達(dá)狀態(tài) 一個(gè)活的Petri網(wǎng) 一個(gè)不活的Petri網(wǎng),-83-,不變量、關(guān)聯(lián)矩陣和狀態(tài)方程,這一部分介紹的是完全用代數(shù)計(jì)算來對(duì)網(wǎng)系統(tǒng)進(jìn)行分析。 前邊介紹的可達(dá)集都是從網(wǎng)的整體行為來刻畫的。這里講不變量，整體中有許多不變量，這是局部行為。 不變量用關(guān)聯(lián)矩陣定義，它給出了系統(tǒng)的結(jié)構(gòu)。 根據(jù)關(guān)聯(lián)矩陣與網(wǎng)存在的一一對(duì)應(yīng)關(guān)系推出狀態(tài)方程。 最后就可用關(guān)聯(lián)矩陣和狀態(tài)方程計(jì)算出網(wǎng)的不變量和網(wǎng)的各種特性。,-84-,不變量（invariant）,網(wǎng)系統(tǒng)中有S-不變量和T-不變量 如果網(wǎng)系統(tǒng)中有一些位置，其中包含的資源（標(biāo)記）的總和在任何可達(dá)標(biāo)識(shí)情況下均為常數(shù)，即系統(tǒng)不論發(fā)生什么事件，這些位

36、置中的標(biāo)記總數(shù)不變，則這些位置就是系統(tǒng)的一個(gè)S-不變量。也就是說，S-不變量代表著網(wǎng)系統(tǒng)中若干個(gè)資源的流動(dòng)范圍 如果網(wǎng)系統(tǒng)中有一些轉(zhuǎn)移，它們的發(fā)生會(huì)使它們的標(biāo)識(shí)恢復(fù)到它們的開始狀態(tài)，則這些轉(zhuǎn)移就是系統(tǒng)的一個(gè)T-不變量,-85-,不變量-示例1,S-不變量和T-不變量一般采用向量表示，即以位置元素為序標(biāo)的列向量表示S -不變量，以轉(zhuǎn)移元素為序標(biāo)的列向量表示T-不變量 本網(wǎng)系統(tǒng)的不變量為： S-不變量 T-不變量,-86-,不變量-示例2,本網(wǎng)系統(tǒng)的不變量：,-87-,不變量-示例3,本網(wǎng)系統(tǒng)的不變量：,-88-,關(guān)聯(lián)矩陣（Incidence Matrix）（ 1）,正如網(wǎng)系統(tǒng)的標(biāo)識(shí)可以表示為一個(gè)

37、向量一樣，網(wǎng)結(jié)構(gòu)也可以用一個(gè)矩陣來表示。 設(shè)=（N,M0）,其中N=（P,T;F）是一個(gè)純網(wǎng)，其中P=p1, p2, pm，T=t1,t2,tn 用S-元素作為序標(biāo)的列向量V：PZ 稱為的S-向量，Z為正負(fù)數(shù)集合。其中，Z=2, 1,0,1,2, 為正負(fù)數(shù)集合 用T-元素作為序標(biāo)的列向量U： TZ 稱為的T-向量 用PT作為序標(biāo)的矩陣C： PTZ 稱為的關(guān)聯(lián)矩陣 其關(guān)聯(lián)矩陣元素C （pi,tj ）=W （tj,pi） W （pi,tj ）,-89-,關(guān)聯(lián)矩陣（2）,C （pi,tj ）=W （tj,pi） W （pi,tj ）也可寫成： Cijmn=Cijmn Cijmn 其中 Cij就是從轉(zhuǎn)

38、移j到它的輸出位置I的弧的權(quán)， Cij是抗持轉(zhuǎn)移的輸入伍卜位置I到轉(zhuǎn)移j的弧的權(quán)。從轉(zhuǎn)移規(guī)則很容易看出， Cij、 Cij和Cij 分別表示當(dāng)轉(zhuǎn)移j一旦發(fā)生，位置i中標(biāo)記取走、增加和改變的數(shù)量。,-90-,關(guān)聯(lián)矩陣（3）,關(guān)聯(lián)矩陣一般表示形式 其中Cij表一下示取走、增加后產(chǎn)生的變化數(shù)。此關(guān)聯(lián)矩陣給出了系統(tǒng)的結(jié)構(gòu),-91-,狀態(tài)方程,如果N=（P,T;F）是純網(wǎng)，則C與N存在一一對(duì)應(yīng)關(guān)系。在此，我們用m維列向量來表示標(biāo)識(shí)M，即M=M（p1）,M（p2）, ,M（pm）T。這樣，Mtj的充分必要條件為： i1,2, m：CijM （i） 或?qū)懗桑?C*j M 其中C*j表示矩陣Cij 的第j列。

39、 如果M1tj M2，則有M2=M1+ C*j。若M0 M，就可以推出狀態(tài)方程為： M= M0+CU 其中CU是矩陣乘法，是的轉(zhuǎn)移序列，U是的T-向量表示，它以tj為序標(biāo)的分量值為tj在中出現(xiàn)的次數(shù)，即U（tj）=#（tj/ ），M0是的初始標(biāo)識(shí)的S-向量表示，由導(dǎo)出的可達(dá)標(biāo)識(shí)M也表示為S-向量形式。,-92-,用關(guān)聯(lián)矩陣和狀態(tài)方程求不變量,設(shè)I是的S-不變量，M M0 ，則 ITM=ITM0 設(shè)是從M0到M的轉(zhuǎn)移序列：M0 M，于是 M0+CT U=M， 其中U是對(duì)應(yīng)于的T-向量，對(duì)所有tj T，U（tj）是tj在 中出現(xiàn)的次數(shù)。兩邊同時(shí)乘以IT，則得 IT M0一+IT CT U=IT M

40、,-93-,狀態(tài)方程在可達(dá)性分析中的應(yīng)用（1）,狀態(tài)方程M = M0+CT U為部分解決可達(dá)性問題提供了一個(gè)依據(jù)。若Md 從 M0可達(dá)則方程CT U = Md M0 =M必然存在一個(gè)非負(fù)整數(shù)解Ux，該解即為發(fā)生的計(jì)數(shù)向量。若無這樣的解，Md 就不繼從M0到達(dá)。 示例1,-94-,狀態(tài)方程在可達(dá)性分析中的應(yīng)用（2）,示例1（續(xù)） 在所示的Petri網(wǎng)中： 在狀態(tài)M0下轉(zhuǎn)移t3是可發(fā)生的。設(shè)M1是發(fā)生t3所得的標(biāo)識(shí)，則有,-95-,狀態(tài)方程在可達(dá)性分析中的應(yīng)用（3）,示例1（續(xù)） 發(fā)生序列=t3 t2 t3 t2 t1表示成發(fā)生計(jì)數(shù)向量（1,2,2），發(fā)生后產(chǎn)生的新標(biāo)識(shí)為,-96-,狀態(tài)方程在可達(dá)

41、性分析中的應(yīng)用（4）,示例1（續(xù)） 考察標(biāo)識(shí) ，它可以從標(biāo)識(shí)M0到達(dá)方程為 有一個(gè)解U=（0,4,5），它對(duì)應(yīng)于發(fā)生序列=t3 t2 t3 t2 t3 t2 t3 t2 t3,-97-,狀態(tài)方程在可達(dá)性分析中的應(yīng)用（5）,再考察后標(biāo)識(shí) ，因方程 無解，所以標(biāo)識(shí) 為不可達(dá)標(biāo)識(shí),-98-,狀態(tài)方程在可達(dá)性分析中的應(yīng)用（6）,注意，狀態(tài)方程有解只是可達(dá)性的必要條件，而不是充分條件。這是由于缺少M(fèi) 初始標(biāo)識(shí)信息導(dǎo)致的 示例2 考察所示的Petri網(wǎng),-99-,狀態(tài)方程在可達(dá)性分析中的應(yīng)用（7）,示例2（續(xù)） 在所示的Petri網(wǎng)中 方程,-100-,狀態(tài)方程在可達(dá)性分析中的應(yīng)用（8）,示例2（續(xù)） 有

42、一個(gè)解U = 。這個(gè)解對(duì)應(yīng)的兩個(gè)可能發(fā)生序列為t1 t2或t2 t1，然而這兩個(gè)序列都不是可發(fā)生序列。因?yàn)樵贛0下，t1、t2都不可能發(fā)生。這里 若取初始標(biāo)識(shí)為 則為可達(dá)的，且對(duì)應(yīng)于發(fā)生計(jì)數(shù)向量 的發(fā)生序列為t1t2,-101-,關(guān)聯(lián)矩陣和狀態(tài)方程在其他特性方面的應(yīng)用（1）,結(jié)構(gòu)有界性 N=（P,T；F）稱為結(jié)構(gòu)有界，是指對(duì)任何初始標(biāo)識(shí)M0，（N,M0）都是有界的。可以證明，網(wǎng)N 結(jié)構(gòu)有界的充分必要條件是存在m 維正整數(shù)向量V，使得CTV0 守恒性 如果存在P上的一個(gè)正整數(shù)函數(shù)V，使得對(duì)任何初始標(biāo)識(shí)M0和任何MR （M0），M （i ）V （i ）為一固定值，則稱N為守恒的。可以證明，網(wǎng)N守恒

43、的充分必要條件是存在m 維正整數(shù)向量V，使得CT V=0 可重復(fù)性 如果在存在初始標(biāo)識(shí)M0，在（N,M0）中存在無限轉(zhuǎn)移序列，使得M0，而且每個(gè)轉(zhuǎn)移tj 都在 中出現(xiàn)無限多次，則稱網(wǎng)N為可重復(fù)的。可以證明，網(wǎng)N可充分必要條件是存在n 維正整數(shù)向量U，使得C U0,-102-,關(guān)聯(lián)矩陣和狀態(tài)方程在其他特性方面的應(yīng)用（2）,相容性 如果存在初始標(biāo)識(shí) M0，在（N,M0）中存在無限轉(zhuǎn)移序列，使得M0 M0，而且tj T，# （tj /） 1，則稱網(wǎng)N為可相容的。可以證明，網(wǎng)N 為相容的充分必要條件是存在n 維正整數(shù)向量U，使得C U = 0 結(jié)構(gòu)公平性 如果對(duì)任何初始標(biāo)識(shí)M0，在（N,M0）中都是公

44、平網(wǎng)，則稱網(wǎng)N為公平網(wǎng)。 可以證明，網(wǎng)N 為公平網(wǎng)的充分必要條件是對(duì)任意n 維非負(fù)整數(shù)向量U：C U 0 i 1,2, , m：U （i） 0，而且若有U1和U2 滿足C U 1 0 和 C U 2 0 ，則U 1和U 2 線性相關(guān),-103-,關(guān)聯(lián)矩陣和狀態(tài)方程在其他特性方面的應(yīng)用（3）,示例 本例所示的網(wǎng)（N,M0），它的位置集S和轉(zhuǎn)移集T各有4個(gè)元素，流關(guān)系如圖所示，初始標(biāo)識(shí)M0=1,0,0,0。對(duì)這樣的網(wǎng)（N,M0），可以寫出它的關(guān)聯(lián)矩陣和狀態(tài)方程,-104-,關(guān)聯(lián)矩陣和狀態(tài)方程在其他特性方面的應(yīng)用（4）,由于M0C*2，所以t2可以發(fā)生。設(shè)M0t2M1，則 如沒=t2t1t2t1t2

45、t4在M0可以發(fā)生，記M0M2，則可計(jì)算出M2為,-105-,關(guān)聯(lián)矩陣和狀態(tài)方程在其他特性方面的應(yīng)用（5）,本例容易證明，存在U1= 使得CU1=0。所以網(wǎng)N是相容的，也是可重復(fù) 的。但不存在四維正整數(shù)向量V，使得CTV0。所以網(wǎng)N不是結(jié)構(gòu)有界的 對(duì)于任意非負(fù)整數(shù)kV=k 都滿足CTV=0。何所以k 是N 的一個(gè)S-不 變量，從而S1,S2,S4是N 的S-不變量的支集。 同理，N 的T-不變量額廣都有k 的形式，也即轉(zhuǎn)移集T本身是N 的T-不變量的支集 由于存在U2= ，使得CU2= ，而U2中含有零分量。所以N不是公平,-106-,改進(jìn)Petri網(wǎng)及其應(yīng)用,什么是改進(jìn)Petri網(wǎng) 改進(jìn)Pe

46、tri網(wǎng)指的是謂詞/轉(zhuǎn)移網(wǎng)和著色網(wǎng)。它們由基本網(wǎng)改進(jìn)而來，故稱它們?yōu)楦倪M(jìn)Petri網(wǎng)。有的稱它們?yōu)樽冃尉W(wǎng)，還有的稱它們?yōu)楦呒?jí)網(wǎng) 既然有了上面討論的基本網(wǎng)，為什么還要高級(jí)網(wǎng) 這是因?yàn)樵趯?shí)際應(yīng)用中，一個(gè)稍復(fù)雜的網(wǎng)系統(tǒng)就會(huì)使用大量的位置和轉(zhuǎn)移，由此引起狀態(tài)組合爆炸問題，使Petri網(wǎng)難以理解和分析。有人甚至認(rèn)為在狀態(tài)（可達(dá)集）組合爆炸這一基本問題未獲解決或有可能避免之前，Petri網(wǎng)建模不可能出現(xiàn)實(shí)質(zhì)性的成功或突破。所以還要介紹高級(jí)網(wǎng)。 高級(jí)網(wǎng)系統(tǒng)如何構(gòu)造 高級(jí)網(wǎng)系統(tǒng)如何構(gòu)造，一般都從應(yīng)用的問題的P/T網(wǎng)系統(tǒng)模型著手，經(jīng)折疊而成。所以，我們就應(yīng)該先弄清什么是P/T網(wǎng)系統(tǒng)的折疊，然后介紹折疊的高級(jí)網(wǎng)系

47、統(tǒng)的定義 什么是折疊 折疊就是采用抽象的方法，把具有同類邏輯功能制的位置和轉(zhuǎn)移進(jìn)行合并，這樣就可以大大減少位置和轉(zhuǎn)移的數(shù)量，將結(jié)點(diǎn)多的P/T網(wǎng)系統(tǒng)轉(zhuǎn)換為結(jié)點(diǎn)較少的高級(jí)網(wǎng)系統(tǒng),-107-,謂詞/轉(zhuǎn)移網(wǎng),謂詞/轉(zhuǎn)移網(wǎng)（Predicate/Transition nets, Pr/T網(wǎng)） Pr/T網(wǎng)的轉(zhuǎn)移發(fā)生條件和引起的標(biāo)識(shí)變化是通過刻畫標(biāo)記性質(zhì)的謂詞來解釋的 示例：一個(gè)機(jī)械制造車間零件加工的簡化Pr/T網(wǎng)系統(tǒng)模型,-108-,一個(gè)機(jī)械制造車間零件加工的簡化Pr/T網(wǎng)系統(tǒng)模型（1）,1,問題描述 有一名工人分別在機(jī)床甲和機(jī)床乙上加工零件。先加工完的機(jī)床要等待另一臺(tái)機(jī)床加工完后，零件經(jīng)裝配才能卸下。然后

48、，機(jī)床轉(zhuǎn)入空閑，再進(jìn)入就緒。以上加工過程重復(fù)進(jìn)行 為簡化問題，這里只考慮工人和機(jī)床的關(guān)系。其他如原材料來源、成品的去處，以及輔助工具（刀、量等）等一概不考慮,-109-,一個(gè)機(jī)械制造車間零件加工的簡化Pr/T網(wǎng)系統(tǒng)模型（2）,2,P/T網(wǎng)系統(tǒng)模型,-110-,一個(gè)機(jī)械制造車間零件加工的簡化Pr/T網(wǎng)系統(tǒng)模型（3）,3,先分析位置 從上可知：本系統(tǒng)中有3 個(gè)個(gè)體：工人、機(jī)床甲作和機(jī)床乙，用w、a、b來表示 這3 個(gè)個(gè)體可能處于4 種狀態(tài)：就緒（ready）、工作（working）、等待（waiting）和休息（resting） 工作必須是w和a或w和b的結(jié)合，為了強(qiáng)調(diào)結(jié)合用joint（結(jié)合）表示

49、working 如果用P-元素表示4個(gè)狀態(tài)，用w、a、b三個(gè)個(gè)體名代替沒有個(gè)性的標(biāo)記。就可把邏輯功能相同的位置（狀態(tài)）折疊在一起 這樣位置由10個(gè)減少為4個(gè),-111-,一個(gè)機(jī)械制造車間零件加工的簡化Pr/T網(wǎng)系統(tǒng)模型（4）,邏輯功能相同的位置折疊在一起的圖形表示,-112-,一個(gè)機(jī)械制造車間零件加工的簡化Pr/T網(wǎng)系統(tǒng)模型（5）,在位置折疊的圖中可見 它保留了P/T網(wǎng)系統(tǒng)中的全部有向孤和所有轉(zhuǎn)移。有向張上旅弧上標(biāo)注了孤上流動(dòng)的個(gè)體或由個(gè)體結(jié)合而成的偶如w,a或w,b P-元素（位置）已不是原P/T網(wǎng)系統(tǒng)中的位置，而是其中個(gè)體當(dāng)前的狀態(tài)，即謂詞。謂詞中的標(biāo)識(shí)也不是非負(fù)整數(shù)，而是由個(gè)體組成的集合

50、。如P1中初始標(biāo)識(shí)有3個(gè)個(gè)體，表明w、a、b都處于就緒狀態(tài)。P2、P3和P4在初始標(biāo)識(shí)下，均無個(gè)體，為空集。由此可見，引進(jìn)謂詞后，減少了P （位置）的個(gè)數(shù),-113-,一個(gè)機(jī)械制造車間零件加工的簡化Pr/T網(wǎng)系統(tǒng)模型（4）,4,再分析轉(zhuǎn)移 很明顯，由上圖可見：轉(zhuǎn)移也可分為4類：結(jié)合（joint）（開始工作）=t1,t2、完成（finish）（工作完成）=t3,t4、裝配（assemble）=t5和準(zhǔn)備（to-ready）=t6,t7,t8 由上圖還可見：同類轉(zhuǎn)移有相同的前集和后集，t1與t2、t3與t4，以及t6、t7和t8之間的區(qū)別在于參與轉(zhuǎn)移的個(gè)體不同。如果我們用變量x來代替?zhèn)€體名，則可把

51、同類轉(zhuǎn)移也合并為一個(gè)。這就可以得到合并轉(zhuǎn)移后的網(wǎng)系統(tǒng),-114-,一個(gè)機(jī)械制造車間零件加工的簡化Pr/T網(wǎng)系統(tǒng)模型（5）,合并轉(zhuǎn)移后得到的網(wǎng)系統(tǒng),-115-,一個(gè)機(jī)械制造車間零件加工的簡化Pr/T網(wǎng)系統(tǒng)模型（6）,在轉(zhuǎn)移折疊的圖中可見 把P、T 兩個(gè)元素間的多條有向弧合并為一條，弧上標(biāo)注也用“+”號(hào)連在一起。如P1與t1、t2之間的兩條弧合并為一條后，弧上記為w+x，x表示P1中的任何一個(gè)個(gè)體。為統(tǒng)一符號(hào)，w,a和w,b可改寫為w,x。用尖括號(hào)及“+”號(hào)連在一起的表達(dá)式為符號(hào)和 必須指出，w+x是兩個(gè)獨(dú)立的個(gè)體，w,x是兩個(gè)結(jié)合在一起的個(gè)體 新轉(zhuǎn)移joint、finish、assemble和t

52、o-ready分別代表系統(tǒng)中的同一類轉(zhuǎn)移 當(dāng)從P1到j(luò)oint的弧上標(biāo)注w+x中的變量x取個(gè)體a為值時(shí)，轉(zhuǎn)移joint發(fā)生就是原系統(tǒng)中t1的發(fā)生。當(dāng)x以b為值時(shí)，joint發(fā)生不是t1，而是t2。但x不能以w為值 圖中只使用了一個(gè)變量名x，但x并非表示同一個(gè)變量。事實(shí)上，只有同一個(gè)轉(zhuǎn)移的所有I/O弧上的變量才是同一個(gè)變量，它必須取同一個(gè)個(gè)體為值。由此可見，引進(jìn)變量后減少了T-元素的個(gè)數(shù),-116-,一個(gè)機(jī)械制造車間零件加工的簡化Pr/T網(wǎng)系統(tǒng)模型（7）,5,Pr/T網(wǎng)系統(tǒng)的轉(zhuǎn)移規(guī)則 Pr/T網(wǎng)系統(tǒng)的標(biāo)識(shí)為系統(tǒng)中每個(gè)謂詞指明了其外延。在轉(zhuǎn)移的折疊圖中P1的外延為|a，b，w |，寫成符號(hào)和為+。

53、而P2、P3和P4的外延均為空集合。轉(zhuǎn)移joint前后的變量x可以分別以a和b值發(fā)生，發(fā)生的兩次轉(zhuǎn)移分別記為joint（xa）和joint（xa），而x a 和xb稱為轉(zhuǎn)移joint的可行替換，即以a替換x和以b替換x。這肘轉(zhuǎn)移才有發(fā)生權(quán)和發(fā)生權(quán)的后繼。對(duì)joint而言，x w不是可行替換，joint（x w ）在初始標(biāo)下沒有發(fā)生權(quán)。所以Pr/T網(wǎng)系統(tǒng)不能離開變量替換來討論 joint （xa）發(fā)生偽一的后果是化從P1中拿走個(gè)體a和w，在P2中加上a和w的結(jié)合，這些都是由joint的I/O弧上的標(biāo)注和替換xa計(jì)算出來的。joint （xa）發(fā)生后的后繼M1為M1（P1）=，M1（P2）=|，M

54、1（P3）=M1（P4）=null，即空符號(hào)和 按上述規(guī)則，可以給出轉(zhuǎn)移折疊圖的Pr/T網(wǎng)系統(tǒng)中一些可能替換及相應(yīng)的謂詞外延的變化如下頁列表所示,-117-,一個(gè)機(jī)械制造車間零件加工的簡化Pr/T網(wǎng)系統(tǒng)模型（8）,Pr/T網(wǎng)系統(tǒng)的轉(zhuǎn)移規(guī)則（續(xù)） 謂詞外延的變化 表中謂詞外延以集合形式給出以便比較集合的形式與符號(hào)和的對(duì) 應(yīng)關(guān)系,-118-,一個(gè)機(jī)械制造車間零件加工的簡化Pr/T網(wǎng)系統(tǒng)模型（9）,6,Pr/T網(wǎng)系統(tǒng)的定義 =（P,T；F,D,V,A,M0） 其中 （P,T；F）為有向網(wǎng)，即的基網(wǎng) D 為非空有限集，即的個(gè)體集（標(biāo)記的分類） V 為D上的變量集 A 為有向集F上的可變謂詞集（這些謂詞

55、是以V 的元素為變?cè)倪壿嬍交虼鷶?shù)式） M0 為狀態(tài)的初始標(biāo)識(shí) 說明 定義中沒有明確給出的兩點(diǎn)要求是：M0 必須是D 在謂詞集P上的一個(gè)分布，而每個(gè)轉(zhuǎn)移tT 必須是個(gè)體守恒的。轉(zhuǎn)移t 的個(gè)體字恒表現(xiàn)在，即出現(xiàn)在它的輸入弧上的個(gè)體必須也出現(xiàn)在它的輸出弧上。反之亦然。出現(xiàn)的形式可以不同,-119-,一個(gè)機(jī)械制造車間零件加工的簡化Pr/T網(wǎng)系統(tǒng)模型（10）,7,Pr/T網(wǎng)系統(tǒng)的行為 與P/T網(wǎng)系統(tǒng)相同點(diǎn) 謂詞/轉(zhuǎn)移網(wǎng)和著色網(wǎng)實(shí)質(zhì)上都是P/T網(wǎng)系統(tǒng)為與折疊和擴(kuò)充行為上自然類似順序并發(fā)和沖突等基本現(xiàn)象都可以得到嚴(yán)格的描述。所以，分析P/T網(wǎng)系統(tǒng)行為的方法都可以用來分析Pr/T網(wǎng)系統(tǒng)和著色網(wǎng)系統(tǒng) 與P/T

56、網(wǎng)系統(tǒng)不同點(diǎn) 因?yàn)镻r/T網(wǎng)系統(tǒng)中的標(biāo)識(shí)都是一種個(gè)體的分布，而且每個(gè)轉(zhuǎn)移都是個(gè)體守恒的，所以Pr/T網(wǎng)中不會(huì)有沖突 另外，謂詞只是個(gè)體狀態(tài)的一種描述，所以P（位置）元素應(yīng)該沒有容量限制。因而一般不會(huì)發(fā)生碰撞 也可以使用P/T網(wǎng)系統(tǒng)構(gòu)造可達(dá)樹的方法,對(duì)Pr/T網(wǎng)系統(tǒng)進(jìn)行分析。但Pr/T網(wǎng)系統(tǒng)的可達(dá)樹的結(jié)點(diǎn)標(biāo)識(shí)中不會(huì)出現(xiàn)“”。因?yàn)镻r/T網(wǎng)系統(tǒng)中每個(gè)標(biāo)識(shí)都是個(gè)體集中的一種個(gè)體分布，而有限個(gè)個(gè)體在有限個(gè)謂詞中的分布一共只有有限種，所以Pr/T網(wǎng)系統(tǒng)的可達(dá)樹也是有限的,-120-,著色網(wǎng)（colored nets）,著色網(wǎng)通過顏色區(qū)分標(biāo)記，通過增加位置的顏色集和轉(zhuǎn)移出現(xiàn)的顏色集，以及轉(zhuǎn)移的I/O函數(shù)來

57、刻畫解釋 1,定義 =（P,T;F,C,I-,I+,M0） 其中 （P,T；F）分廣為有向網(wǎng)，即的基網(wǎng) C為顏色集合，并有 對(duì)p P,C （p）是位置p上所有可能標(biāo)記顏色非空有限集合 對(duì)t T,C （t）是轉(zhuǎn)移t 上所有可能出現(xiàn)的顏色非空有限集合 I-和I+分別為PT 和TP上的負(fù)函數(shù)和正函數(shù) p P, t T I-（p,t） 0 I+（t,p） 0 t T, p P I-（p,t） 0 I+（t,p） 0 M0為的初始標(biāo)識(shí),-121-,2,著色網(wǎng)系統(tǒng)定義中的符號(hào)含義（1）,這里仍使用Pr/T網(wǎng)系統(tǒng)的示例說明 （1）C（顏色集合） 系統(tǒng)有3個(gè)個(gè)體（a,b,w）和4種狀態(tài)（就緒、工作、等待和休息

58、），這樣就可以給出位置p上的所有可能的標(biāo)記顏色集合 C（p1）=, C（p2）=a,b C（p3）=a,b,w 同樣系統(tǒng)中的轉(zhuǎn)移也有4類（結(jié)合、完成、裝配和推產(chǎn)準(zhǔn)備），這樣也就可以給出所有可以出現(xiàn)的顏色集合 C（joint）=, C（finish）=, C（assemble）= C（to-ready）=,-122-,2,著色網(wǎng)系統(tǒng)定義中的符號(hào)含義（2）,這里仍使用Pr/T網(wǎng)系統(tǒng)的示例說明（續(xù)） （2） I-和I+（PT和TP上的負(fù)函數(shù)和正函數(shù)） 只有上面顏色說明還不夠，還應(yīng)當(dāng)說明轉(zhuǎn)移發(fā)生時(shí)其I/O位置中標(biāo)記的變化 I-（joint,p1,）=1 I-（joint,p1,）=1 I+（joint ,p2,）=1 I+（joint,p2,）=1 I- （finish,p2,）=1 I -（finish,p2,）=1 I+（finish,p3,a）=1 I+（finish,p4,w ）=1 I+（finish,p3,b）=1 I+（finish,p4,w ）=1 I-（assemble,p3,）=1 I+（assemble,p4,）=1 I-（to-ready,p4,）=1 I+（to-eady,p1,）=1 這樣，著色網(wǎng)系統(tǒng)表示的語義就非常清楚了 從中還可發(fā)現(xiàn)a、b也為