部分Petri網的基本概念.ppt

1、第一部分 Petri網的基本概念,提綱,網與網系統(tǒng) 庫所/變遷系統(tǒng)與加權Petri網 并發(fā)與沖突,網與網系統(tǒng),Petri網是一種網狀信息流模型，包括庫所和變遷兩類節(jié)點，同時在庫所集上添加表示狀態(tài)信息的托肯分布（標識） 庫所表示條件、資源、等待隊列和信道等 變遷表示事件、動作、語句執(zhí)行和消息發(fā)送/接受等 一個變遷（事件）有一定數量的輸入和輸出庫所，分別代表事件的前置條件和后置條件 庫所中的托肯代表可以使用的資源數量或數據 Petri網按引發(fā)規(guī)則使得事件驅動狀態(tài)的演變，從而反映系統(tǒng)動態(tài)運行過程,網與網系統(tǒng),例：網N1=(P1,T1; F1)，其中 P1 = p1, p2, c1, c2, B T1

2、=t1, t2, t3, t4 F1=(p1, t1),(t1, p2), ,網與網系統(tǒng),定義1.1. 三元組N=(P,T;F)稱作網當且僅當： （1） PT, PT=; （2） F(PT)(TP); （3）dom(F)cod(F)=PT 其中， dom(F)=x PT | yPT: (x, y) F cod(F) =x PT | yPT: (y, x) F 這里， P表示庫所（Place）集合 T表示變遷（Transition）集合 F是網的流關系（Flow）,網與網系統(tǒng),定義1.2. 設N=(P,T;F)為一個網，對 xPT，令 x = y | yPT (y, x)F x = y | yP

3、T (x, y)F 稱x為x的前集或輸入集， x為x的后集或輸出集。稱x x 為元素x的外延。,一個庫所的外延是變遷集T的一個子集 一個變遷的外延是庫所集P的一個子集,網與網系統(tǒng),例：網N1=(P1,T1;F1)，其中 t2 = p2 t2 = p1, B,網與網系統(tǒng),定義1.3. 設N=(P,T;F)為一個網 （1）若對 xPT， x x =，則稱N為一個純網（pure net）。 （2）若對 x, yPT，(x= y)(x =y ) x=y，則稱N為一個簡單網（simple net）。 （3）若 pP，|p|=|p|=1，則稱N為一個T-圖（T-Graph）或標識圖（marked grap

4、h）。 （4）若 tT，|t|=|t|=1，則稱N為一個S-圖（S-Graph）或狀態(tài)機（state machine）。 （5）若t1,t2 T (t1 t2), t1 t2 |t1|=|t2|=1，則稱N為一個自由選擇網（free-choice net）。 （6）若t1,t2 T (t1 t2), t1 t2 t1=t2，則稱N為一個擴充的自由選擇網（extended free-choice net）。,網與網系統(tǒng),定義1.4. 四元組PN=(P,T;F,M0)稱作Petri網（網系統(tǒng)）當且僅當 （1） N=(P,T;F)為一個網； （2）映射M:P 0,1,2,(非負整數集)稱為網N的一個

5、標識，其中，M0是初始標識； （3）引發(fā)規(guī)則： （3.1）變遷t T稱為使能的當且僅當： p t：M(p)1，記作Mt; （3.2）在M下使能的變遷t可以引發(fā)，引發(fā)后得到一個新的標識M，記作MtM,對pP，有,網與網系統(tǒng),p1,p2,t1,t2,c1,c2,t3,t4,B,一個網系統(tǒng)的全部可能的運行情況由它的基網N和初始標識M0完全確定。 因此，給出了基網和初始標識，也就唯一確定了一個網系統(tǒng),M01=1,0,0,M02=0,1,0,提綱,網與網系統(tǒng) 庫所/變遷系統(tǒng)與加權Petri網 并發(fā)與沖突,庫所/變遷系統(tǒng)與加權Petri網,庫所/變遷系統(tǒng)（簡稱P/T系統(tǒng)）是在定義1.4的Petri網基礎上

6、增加兩個函數得到的 庫所集上的容量函數 有向邊上的權函數 增加這兩個函數的目的是使得對某些實際系統(tǒng)建模顯得方便,庫所/變遷系統(tǒng)與加權Petri網,定義1.5. 六元組=(P,T;F,K,W,M0)稱作一個庫所/變遷網系統(tǒng)，其中 （1） N=(P,T;F)為一個網； （2） W: F 1,2,(正整數集)稱為權函數； （3） K: P 1,2,(正整數集)稱為容量函數； （4） M: P 0,1,2,是一個標識，滿足p P：M(p)K(p)其中，M0是初始標識； （5）引發(fā)規(guī)則： （5.1）對于t T，Mt的引發(fā)條件 （5.2）若MtM,對pP，有,t,H2,O2,2,2,例：化學反應的P/T系

7、統(tǒng),H2O,庫所/變遷系統(tǒng)與加權Petri網,定義1.4的Petri網,P/T系統(tǒng),t2無法引發(fā),庫所/變遷系統(tǒng)與加權Petri網,對于一個庫所/變遷系統(tǒng)=(P,T;F,K,W,M0)，若規(guī)定 p P：K(p)= f F：W(f)=1 那么，就變成形如定義1.4給出的網系統(tǒng)（原型Petri網） 對于一個P/T系統(tǒng)，如果規(guī)定各個庫所的容量都為無窮大，即取消庫所集上的容量函數而保留有向邊集上的權函數，就得到一種介于原型Petri網和P/T系統(tǒng)之間的網系統(tǒng)模型=(P,T;F,W,M0)，稱這種模型為加權Petri網（weighted Petri net） P/T系統(tǒng)并不比原型Petri網具有更強的模

8、擬能力，凡是可以用P/T系統(tǒng)對其建模的實際系統(tǒng)，也可以用原型Petri網對其建模。每一個P/T系統(tǒng)都可以轉換為一個行為等效的Petri網,庫所/變遷系統(tǒng)與加權Petri網,提綱,網與網系統(tǒng) 庫所/變遷系統(tǒng)與加權Petri網 并發(fā)與沖突,并發(fā)與沖突,定義1.6. 設PN=(P,T;F,M0)是一個Petri網， t1和t2是PN中的兩個變遷。如果PN的一個標識M使得Mt1且Mt2，那么若 Mt1M1 M1 t2 且 Mt2M2 M2 t1 則稱t1和t2在M并發(fā)，記為Mt1 , t2 。,如果兩個事件（變遷）在某狀態(tài)下都有發(fā)生權，而且其中任何一個的發(fā)生 都不會使另一個失去發(fā)生權，則稱這兩個事件在

9、該狀態(tài)下處于并發(fā) 并發(fā)不能簡單地理解為“同時發(fā)生”，而是指事件之間因果上的無依賴性。 按網論的觀點，事件的發(fā)生只依賴于它們的外延，而與全局情況無關,并發(fā)與沖突,定義1.7. 設PN=(P,T;F,M0)是一個Petri網， t1和t2是PN中的兩個變遷。如果PN的一個標識M使得 （1）Mt1 但 Mt2 ； （2）Mt1M1 M1 t2 則稱t1和t2存在順序關系。,并發(fā)與沖突,定義1.8. 設PN=(P,T;F,M0)是一個Petri網， t1和t2是PN中的兩個變遷。如果PN的一個標識M使得Mt1且Mt2，那么若 Mt1M1 M1 t2 且 Mt2M2 M2 t1 則稱t1和t2在M沖突。,沖突關系描述了系統(tǒng)的非確定性：在某情況下有兩個（或多個）事件都有權發(fā)生，但在實際運行過程中，只有一個能真正發(fā)生。系統(tǒng)存在沖突之處，正是外界環(huán)境可以對其施加控制（加以選擇）之處。,并發(fā)與沖突,t3和t4并發(fā),t1和t2沖突,并發(fā)和沖突的示例,控制裝置,t1和t2不是沖突，而是并發(fā)關系,并發(fā)與沖突,混惑的示例,存在混惑的網系統(tǒng)不是好的系統(tǒng)模型，因為在這種網系統(tǒng)的運行中，沖突是