測試人員的離散數(shù)學(xué)

1、Software Testing 軟件測試Software Testing 第第3章章 測試人員的離散數(shù)學(xué)測試人員的離散數(shù)學(xué)學(xué)習(xí)目標(biāo) 集合論（掌握） 函數(shù)（了解） 關(guān)系（了解） 命題邏輯（掌握）3.1集合論集合：作為一個(gè)單位，或一個(gè)整體引用多個(gè)事物。 集合成員關(guān)系集合中的項(xiàng)叫做集合的元素或成員，這種關(guān)系采用符號表示。集合定義集合定義簡單列出集合的元素簡單列出集合的元素給出辨別規(guī)則給出辨別規(guī)則通過其他集合構(gòu)建通過其他集合構(gòu)建 無歧義定義清晰無歧義定義清晰很難列舉很難列舉空集空集空集采用符號空集采用符號表示表示 ?？占??？占话亍０?。空集空集是惟一的，即不會(huì)有兩是惟一的，即不會(huì)有兩個(gè)

2、空集個(gè)空集。如果集合被決策規(guī)則定義為永如果集合被決策規(guī)則定義為永遠(yuǎn)失敗，則該集合是空集。遠(yuǎn)失敗，則該集合是空集。 維恩圖維恩圖 在維恩圖中，集合被表示為一個(gè)圓圈，在維恩圖中，集合被表示為一個(gè)圓圈，圓圈中的點(diǎn)表示集合元素圓圈中的點(diǎn)表示集合元素 維恩圖以直觀方式表示各種集合關(guān)系，維恩圖以直觀方式表示各種集合關(guān)系，但存在一些但存在一些問題問題：無限集合、空集等無限集合、空集等U集合操作集合操作 集合基本操作：并、交和補(bǔ)集合基本操作：并、交和補(bǔ) 定義定義 給定集合給定集合A A和和B B， 其其并并是集合是集合A AB B x x：x x A Ax x B B 。 其其交交是集合是集合ABAB x x

3、：x x A Ax x B B 。 A A的的補(bǔ)補(bǔ)是集合是集合AA x x：x x 不屬于不屬于A A 。 B B針對針對A A的的相對補(bǔ)相對補(bǔ)是集合是集合A AB B x x：x x A Ax x不屬于不屬于B B A A和和B B的的對稱差對稱差是集合是集合A A B B x x：x x A A x x B B ABABABABAAABA-BABA BA B（AB）-（AB）舉例 給定兩個(gè)集合：給定兩個(gè)集合： A= 1A= 1，3 3，4 4，7 7，8 8，1010，11 11 B= 2 B= 2，3 3，5 5，6 6，8 8，9 9，1111； 求求A AB B， ABAB， A A

4、B B， A A B B。 無序和有序?qū)ε?無序和有序?qū)ε嫉谋硎痉ㄒ话闶牵?無序?qū)ε迹海╝，b） 有序?qū)ε迹?兩者的差別是，對于ab， （a，b）（ b，a），但是 這種差別對于圖論很重要。兩個(gè)集合的笛卡兒集 定義 兩個(gè)集合A和B的笛卡兒積（又叫叉積），是集合AB：x Ay B 笛卡兒積與運(yùn)算有直觀的聯(lián)系。集合A的勢是勢是A A中元素?cái)?shù)，用中元素?cái)?shù)，用|A|A|表示表示，對于集合A和B , |AB|=|A|B|。維恩圖不能顯示笛卡兒積維恩圖不能顯示笛卡兒積集合關(guān)系 定義定義 A A是是B B的的子集子集，記做，記做A BA B， 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)a a Aa Aa B B A A是是B B的的

5、真子集真子集，記做，記做A BA B， 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)A BA BB BAA A A和和B B是是相等集合相等集合，記做，記做A AB B， 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)A BA BB AB A子集劃分 劃分劃分劃分是將一個(gè)整體分成小塊，使得所有事物都在劃分是將一個(gè)整體分成小塊，使得所有事物都在某個(gè)小塊中，不會(huì)遺漏某個(gè)小塊中，不會(huì)遺漏。 定義定義 給定集合給定集合B B，以及，以及B B的一組子集的一組子集A1A1、A2A2、 、AnAn，這些子集是，這些子集是B B的一個(gè)劃分，的一個(gè)劃分，當(dāng)且僅當(dāng)：當(dāng)且僅當(dāng)： A 1A 1A 2A 2 A n A nB B ijij A A iAiA j j完備性（未

6、測試完備性（未測試）無冗余性（多次測試）無冗余性（多次測試）集合恒等式集合恒等式名稱名稱 表達(dá)式表達(dá)式等同律等同律 A AA AUA AUA A支配律支配律 A AUUU AU A冪等律冪等律 A AA AA AAA AAA A求反律求反律 （A A ） A A交換律交換律 A AB BB BA ABA ABBABA結(jié)合律結(jié)合律 A A(B(BC)C)(A(AB)B)C C A(BC) A(BC)(AB)C(AB)C分配律分配律 A A(BC)(BC)(A(AB)( AB)( AC)C) A(B A(BC)C)(AB)(AB)( AC)( AC)迪摩根定律迪摩根定律 （A AB B） A B

7、A B （ABAB） A A B B 3.2 函數(shù)函數(shù) 函數(shù)是軟件開發(fā)和測試的核心概念函數(shù)是軟件開發(fā)和測試的核心概念函數(shù)定義函數(shù)定義給定集合給定集合A A和和B B，函數(shù)，函數(shù)f f是是A AB B的一個(gè)子集，使的一個(gè)子集，使得對于得對于a ai i、a aj jA A，b bi i、b bj jB B，f(af(ai i) )b bi i，f(af(aj j) ) b bj j，b bi ibbj j a ai iaaj j。 記為：記為：f f：ABAB 函數(shù)映射：給出函數(shù)函數(shù)映射：給出函數(shù)f f：ABAB，并且定義，并且定義集合：集合： f(A) f(A) bi biB B：bibif(

8、ai)f(ai)對于某個(gè)對于某個(gè)aiaiA A ，這個(gè)集合有時(shí)記做這個(gè)集合有時(shí)記做A A在在f f下的映象。下的映象。函數(shù)類型 類型定義：類型定義： f f是從是從A A到到B B的的上函數(shù)上函數(shù)，當(dāng)且僅當(dāng)，當(dāng)且僅當(dāng)f f（A A）B B f f是從是從A A到到B B的的中函數(shù)中函數(shù)，當(dāng)且僅當(dāng)，當(dāng)且僅當(dāng)f f（A A） B B f f是從是從A A到到B B的的一對一函數(shù)一對一函數(shù)，當(dāng)且僅當(dāng)對于所有，當(dāng)且僅當(dāng)對于所有aiai、ajajA A，aiaj faiaj f（aiai） f f（ajaj）。）。 f f是從是從A A到到B B的的多對一函數(shù)多對一函數(shù)，當(dāng)且僅當(dāng)存在，當(dāng)且僅當(dāng)存在aia

9、i、aj aj A A，aiajaiaj使得使得f f（aiai） f f（ajaj）。）。 函數(shù)合成 設(shè)引用集合定義域和值域的特定元素a A、bB、cC、dD，并假設(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） dfgfgBabcabbbc因果流因果流非因果流非因果流函數(shù)合成函數(shù)合成3.3關(guān)系關(guān)系 函數(shù)是關(guān)系的一種特例函數(shù)是關(guān)系的一種特例 集合之間的關(guān)系集合之間的關(guān)系 定義：給定兩個(gè)集合定義：給定兩個(gè)集合A A和和B B，關(guān)系，關(guān)系R R是笛卡兒積是笛卡兒積A AB B的一個(gè)子集。的一個(gè)子集。勢：指集合中的元素個(gè)數(shù)

10、勢：指集合中的元素個(gè)數(shù) 給定兩個(gè)集合給定兩個(gè)集合A A和和B B，一個(gè)關(guān)系，一個(gè)關(guān)系R AR AB B，關(guān)，關(guān)系系R R的勢是：的勢是： 一對一勢一對一勢，當(dāng)且僅當(dāng)，當(dāng)且僅當(dāng)R R是是A A到到B B的一對一函數(shù)。的一對一函數(shù)。 多對一勢多對一勢，當(dāng)且僅當(dāng)，當(dāng)且僅當(dāng)R R是是A A到到B B的多對一函數(shù)。的多對一函數(shù)。 一對多勢一對多勢，當(dāng)且僅當(dāng)至少有一個(gè)元素，當(dāng)且僅當(dāng)至少有一個(gè)元素a aA A在在R R中的兩中的兩個(gè)有序?qū)ε贾校矗▊€(gè)有序?qū)ε贾?，即?a a，b bi i）R R和（和（a a，b bj j）R R 多對多勢多對多勢，當(dāng)且僅當(dāng)至少有一個(gè)元素，當(dāng)且僅當(dāng)至少有一個(gè)元素a aA A

11、在在R R中的兩中的兩個(gè)有序?qū)ε贾?，即（個(gè)有序?qū)ε贾?，即?a a，b bi i）R R和（和（a a，b bj j）R R。并且至少有一個(gè)元素并且至少有一個(gè)元素b b B B在在R R中的兩個(gè)有序?qū)ε贾?，中的兩個(gè)有序?qū)ε贾校╝ ai i，b b） R R和（和（a ai i，b b） R R。 單個(gè)集合上的關(guān)系 定義定義 關(guān)系關(guān)系R AR AA A是：是：自反的自反的， 當(dāng)且僅當(dāng)所有當(dāng)且僅當(dāng)所有a a A A， R R 對稱的對稱的， 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) R R R R 反對稱的反對稱的， 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)、 R a R ab b 傳遞的傳遞的 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)、 R R R R續(xù) 定義 關(guān)

12、系R AA是排序關(guān)系排序關(guān)系，如果R是自反、反對稱和傳遞的 定義 關(guān)系R AA是等價(jià)關(guān)系等價(jià)關(guān)系，如果R是自反、對稱和傳遞的3.4命題邏輯命題邏輯 邏輯操作符邏輯操作符 兩個(gè)值：兩個(gè)值：T T（代表真）和（代表真）和F F（代表假）（代表假） 三種基本邏輯操作符：與三種基本邏輯操作符：與( (合取合取)”)” ”、或或( (析取析取)” )” ” ”和非和非”非是惟一一個(gè)一元（一個(gè)操作數(shù)）邏輯非是惟一一個(gè)一元（一個(gè)操作數(shù)）邏輯操作符，其他都是二元操作符操作符，其他都是二元操作符。pqpq pq p p q pqTT T T F F TTF F T F T FFT F T T T TFF F F T F T邏輯操作定義如下：邏輯操作定義如下： 邏輯表達(dá)式邏輯表達(dá)式 采用邏輯操作運(yùn)算符構(gòu)建邏輯表達(dá)式的采用邏輯操作運(yùn)算符構(gòu)建邏輯表達(dá)式的方式，與使用算術(shù)操作符構(gòu)建代數(shù)表達(dá)方式，與使用算術(shù)操作符構(gòu)建代數(shù)表達(dá)式的方式完全一樣。式的方式完全一樣?？梢允褂美ㄌ?，也可以使用括號，也可以使用優(yōu)先順序可以使用優(yōu)先順序。 邏輯運(yùn)算的優(yōu)先順序是：邏輯運(yùn)算的優(yōu)先順序是：非最先，然后非最先，然后是合取，最后是析取。是合取，最后是析取。例：p pq qpqpqqpqp(pq) (pq) ( qp)( qp)(pq) (pq