測試人員的數(shù)學(xué)背景

2.測試人員的數(shù)學(xué)背景課程內(nèi)容離散數(shù)學(xué)圖論測試人員的離散數(shù)學(xué)離散數(shù)學(xué)包括：集合論、函數(shù)、關(guān)系、命題邏輯和概率論。集合論關(guān)于集合，是它使我們能夠作為一個(gè)單位，或一個(gè)整體引用多個(gè)事物。例如，我們可能要引用正好有30天的月份。采用集合論表示法可以寫為：

M1={4月，6月，9月，11月)集合成員關(guān)系集合中的項(xiàng)叫做集合的元素或成員，這種關(guān)系采用符號(hào)∈表示。這樣我們可以有4月∈M1。如果事物不是集合成員，則使用符號(hào)表示，可以有12月M1集合的定義集合有三種方式定義：簡單列出集合的元素；

Y={1812，1813，1814，…

…，2011，2012}

給出辨別規(guī)則；

Y={年：1812≤年≤2012}

決策規(guī)則定義集合必須是無歧義的。

N={t：t是近似三角形}

決策規(guī)則定義可以解決集合元素很難列出的集合。

S={銷售：15%的傭金率適用于該銷售額}

通過其他集合構(gòu)建；

空集采用符號(hào)表示，在集合論中占有特殊位置。空集不包含元素。

如果集合被決策規(guī)則定義為永遠(yuǎn)失敗，那么該集合就是空集。例如，

={年：2012≤年≤1812}空集維恩圖在維恩圖中，集合被表示為一個(gè)圓圈，圓圈中的點(diǎn)表示集合元素。

4月

11月

9月

6月U有30天的月份集合的維恩圖集合操作集合基本操作：并、交和補(bǔ)。其他便利的操作：相對(duì)補(bǔ)、對(duì)稱差和笛卡爾積。

集合操作定義假設(shè)某個(gè)論域空間U包含兩個(gè)集合A和B。定義使用來自謂詞演算的邏輯連接符，與(∧)、或(∨)、異或(⊕)和非(﹁)。定義給定集合A和B，其并是集合A∪B={x：x∈A∨x∈B}。其交是集合A∩B={x：x∈A∧x∈B}。

A的補(bǔ)是集合A’={x：xA}。

B針對(duì)A的相對(duì)補(bǔ)是集合A-B={x：x∈A∧xB}。

A和B的對(duì)稱差是集合A⊕B={x：x∈A⊕x∈B}。基本集合的維恩圖笛卡兒積

笛卡兒積取決于有序?qū)ε嫉母拍?，即兩個(gè)元素集合中的元素順序是重要的。無序和有序?qū)ε嫉谋硎痉ㄒ话闶牵簾o序?qū)ε迹?a，b)

有序?qū)ε迹?lt;a，b>

兩者的差別是，對(duì)于a≠b，

(a，b)=(b，a)，但是

<a，b>≠<b，a>

笛卡兒積的定義定義兩個(gè)集合A和B的笛卡兒積，是集合

A×B={<x，y>：x∈A∧y∈B}

舉例：集合A：(1，2，3)和B：<w，x，y，z)的笛卡兒積是集合：

A×B={<1,w>,<1,x>,<l,y>,<1，z>,<2,w>,<2,x>,<2,y>,<2,z>,<3，w>，<3，x>，<3，y>，<3,z>}

集合的勢集合A的勢是A中的元素?cái)?shù)，采用表示。對(duì)于集合A和B，=×AA×BAB集合關(guān)系定義

A是B的子集，記做AB，當(dāng)且僅當(dāng)a∈A=>a∈B。

A是B的真子集，記做AB，當(dāng)且僅當(dāng)AB∧B-A≠。

A和B是相等集合，記做A=B，當(dāng)且僅當(dāng)AB=BA。子集劃分定義給定集合B，以及B的一組子集Al、A2、……、An，這些子集是B的一個(gè)劃分，當(dāng)且僅當(dāng)：

Al∪A2∪…∪An=B，且

i≠j=>Ai∩Aj=空集劃分對(duì)測試人員很有用，因?yàn)閮蓚€(gè)界定性質(zhì)會(huì)產(chǎn)生重要保證：完備性(任何事物都在某處)和無冗余性。

集合恒等式集合操作和關(guān)系合在一起，會(huì)產(chǎn)生一種重要的集合恒等式類，可以用于代數(shù)級(jí)地簡化復(fù)雜集合的表示。

名稱表達(dá)式等同律A∪A=A

A∩A=A求反律(A’)’=A交換律A∪B=B∪A

A∩B=B∩A結(jié)合律A∪(B∪C)=(A∪B)∪CA∩(B∩C)=(A∩B)∩C分配律A∪(B∩C)=(A∪B)∩(A∪C)A∩(B∪C)=(A∩B)∪(A∩C)迪摩根定律(A∪B)’=A’∩B’(A∩B)’=A’∪B’函數(shù)定義給定集合A和B，函數(shù)f是A×B的一個(gè)子集，使得ai、aj∈A，bi、bj∈B，f(ai)=bi，f(aj)=bj，bi≠bj=>ai≠aj。

函數(shù)f的輸入是集合A的元素，f的輸出是B的元素。

定義域和值域集合A是函數(shù)f的定義域，集合B是值域。由于輸入和輸出具有某種“自然”順序，因此很容易進(jìn)一步說函數(shù)f是一個(gè)有序?qū)ε嫉募希渲械谝粋€(gè)元素來自定義域，第二個(gè)元素來自值域。以下是函數(shù)的兩種常見表示法：

f：A->Bf：A×B

函數(shù)類型首先給出函數(shù)f：AB，并且定義集合：

f(A)={bi∈B：bi=f(ai)對(duì)于某個(gè)ai∈A}

這個(gè)集合有時(shí)記做A在f下的映象。定義

f是從A到B的上函數(shù)，當(dāng)且僅當(dāng)f(A)=B。

f是從A到B的中函數(shù)，當(dāng)且僅當(dāng)f(A)B。(請(qǐng)注意這里的真子集!)f是從A到B的一對(duì)一函數(shù)，當(dāng)且僅當(dāng)對(duì)于所有ai、aj∈A，ai≠aj==>f(ai)≠f(aj)。

f是從A到B的多對(duì)一函數(shù)，當(dāng)且僅當(dāng)存在ai、aj∈A，ai≠aj

使得f(ai)=f(aj)。函數(shù)類型NextDate:A->B是什么函數(shù)？NextDate:A->C是什么函數(shù)？一對(duì)一的中函數(shù)一對(duì)一的上函數(shù)函數(shù)合成函數(shù)的合成鏈對(duì)于測試的影響(1)多個(gè)b取值的來源？（2）時(shí)序問題函數(shù)合成假設(shè)我們有集合和函數(shù)，使得一個(gè)函數(shù)的值域是另一個(gè)函數(shù)的定義域：

f：A→Bg：B→Ch：C→D

如果出現(xiàn)這種情況，則可以合成函數(shù)。為此，設(shè)引用集合定義域和值域的特定元素a∈A、b∈B、c∈C、d∈D，并假設(shè)f(a)=b、g(b)=c和h(c)=d，則函數(shù)g和f的合成為：

h·g·f(a)=h(g(f(a)))=h(g(b))=h(c)=d傭金合成的例子關(guān)系函數(shù)是關(guān)系的一種特例：兩者都是某個(gè)笛卡兒積的子集。但是對(duì)于函數(shù)，定義域元素不能與多個(gè)值域元素關(guān)聯(lián)并不是所有關(guān)系都嚴(yán)格地是函數(shù)。集合之間的關(guān)系定義給定兩個(gè)集合A和B，關(guān)系R是笛卡兒積AXB的一個(gè)子集。

有兩種表示法很常見，如果希望描述整個(gè)關(guān)系，則通常只寫RAXB。對(duì)于特定元素aj∈A、bj∈B，我們記做aiRbi。

關(guān)系R的勢定義給定兩個(gè)集合A和B，一個(gè)關(guān)系RAxB，關(guān)系R的勢是：一對(duì)一勢，當(dāng)且僅當(dāng)R是A到B的一對(duì)一函數(shù)。多對(duì)一勢，當(dāng)且僅當(dāng)R是A到B的多對(duì)一函數(shù)。一對(duì)多勢，當(dāng)且僅當(dāng)至少有一個(gè)元素a∈A在R中的兩個(gè)有序?qū)ε贾?a，bj)∈R和(a，bi)∈R

多對(duì)多勢，當(dāng)且僅當(dāng)至少有一個(gè)元素a∈A在R中的兩個(gè)有序?qū)ε贾校?a，bi)∈R和(a，bj)∈R。并且至少有一個(gè)元素b∈B在R中的兩個(gè)有序?qū)ε贾校?ai，b)∈R和(aj，b)∈R。函數(shù)參與的概念函數(shù)映射到值域上或值域中之間的差別可以與關(guān)系類比，這就是參與概念。定義給定兩個(gè)集合A和B，一個(gè)關(guān)系RAXB，關(guān)系R的參與是：全參與，當(dāng)且僅當(dāng)A中的所有元素都在R的某個(gè)有序?qū)ε贾?。部分參與，當(dāng)且僅當(dāng)A中有元素不在R的有序?qū)ε贾?。上參與，當(dāng)且僅當(dāng)B中的所有元素都在R的某個(gè)有序?qū)ε贾?。中參與，當(dāng)且僅當(dāng)B中有元素不在R的有序?qū)ε贾?。單個(gè)集合上的關(guān)系設(shè)A是一個(gè)集合，設(shè)RAXA是定義在A上的一個(gè)關(guān)系，<a，a>、<a，b>、<b，a>、<b，c>、<a，c>∈R。關(guān)系具有四個(gè)特殊屬性：定義關(guān)系RAXA是：自反的，當(dāng)且僅當(dāng)所有a∈A，<a，a>∈R。對(duì)稱的，當(dāng)且僅當(dāng)<a，b>∈R=><b，a>∈R。反對(duì)稱的，當(dāng)且僅當(dāng)<a，b>、<b，a>∈R=>a=b。傳遞的，當(dāng)且僅當(dāng)<a，b>、<b，c>∈R=><a，c>∈R。

排序關(guān)系和等價(jià)關(guān)系定義

關(guān)系RAXA是排序關(guān)系，如果R是自反、反對(duì)稱和傳遞的。定義

關(guān)系RAXA是等價(jià)關(guān)系，如果R是自反、對(duì)稱和傳遞的。

命題邏輯命題是要么真要么假的句子，我們叫做命題的真值。命題是無歧義的：給定一個(gè)命題，總是能夠確定它是真還是假。

邏輯操作符

邏輯操作符(又叫做邏輯連接符或操作)根據(jù)它們對(duì)命題真值的作用來定義。也就是說，只使用兩個(gè)值：T(代表真)和F(代表假)。三種基本邏輯操作符是與(∧)、或(∨)和非(﹁)。這些操作符有時(shí)又叫做合取、析取和非。

pqp∧qp∨q﹁pTTTTFTFFTFFTFTTFFFFT邏輯操作符異或：只有當(dāng)一個(gè)命題為真時(shí)，異或?yàn)檎妗?/p>

IF-THEN連接（→）pqp⊕qp→qTTFTTFTFFTTTFFFT邏輯表達(dá)式pqp→qq→p(p→q)∧(q→p)﹁((p→q)∧(q→p))TTTTTFTFFTFTFTTFFTFFTTTF邏輯等價(jià)定義兩個(gè)命題p和q是等價(jià)的(記做pq)，當(dāng)且僅當(dāng)其真值表相同。定義永遠(yuǎn)為真的命題是重言式，永遠(yuǎn)為假的命題是矛盾式。

邏輯等價(jià)定律表達(dá)式等同律p∧Tpp∨Fp支配律p∨TTp∧FF冪等律p∧ppp∨pp求反律﹁(﹁p)p交換律p∧qq∧pp∨qq∨p結(jié)合律p∧(q∧r)(p∧q)∧rp∨(q∨r)(p∨q)∨r分配律p∧(q∨r)(p∧q)∨(p∧r)p∨(q∧r)(p∨q)∧(p∨r)迪摩根定律﹁(p∧q)﹁p∨﹁q﹁(p∨q)﹁p∧﹁q概率論

定義結(jié)果可能性相等的有限樣本空間S中的事件E的概率，是p(E)=/。

定義命題p的真值集合T記做T(p)，是p為真的論域空間U中的所有元素的集合。定義命題p為真的概率記做Pr(p)=/。

EST(p)UNextDate例子：p(m):m是一個(gè)有30天的月份T(p(m))={4月，6月，9月，11月}U={1月，2月，…，12月}這樣，給定月份有30天的概率是：Pr(p)=|T(p)|/|U|=4/12概率論給定論域空間，命題p和q，真值集合是T(p)和T(q)：

Pr(﹁p)=1—Pr(p)Pr(p∧q)=Pr(p)XPr(q)Pr(pVq)=Pr(p)+Pr(q)-Pr(p∧q)

這些事實(shí)，結(jié)合集合論和命題恒等式表，為操作概率表達(dá)式提供了強(qiáng)有力的代數(shù)能力。

課程內(nèi)容離散數(shù)學(xué)圖論圖圖(又叫做線性圖)是一種由兩個(gè)集合定義的抽象數(shù)學(xué)結(jié)構(gòu)，即一個(gè)節(jié)點(diǎn)集合和一個(gè)構(gòu)成節(jié)點(diǎn)之間連接的邊集合。

定義圖G=(V，E)由節(jié)點(diǎn)的有限(并且非空)集合V和節(jié)點(diǎn)無序?qū)ε技螮組成。

V={n1，n2，…，nm)和

E={el，e2，…，ep}

其中每條邊ek=(ni，nj)，ni、nj∈V。舉例V={nl，n2，n3，n4，n5，n6，n7)E={e1，e2，e3，e4，e5}={(nl，n2)，(nl，n4)，(n3，n4)，(n2，n5)，(n4，n6)}圖4-1有7個(gè)節(jié)點(diǎn)和5條邊的圖n1n2n4n3n5n6n7e1e2e3e4e5節(jié)點(diǎn)的度定義圖中節(jié)點(diǎn)的度是以該節(jié)點(diǎn)作為端點(diǎn)的邊的條數(shù)。我們把節(jié)點(diǎn)n的度記做deg(n)。

deg(n1)=2deg(n2)=2deg(n3)=1deg(n4)=3deg(n5)=1deg(n6)=1deg(n7)=0關(guān)聯(lián)矩陣定義擁有m個(gè)節(jié)點(diǎn)和n條邊的圖G=(V，E)的關(guān)聯(lián)矩陣是一種m×n矩陣，其中第i行第j列的元素是1，當(dāng)且僅當(dāng)節(jié)點(diǎn)i是邊j的一個(gè)端點(diǎn)，否則該元素是0。

e1e2e3e4e5n111000n210010n300100n401101n500010n600001n700000相鄰矩陣定義

擁有m個(gè)節(jié)點(diǎn)和n條邊的圖G=(V，E)的相鄰矩陣是一種m×m矩陣，其中第i行第j列的元素是1，當(dāng)且僅當(dāng)節(jié)點(diǎn)i和節(jié)點(diǎn)j之間存在一條邊，否則該元素是0。n1n2n3n4n5n6n7n10101000n21000100n30001000n41010010n50100000n60001000n70000000路徑定義路徑是一系列的邊，對(duì)于序列中的任何相鄰邊對(duì)偶ei、ej，邊都擁有相同的(節(jié)點(diǎn))端點(diǎn)。

路徑可以描述為一系列邊，也可以描述為一系列節(jié)點(diǎn)。一般更常見的是節(jié)點(diǎn)序列。

路徑節(jié)點(diǎn)序列邊序列n1和n5之間n1，n2，n5e1，e4n6和n5之間n6，n4，n1，n2，n5e5，e2

，e1，e4n3和n2之間n3，n4，n1，n5e3，e2，e1n1n2n4n3n5n6n7e1e2e3e4e5連接性定義節(jié)點(diǎn)ni和nj是被連接的，當(dāng)且僅當(dāng)它們都在同一條路徑上?！斑B接性”是一種圖的節(jié)點(diǎn)集合上的等價(jià)關(guān)系。為了說明這一點(diǎn)，可以再復(fù)習(xí)一遍定義等價(jià)關(guān)系的三個(gè)性質(zhì)：

1．連接性是自反的，因?yàn)槊總€(gè)節(jié)點(diǎn)顯然都在到其本身長度為0的路徑上。

2．連接性是對(duì)稱的，由于如果ni和nj在一條路徑上，則nj和ni也在同一條路徑上。

3．連接性是傳遞的。

組件定義圖的組件是相連節(jié)點(diǎn)的最大集合。等價(jià)類中的節(jié)點(diǎn)是圖的組件。圖4-1種的圖有兩個(gè)組件：

{n1，n2，n3，n4，n5，n6}{n7}n1n2n4n3n5n6n7e1e2e3e4e5壓縮圖定義

給定圖G=(V，E)，其壓縮圖通過用壓縮節(jié)點(diǎn)替代每個(gè)組件構(gòu)成。給定圖的壓縮圖是惟一的。

S1=

{n1，n2，n3，n4，n5，n6}S2={n7}圈數(shù)定義．圖G的圈數(shù)由V(G)=e–n+p給出，其中：

e是G中的邊數(shù)。

n是G中的節(jié)點(diǎn)數(shù)。

p是G中的組件數(shù)。

n1n2n3n4n5n6n7有向圖定義有向圖（或框圖）D=(V，E)包含：一個(gè)節(jié)點(diǎn)的有限集合V=(n1，n2，…，nm)，一個(gè)邊的集合E=<e1，e2，…，ep}，其中每條邊ek=<ni，nj>是節(jié)點(diǎn)ni、nj∈V的一個(gè)有序?qū)ε肌?/p>

有向圖例子n1n2n4n3n5n6n7e1e2e3e4e5V={nl，n2，n3，n4，n5，n6，n7)E={e1，e2，e3，e4，e5}={<nl，n2>，<nl，n4>，<n3，n4>，<n2，n5>，<n4，n6>}圖4-2一個(gè)有向圖外度和內(nèi)度定義有向圖中節(jié)點(diǎn)的內(nèi)度，是將該節(jié)點(diǎn)作為終止節(jié)點(diǎn)的不同邊的條數(shù)。節(jié)點(diǎn)n的內(nèi)度記做indeg(n)

有向圖中節(jié)點(diǎn)的外度，是將該節(jié)點(diǎn)作為開始節(jié)點(diǎn)的不同邊的條數(shù)。節(jié)點(diǎn)n的外度記做outdeg(n)indeg(n1)=0Outdeg(n1)=2indeg(n2)=1Outdeg(n2)=1indeg(n3)=0Outdeg(n3)=1indeg(n4)=2Outdeg(n4)=1indeg(n5)=1Outdeg(n5)=0indeg(n6)=1Outdeg(n6)=0indeg(n7)=0Outdeg(n7)=0n1n2n4n3n5n6n7e1e2e3e4e5節(jié)點(diǎn)的類型定義內(nèi)度為0的節(jié)點(diǎn)是源節(jié)點(diǎn)。外度為0的節(jié)點(diǎn)是吸收節(jié)點(diǎn)。內(nèi)度不為0，并且外度不為0的節(jié)點(diǎn)是傳遞節(jié)點(diǎn)。有向圖的相鄰矩陣

定義

有m個(gè)節(jié)點(diǎn)的有向圖D=(V，E)的相鄰矩陣是一種m×m矩陣：A=(a(i，j))，其中a(i，j)是1，當(dāng)且僅當(dāng)從節(jié)點(diǎn)i到節(jié)點(diǎn)j有一條邊，否則該元素為0。n1n2n3n4n5n6n7n10101000n20000100n30001000n40000010n50000000n60000000n70000000路徑和半路徑定義

(有向)路徑是一系列邊，使得對(duì)于該序列中的所有相鄰邊對(duì)偶ei,ej來說，第一條邊的終止節(jié)點(diǎn)是第二條邊的初始節(jié)點(diǎn)。

環(huán)路是一個(gè)在同一個(gè)節(jié)點(diǎn)上開始和結(jié)束的有向路徑。

(有向)半路徑是一系列邊，使得對(duì)于該序列中至少有一個(gè)相鄰邊對(duì)偶ei,ej來說，第一條邊的初始節(jié)點(diǎn)是第二條邊的初始節(jié)點(diǎn)，或第一條邊的終止節(jié)點(diǎn)是第二條邊的終止節(jié)點(diǎn)。n1n2n4n3n5n6n7e1e2e3e4e5示例從n1到n6的一條路徑從n1到n3的一條半路徑從n2到n4的一條半路徑從n5到n6的一條半路徑可到達(dá)性矩陣定義

有m個(gè)節(jié)點(diǎn)的有向圖D=(V，E)的可達(dá)性矩陣是一種m×m矩陣R=(r(i,j))，其中r(i，j)是1，當(dāng)且僅當(dāng)從節(jié)點(diǎn)i到節(jié)點(diǎn)j有一條路徑，否則該元素為0。

有向圖D的可到達(dá)性矩陣可以通過相鄰矩陣A計(jì)算如下：

R=I+A+A2+A3+…+Ak其中k是D最長路徑的長度，I是單位矩陣。

圖4-2的可到達(dá)性矩陣n1n2n3n4n5n6n7n10101110n20000100n30001010n40000010n50000000n60000000n7000000058A可以通到B及EB可以通到C從A到C僅有一長度為二的有向漫游ABC存在59A可以通到B及EB可以通到F從A到F有ABF及AEF兩種長度為二的有向漫游存在E可以通到F從A到B有三條長度為三的有向漫游ABCBABFBAEFB將亮點(diǎn)之間各種長度的漫游數(shù)目加總，如果將大于零的數(shù)字改成1，來表示兩點(diǎn)之間是否相通R=I+A+A2+A3+…+Akn-連接性定義

有向圖中的兩個(gè)節(jié)點(diǎn)ni和nj是：

0-連接，當(dāng)且僅當(dāng)ni和nj之間沒有路徑。

l-連接，當(dāng)且僅當(dāng)ni和nj之間有一條半路徑，但是沒有路徑。

2-連接，當(dāng)且僅當(dāng)從ni和nj之間有一條路徑。

3-連接，當(dāng)且僅當(dāng)從ni和nj有一條路徑，并且從nj到ni有一條路徑。圖4-2的連接性n1和n7是0—連接。n2和n6是1—連接。n1和n6是2—連接。n3和n6是3—連接。n1n2n4n3n5n6n7e1e2e3e4e5強(qiáng)組件定義

有向圖的強(qiáng)組件是3-連接節(jié)點(diǎn)的最大集合。

n1n2S1n5S2e1e2e4n4n3n6e3e5n7用于測試的圖程序圖有限狀態(tài)機(jī)

Petri網(wǎng)狀態(tài)圖程序圖定義給定一個(gè)采用命令式程序設(shè)計(jì)語言編寫的程序，其程序圖是一種有向圖，其中：

1．(傳統(tǒng)定義)

節(jié)點(diǎn)是程序語句，邊表示控制流(從節(jié)點(diǎn)i到節(jié)點(diǎn)j有一條邊，當(dāng)且僅當(dāng)對(duì)應(yīng)節(jié)點(diǎn)j的語句可以立即在節(jié)點(diǎn)i對(duì)應(yīng)的語句之后執(zhí)行)。

2．(經(jīng)過改進(jìn)的定義)

節(jié)點(diǎn)要么是整個(gè)語句，要么是語句的一部分，邊表示控制流(從節(jié)點(diǎn)i到節(jié)點(diǎn)j有一條邊，當(dāng)且僅當(dāng)對(duì)應(yīng)節(jié)點(diǎn)j的語句或語句的一部分，可以立即在節(jié)點(diǎn)i對(duì)應(yīng)的語句或語句的一部分之后執(zhí)行)。

結(jié)構(gòu)化程序設(shè)計(jì)構(gòu)造的有向圖串行IF-ThenIF-Then-Else條件前測試環(huán)路后測試環(huán)路有限狀態(tài)機(jī)有限狀態(tài)機(jī)是一種有向圖，其中狀態(tài)是節(jié)點(diǎn)，轉(zhuǎn)移是邊。源狀態(tài)和吸收狀態(tài)是初始節(jié)點(diǎn)和終止節(jié)點(diǎn)，路徑被建模為通路，等等。大多數(shù)有限狀態(tài)機(jī)表示方法都要為邊(轉(zhuǎn)移)增加信息，以指示轉(zhuǎn)移的原因和作為轉(zhuǎn)移的結(jié)果要發(fā)生的行動(dòng)。

用于PIN嘗試的有限狀態(tài)機(jī)Petri網(wǎng)定義

Petri網(wǎng)是一種雙向有向圖(P，T，In，Out)，其中，P和T是不相交的節(jié)點(diǎn)集合，P是地點(diǎn)集合，T是轉(zhuǎn)移集合，In和Out是邊集合，InP×T，Out

T×P。

P1P5P2P3P4t1t2t3有標(biāo)記的Petri網(wǎng)定義有標(biāo)記的Petri網(wǎng)是一種5元組(P，T，In，Out，M)，其中(P，T，In，Out)是一個(gè)Petri網(wǎng)，M是從地點(diǎn)到正整數(shù)的映射集合。····t1p1p5p2t3p4p3t2Petri網(wǎng)的標(biāo)記元組是<1，1，0，2，0>。兩個(gè)基本定義定義轉(zhuǎn)移可以在Petri網(wǎng)中發(fā)生，如果在其所有輸入地點(diǎn)中至少有一個(gè)記號(hào)。定義當(dāng)觸發(fā)Petri網(wǎng)一個(gè)轉(zhuǎn)移時(shí)，要從其每個(gè)輸入地點(diǎn)刪除一個(gè)記號(hào)，并在其每個(gè)輸出地點(diǎn)增加一個(gè)記號(hào)。兩個(gè)基本定義·····t1p1p5p2t3p4p3t2·····t1p1p5p2t3p4p3t2M={<1，1，1，2，0>，<1，1，0，3，0>}

2023/2/674另一種表示庫所places(被動(dòng))：表示媒介、緩沖器、地理位置、狀態(tài)、階段、條件變遷transitions(主動(dòng))：通常表示事件，操作，轉(zhuǎn)換和傳輸連接在庫所和變遷之間，具有方向庫所可以容納標(biāo)記，用黑點(diǎn)表示。標(biāo)記通常表示對(duì)象，這些對(duì)象可能是具體的事物，也可能是抽象的信息，如上例中每個(gè)標(biāo)記都表示一個(gè)保險(xiǎn)索賠案例。Petri網(wǎng)結(jié)構(gòu)是固定的，而庫所中的標(biāo)記的分布是可變化的。payClaimUnderconsiderationreadySend_letterRecordrgredyellowgreenyrgy例子：交通燈rg1red1yellow1green1yr1gy1rg2red2yellow2green2yr2gy2例子：兩個(gè)交通燈rg1red1yellow1green1yr1gy1rg2red2yellow2green2yr2gy2safe例子：兩個(gè)安全的交通燈rg1red1yellow1green1yr1gy1rg2red2yellow2green2yr2gy2safe2safe1例子：安全而公平的交通燈事件驅(qū)動(dòng)的Petri網(wǎng)定義

EDPN是一種多向圖(P，D，S，In，Out)，包括三個(gè)節(jié)點(diǎn)集合P、D和S，以及兩個(gè)映射集合In和Out。其中：

P是端口事件的集合。

D是數(shù)據(jù)地點(diǎn)的集合。

S是轉(zhuǎn)移的集合。

In是(P∪D)×S的有序?qū)ε技稀?/p>

Out是S×(P∪D)的有序?qū)ε技?。EDPN圖p3d5p4p3d6p4d7s7s8s10s9為EDPN做標(biāo)記定義

EDPN(P，D，S，In，Out)的一個(gè)標(biāo)記M，是p元組的一個(gè)序列M=<m1，m2，…>，其中l(wèi)=k+n，k和n是集合P和D中的元素個(gè)數(shù)，p元組中的個(gè)體項(xiàng)表示事件或數(shù)據(jù)地點(diǎn)中的記號(hào)個(gè)數(shù)。

p3d5p4p3d6p4d7s7s8s10s9元素類型描述p3端口輸入事件順時(shí)針旋轉(zhuǎn)p4端口輸入事件逆時(shí)針旋轉(zhuǎn)d5數(shù)據(jù)地點(diǎn)位置1d6數(shù)據(jù)地點(diǎn)位置2d7數(shù)據(jù)地點(diǎn)位置3s7轉(zhuǎn)換狀態(tài)轉(zhuǎn)換：d5到d6s8轉(zhuǎn)換狀態(tài)轉(zhuǎn)換：d6到d7s9轉(zhuǎn)換狀態(tài)轉(zhuǎn)換：d7到d6s10轉(zhuǎn)換狀態(tài)轉(zhuǎn)換：d6到d5EDPN圖中的標(biāo)記和轉(zhuǎn)移p3d5p4p3d6p4d7s7s8s10s9標(biāo)記：元組（p3,p4,d5,d6,d7）

m1

（0,0,1,0,0）

m2

（1,0,1,0,0）

m3

（0,0,0,1,0）

m4

（1,0,0,1,0）

m5

（0,0,0,0,1）

m6

（0,1,0,0,1）

m7

（0,0,0,0,1）轉(zhuǎn)移：元組描述

m1

無

m2s7m3無