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

第三章測試人員的離散數(shù)學(xué)第1頁，共34頁，2023年，2月20日，星期三集合論東北大學(xué)軟件學(xué)院關(guān)于集合，是它使我們能夠作為一個單位，或一個整體引用多個事物。例如，我們可能要引用正好有30天的月份。采用集合論表示法可以寫為：M1={4月，6月，9月，11月)第2頁，共34頁，2023年，2月20日，星期三集合成員關(guān)系東北大學(xué)軟件學(xué)院集合中的項(xiàng)叫做集合的元素或成員，這種關(guān)系采用符號∈表示。這樣我們可以有4月∈M1。如果事物不是集合成員，則使用符號表示，可以有12月M1第3頁，共34頁，2023年，2月20日，星期三集合的定義東北大學(xué)軟件學(xué)院集合有三種方式定義：簡單列出集合的元素； Y={1812，1813，1814，……，2011，2012}給出辨別規(guī)則； Y={年：1812≤年≤2012}

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

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

決策規(guī)則定義可以解決集合元素很難列出的集合。S={銷售：15%的傭金率適用于該銷售額}通過其他集合構(gòu)建；

第4頁，共34頁，2023年，2月20日，星期三空集東北大學(xué)軟件學(xué)院空集采用符號表示，在集合論中占有特殊位置?？占话亍？占俏┮坏模床粫袃蓚€空集。，{}，{{}}都是不同的集合。

如果集合被決策規(guī)則定義為永遠(yuǎn)失敗，那么該集合就是空集。例如，={年：2012≤年≤1812}第5頁，共34頁，2023年，2月20日，星期三維恩圖東北大學(xué)軟件學(xué)院在維恩圖中，集合被表示為一個圓圈，圓圈中的點(diǎn)表示集合元素。

4月11月9月6月U有30天的月份集合的維恩圖第6頁，共34頁，2023年，2月20日，星期三集合操作東北大學(xué)軟件學(xué)院集合基本操作：并、交和補(bǔ)。其他便利的操作：相對補(bǔ)、對稱差和笛卡爾積。

第7頁，共34頁，2023年，2月20日，星期三集合操作定義東北大學(xué)軟件學(xué)院假設(shè)某個論域空間U包含兩個集合A和B。定義使用來自謂詞演算的邏輯連接符，與(∧)、或(∨)、異或(⊕)和非(﹁)。定義給定集合A和B，其并是集合A∪B={x：x∈A∨x∈B}。其交是集合A∩B={x：x∈A∧x∈B}。A的補(bǔ)是集合A’={x：xA}。B針對A的相對補(bǔ)是集合A-B={x：x∈A∧x∈B}。A和B的對稱差是集合A⊕B={x：x∈A⊕x∈B}。第8頁，共34頁，2023年，2月20日，星期三基本集合的維恩圖東北大學(xué)軟件學(xué)院第9頁，共34頁，2023年，2月20日，星期三笛卡兒積

東北大學(xué)軟件學(xué)院笛卡兒積取決于有序?qū)ε嫉母拍?，即兩個元素集合中的元素順序是重要的。無序和有序?qū)ε嫉谋硎痉ㄒ话闶牵簾o序?qū)ε迹?a，b)有序?qū)ε迹?lt;a，b>兩者的差別是，對于a≠b，(a，b)=(b，a)，但是<a，b>≠<b，a>

第10頁，共34頁，2023年，2月20日，星期三笛卡兒積的定義東北大學(xué)軟件學(xué)院定義兩個集合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>}

第11頁，共34頁，2023年，2月20日，星期三集合的勢東北大學(xué)軟件學(xué)院集合A的勢是A中的元素?cái)?shù)，采用表示。對于集合A和B，=×AA×BAB第12頁，共34頁，2023年，2月20日，星期三集合關(guān)系東北大學(xué)軟件學(xué)院定義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。第13頁，共34頁，2023年，2月20日，星期三子集劃分東北大學(xué)軟件學(xué)院定義給定集合B，以及B的一組子集Al、A2、……、An，這些子集是B的一個劃分，當(dāng)且僅當(dāng)：Al∪A2∪…∪An=B，且i≠j=>Ai∩Aj=空集劃分對測試人員很有用，因?yàn)閮蓚€界定性質(zhì)會產(chǎn)生重要保證：完備性(任何事物都在某處)和無冗余性。

第14頁，共34頁，2023年，2月20日，星期三集合恒等式東北大學(xué)軟件學(xué)院集合操作和關(guān)系合在一起，會產(chǎn)生一種重要的集合恒等式類，可以用于代數(shù)級地簡化復(fù)雜集合的表示。

名稱表達(dá)式等同律A∪=AA∩U=A支配律A∪U=UA∩=冪等律A∪A=AA∩A=A求反律(A’)’=A交換律A∪B=B∪AA∩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’第15頁，共34頁，2023年，2月20日，星期三函數(shù)東北大學(xué)軟件學(xué)院定義給定集合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的元素。

第16頁，共34頁，2023年，2月20日，星期三定義域和值域東北大學(xué)軟件學(xué)院集合A是函數(shù)f的定義域，集合B是值域。由于輸入和輸出具有某種“自然”順序，因此很容易進(jìn)一步說函數(shù)f是一個有序?qū)ε嫉募希渲械谝粋€元素來自定義域，第二個元素來自值域。以下是函數(shù)的兩種常見表示法：f：A->BfA×B

第17頁，共34頁，2023年，2月20日，星期三函數(shù)類型東北大學(xué)軟件學(xué)院首先給出函數(shù)f：AB，并且定義集合：f(A)={bi∈B：bi=f(ai)對于某個ai∈A}這個集合有時記做A在f下的映象。定義f是從A到B的上函數(shù)，當(dāng)且僅當(dāng)f(A)=B。f是從A到B的中函數(shù)，當(dāng)且僅當(dāng)f(A)B。(請注意這里的真子集!)f是從A到B的一對一函數(shù)，當(dāng)且僅當(dāng)對于所有ai、aj∈A，ai≠aj==>f(ai)≠f(aj)。f是從A到B的多對一函數(shù)，當(dāng)且僅當(dāng)存在ai、aj∈A，ai≠aj使得f(ai)=f(aj)。第18頁，共34頁，2023年，2月20日，星期三函數(shù)合成東北大學(xué)軟件學(xué)院假設(shè)我們有集合和函數(shù)，使得一個函數(shù)的值域是另一個函數(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第19頁，共34頁，2023年，2月20日，星期三關(guān)系東北大學(xué)軟件學(xué)院函數(shù)是關(guān)系的一種特例：兩者都是某個笛卡兒積的子集。但是對于函數(shù)，定義域元素不能與多個值域元素關(guān)聯(lián)并不是所有關(guān)系都嚴(yán)格地是函數(shù)。第20頁，共34頁，2023年，2月20日，星期三集合之間的關(guān)系東北大學(xué)軟件學(xué)院定義給定兩個集合A和B，關(guān)系R是笛卡兒積AXB的一個子集。

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

第21頁，共34頁，2023年，2月20日，星期三關(guān)系R的勢東北大學(xué)軟件學(xué)院定義給定兩個集合A和B，一個關(guān)系RAxB，關(guān)系R的勢是：一對一勢，當(dāng)且僅當(dāng)R是A到B的一對一函數(shù)。多對一勢，當(dāng)且僅當(dāng)R是A到B的多對一函數(shù)。一對多勢，當(dāng)且僅當(dāng)至少有一個元素a∈A在R中的兩個有序?qū)ε贾?a，bj)∈R和(a，bi)∈R多對多勢，當(dāng)且僅當(dāng)至少有一個元素a∈A在R中的兩個有序?qū)ε贾?，?a，bj)∈R和(a，bj)∈R。并且至少有一個元素b∈B在R中的兩個有序?qū)ε贾校?ai，b)∈R和(aj，b)∈R。第22頁，共34頁，2023年，2月20日，星期三函數(shù)參與的概念東北大學(xué)軟件學(xué)院函數(shù)映射到值域上或值域中之間的差別可以與關(guān)系類比，這就是參與概念。定義給定兩個集合A和B，一個關(guān)系RAXB，關(guān)系R的參與是：全參與，當(dāng)且僅當(dāng)A中的所有元素都在R的某個有序?qū)ε贾?。部分參與，當(dāng)且僅當(dāng)A中有元素不在R的有序?qū)ε贾小Ｉ蠀⑴c，當(dāng)且僅當(dāng)B中的所有元素都在R的某個有序?qū)ε贾?。中參與，當(dāng)且僅當(dāng)B中有元素不在R的有序?qū)ε贾小５?3頁，共34頁，2023年，2月20日，星期三單個集合上的關(guān)系東北大學(xué)軟件學(xué)院設(shè)A是一個集合，設(shè)RAXA是定義在A上的一個關(guān)系，<a，a>、<a，b>、<b，a>、<b，c>、<a，c>ER。關(guān)系具有四個特殊屬性：定義關(guān)系RAXA是：自反的，當(dāng)且僅當(dāng)所有a∈A，<a，a>∈R。對稱的，當(dāng)且僅當(dāng)<a，b>∈R=><b，a>∈R。反對稱的，當(dāng)且僅當(dāng)<a，b>、<b，a>∈R=>a=b。傳遞的，當(dāng)且僅當(dāng)<a，b>、<b，c>∈R=><a，c>∈R。

第24頁，共34頁，2023年，2月20日，星期三排序關(guān)系和等價(jià)關(guān)系東北大學(xué)軟件學(xué)院定義

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

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

第25頁，共34頁，2023年，2月20日，星期三命題邏輯東北大學(xué)軟件學(xué)院命題是要么真要么假的句子，我們叫做命題的真值。命題是無歧義的：給定一個命題，總是能夠確定它是真還是假。

第26頁，共34頁，2023年，2月20日，星期三邏輯操作符東北大學(xué)軟件學(xué)院

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

pqp∧qp∨q﹁pTTTTFTFFTFFTFTTFFFFT第27頁，共34頁，2023年，2月20日，星期三邏輯操作符東北大學(xué)軟件學(xué)院異或：只有當(dāng)一個命題為真時，異或?yàn)檎?。IF-THEN連接（→）pqp⊕qp→qTTFTTFTFFTTTFFFT第28頁，共34頁，2023年，2月20日，星期三邏輯表達(dá)式東北大學(xué)軟件學(xué)院pqp→qq→p(p→q)∧(q→p)﹁(p→q)∧(q→p)TTTTTFTFFTFTFTTFFTFFTTTF第29頁，共34頁，2023年，2月20日，星期三邏輯等價(jià)東北大學(xué)軟件學(xué)院定義兩個命題p和q是等價(jià)的(記做pq)，當(dāng)且僅當(dāng)其真值表相同。定義永遠(yuǎn)為真的命題是重言式，永遠(yuǎn)為假的命題是矛盾式。

第30頁，共34頁，2023年，2月20日，星期三邏輯等價(jià)東北大學(xué)軟件學(xué)院定律表達(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第31頁，共34頁，2023年，2月20日，星期三概率論東北大學(xué)軟件學(xué)院

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

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

E