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

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

2、空集個空集。如果集合被決策規(guī)則定義為永如果集合被決策規(guī)則定義為永遠失敗，則該集合是空集。遠失敗，則該集合是空集。 維恩圖維恩圖 在維恩圖中，集合被表示為一個圓圈，在維恩圖中，集合被表示為一個圓圈，圓圈中的點表示集合元素圓圈中的點表示集合元素 維恩圖以直觀方式表示各種集合關(guān)系，維恩圖以直觀方式表示各種集合關(guān)系，但存在一些但存在一些問題問題：無限集合、空集等無限集合、空集等U集合操作集合操作 集合基本操作：并、交和補集合基本操作：并、交和補 定義定義 給定集合給定集合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的的補補是集合是集合AA x x：x x 不屬于不屬于A A 。 B B針對針對A A的的相對補相對補是集合是集合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）舉例 給定兩個集合：給定兩個集合： 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），但是 這種差別對于圖論很重要。兩個集合的笛卡兒集 定義 兩個集合A和B的笛卡兒積（又叫叉積），是集合AB：x Ay B 笛卡兒積與運算有直觀的聯(lián)系。集合A的勢是勢是A A中元素數(shù)，用中元素數(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子集劃分 劃分劃分劃分是將一個整體分成小塊，使得所有事物都在劃分是將一個整體分成小塊，使得所有事物都在某個小塊中，不會遺漏某個小塊中，不會遺漏。 定義定義 給定集合給定集合B B，以及，以及B B的一組子集的一組子集A1A1、A2A2、 、AnAn，這些子集是，這些子集是B B的一個劃分，的一個劃分，當(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、測試完備性（未測試）無冗余性（多次測試）無冗余性（多次測試）集合恒等式集合恒等式名稱名稱 表達式表達式等同律等同律 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的一個子集，使的一個子集，使得對于得對于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)對于某個對于某個aiaiA A ，這個集合有時記做這個集合有時記做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)系 定義：給定兩個集合定義：給定兩個集合A A和和B B，關(guān)系，關(guān)系R R是笛卡兒積是笛卡兒積A AB B的一個子集。的一個子集。勢：指集合中的元素個數(shù)

10、勢：指集合中的元素個數(shù) 給定兩個集合給定兩個集合A A和和B B，一個關(guān)系，一個關(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)至少有一個元素，當(dāng)且僅當(dāng)至少有一個元素a aA A在在R R中的兩中的兩個有序?qū)ε贾?，即（個有序?qū)ε贾?，即?a a，b bi i）R R和（和（a a，b bj j）R R 多對多勢多對多勢，當(dāng)且僅當(dāng)至少有一個元素，當(dāng)且僅當(dāng)至少有一個元素a aA A

11、在在R R中的兩中的兩個有序?qū)ε贾?，即（個有序?qū)ε贾?，即?a a，b bi i）R R和（和（a a，b bj j）R R。并且至少有一個元素并且至少有一個元素b b B B在在R R中的兩個有序?qū)ε贾校械膬蓚€有序?qū)ε贾?，（a ai i，b b） R R和（和（a ai i，b b） R R。 單個集合上的關(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是等價關(guān)系等價關(guān)系，如果R是自反、對稱和傳遞的3.4命題邏輯命題邏輯 邏輯操作符邏輯操作符 兩個值：兩個值：T T（代表真）和（代表真）和F F（代表假）（代表假） 三種基本邏輯操作符：與三種基本邏輯操作符：與( (合取合取)”)” ”、或或( (析取析取)” )” ” ”和非和非”非是惟一一個一元（一個操作數(shù)）邏輯非是惟一一個一元（一個操作數(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邏輯操作定義如下：邏輯操作定義如下： 邏輯表達式邏輯表達式 采用邏輯操作運算符構(gòu)建邏輯表達式的采用邏輯操作運算符構(gòu)建邏輯表達式的方式，與使用算術(shù)操作符構(gòu)建代數(shù)表達方式，與使用算術(shù)操作符構(gòu)建代數(shù)表達式的方式完全一樣。式的方式完全一樣?？梢允褂美ㄌ?，也可以使用括號，也可以使用優(yōu)先順序可以使用優(yōu)先順序。 邏輯運算的優(yōu)先順序是：邏輯運算的優(yōu)先順序是：非最先，然后非最先，然后是合取，最后是析取。是合取，最后是析取。例：p pq qpqpqqpqp(pq) (pq) ( qp)( qp)(pq) (pq