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

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

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

Y={1812，1813，1814，…

…，2011，2012}

給出辨別規(guī)則；

Y={年：1812≤年≤2012}

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

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

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

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

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

空集采用符號表示，在集合論中占有特殊位置?？占话?。

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

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

4月

11月

9月

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

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

A的補是集合A’={x：xA}。

B針對A的相對補是集合A-B={x：x∈A∧xB}。

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

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

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

兩者的差別是，對于a≠b，

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

<a，b>≠<b，a>

笛卡兒積的定義定義兩個集合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中的元素數(shù)，采用表示。對于集合A和B，=×AA×BAB集合關系定義

A是B的子集，記做AB，當且僅當a∈A=>a∈B。

A是B的真子集，記做AB，當且僅當AB∧B-A≠。

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

Al∪A2∪…∪An=B，且

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

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

名稱表達式等同律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的一個子集，使得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是值域。由于輸入和輸出具有某種“自然”順序，因此很容易進一步說函數(shù)f是一個有序?qū)ε嫉募希渲械谝粋€元素來自定義域，第二個元素來自值域。以下是函數(shù)的兩種常見表示法：

f：A->Bf：A×B

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

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

這個集合有時記做A在f下的映象。定義

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

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

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

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

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

如果出現(xiàn)這種情況，則可以合成函數(shù)。為此，設引用集合定義域和值域的特定元素a∈A、b∈B、c∈C、d∈D，并假設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傭金合成的例子關系函數(shù)是關系的一種特例：兩者都是某個笛卡兒積的子集。但是對于函數(shù)，定義域元素不能與多個值域元素關聯(lián)并不是所有關系都嚴格地是函數(shù)。集合之間的關系定義給定兩個集合A和B，關系R是笛卡兒積AXB的一個子集。

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

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

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

排序關系和等價關系定義

關系RAXA是排序關系，如果R是自反、反對稱和傳遞的。定義

關系RAXA是等價關系，如果R是自反、對稱和傳遞的。

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

邏輯操作符

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

pqp∧qp∨q﹁pTTTTFTFFTFFTFTTFFFFT邏輯操作符異或：只有當一個命題為真時，異或為真。

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

邏輯等價定律表達式等同律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是一個有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)

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

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

定義圖G=(V，E)由節(jié)點的有限(并且非空)集合V和節(jié)點無序?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個節(jié)點和5條邊的圖n1n2n4n3n5n6n7e1e2e3e4e5節(jié)點的度定義圖中節(jié)點的度是以該節(jié)點作為端點的邊的條數(shù)。我們把節(jié)點n的度記做deg(n)。

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

e1e2e3e4e5n111000n210010n300100n401101n500010n600001n700000相鄰矩陣定義

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

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

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

，e1，e4n3和n2之間n3，n4，n1，n5e3，e2，e1n1n2n4n3n5n6n7e1e2e3e4e5連接性定義節(jié)點ni和nj是被連接的，當且僅當它們都在同一條路徑上。“連接性”是一種圖的節(jié)點集合上的等價關系。為了說明這一點，可以再復習一遍定義等價關系的三個性質(zhì)：

1．連接性是自反的，因為每個節(jié)點顯然都在到其本身長度為0的路徑上。

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

3．連接性是傳遞的。

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

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

給定圖G=(V，E)，其壓縮圖通過用壓縮節(jié)點替代每個組件構(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é)點數(shù)。

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

n1n2n3n4n5n6n7有向圖定義有向圖（或框圖）D=(V，E)包含：一個節(jié)點的有限集合V=(n1，n2，…，nm)，一個邊的集合E=<e1，e2，…，ep}，其中每條邊ek=<ni，nj>是節(jié)點ni、nj∈V的一個有序?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一個有向圖外度和內(nèi)度定義有向圖中節(jié)點的內(nèi)度，是將該節(jié)點作為終止節(jié)點的不同邊的條數(shù)。節(jié)點n的內(nèi)度記做indeg(n)

有向圖中節(jié)點的外度，是將該節(jié)點作為開始節(jié)點的不同邊的條數(shù)。節(jié)點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é)點的類型定義內(nèi)度為0的節(jié)點是源節(jié)點。外度為0的節(jié)點是吸收節(jié)點。內(nèi)度不為0，并且外度不為0的節(jié)點是傳遞節(jié)點。有向圖的相鄰矩陣

定義

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

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

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

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

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

有向圖D的可到達性矩陣可以通過相鄰矩陣A計算如下：

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

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

有向圖中的兩個節(jié)點ni和nj是：

0-連接，當且僅當ni和nj之間沒有路徑。

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

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

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

有向圖的強組件是3-連接節(jié)點的最大集合。

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

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

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

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

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

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

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

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

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

T×P。

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

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

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

P是端口事件的集合。

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

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

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

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

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

p3d5p4p3d6p4d7s7s8s10s9元素類型描述p3端口輸入事件順時針旋轉(zhuǎn)p4端口輸入事件逆時針旋轉(zhuǎn)d5數(shù)據(jù)地點位置1d6數(shù)據(jù)地點位置2d7數(shù)據(jù)地點位置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圖中的標記和轉(zhuǎn)移p3d5p4p3d6p4d7s7s8s10s9標記：元組（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無