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

2、=t1, t2, t3, t4 F1=(p1, t1),(t1, p2), ,網(wǎng)與網(wǎng)系統(tǒng),定義1.1. 三元組N=(P,T;F)稱作網(wǎng)當(dāng)且僅當(dāng)： （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表示庫(kù)所（Place）集合 T表示變遷（Transition）集合 F是網(wǎng)的流關(guān)系（Flow）,網(wǎng)與網(wǎng)系統(tǒng),定義1.2. 設(shè)N=(P,T;F)為一個(gè)網(wǎng)，對(duì) xPT，令 x = y | yPT (y, x)F x = y | yP

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

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

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

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

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

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

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