第三章测试人员的离散数学优秀课件.ppt

第三章测试人员的离散数学第1页，本讲稿共34页集合论集合论东北大学软件学院东北大学软件学院关关于于集集合合，是是它它使使我我们们能能够够作作为为一一个个单单位位，或或一一个个整整体体引引用多个事物。用多个事物。例如，我们可能要引用正好有例如，我们可能要引用正好有3030天的月份。天的月份。采用集合论表示法可以写为：采用集合论表示法可以写为：M1=4 M1=4月，月，6 6月，月，9 9月，月，1111月月)第2页，本讲稿共34页集合成员关系集合成员关系东北大学软件学院东北大学软件学院集集合合中中的的项项叫叫做做集集合合的的元元素素或或成成员员，这这种种关关系系采采用用符符号号表表示示。这这样样我我们们可可以以有有4 4月月M1M1。如如果果事事物物不不是是集集合合成成员员，则则使使用用符符号号 表示，可以有表示，可以有1212月月 M1 M1 第3页，本讲稿共34页集合的定义东北大学软件学院东北大学软件学院集合有三种方式定义：集合有三种方式定义：简单列出集合的元素；简单列出集合的元素；Y=1812Y=1812，18131813，18141814，20112011，2012 2012 给出辨别规则；给出辨别规则；Y=Y=年：年：18121812年年20122012决策规则定义集合必须是无歧义的。决策规则定义集合必须是无歧义的。N=t N=t：t t是近似三角形是近似三角形 决策规则定义可以解决集合元素很难列出的集合。决策规则定义可以解决集合元素很难列出的集合。S=S=销售：销售：15%15%的佣金率适用于该销售额的佣金率适用于该销售额 通过其他集合构建；通过其他集合构建；第4页，本讲稿共34页空集空集东北大学软件学院东北大学软件学院空空集集采采用用符符号号 表表示示，在在集集合合论论中中占占有有特特殊殊位位置置。空空集集不不包包含含元元素。素。空集是惟一的，即不会有两个空集。空集是惟一的，即不会有两个空集。，都是不同的集合。都是不同的集合。如如果果集集合合被被决决策策规规则则定定义义为为永永远远失失败败，那那么么该该集集合合就就是是空空集集。例例如，如，=年：年：20122012年年18121812第5页，本讲稿共34页维恩图维恩图东北大学软件学院东北大学软件学院在维恩图中，集合被表示为一个圆圈，圆圈中的点表示集合元素。在维恩图中，集合被表示为一个圆圈，圆圈中的点表示集合元素。4月 11月 9月 6月U有有30天的月份集合的维恩图天的月份集合的维恩图第6页，本讲稿共34页集合操作集合操作东北大学软件学院东北大学软件学院集合基本操作：并、交和补。集合基本操作：并、交和补。其他便利的操作：相对补、对称差和笛卡尔积。其他便利的操作：相对补、对称差和笛卡尔积。第7页，本讲稿共34页集合操作定义东北大学软件学院东北大学软件学院假假设设某某个个论论域域空空间间U U包包含含两两个个集集合合A A和和B B。定定义义使使用用来来自自谓谓词词演演算算的的逻逻辑连接符，与辑连接符，与()()、或、或()()、异或、异或()()和非和非()。定义定义 给定集合给定集合A A和和B B，其并是集合其并是集合AB=xAB=x：xAxBxAxB。其交是集合其交是集合AB=xAB=x：xAxBxAxB。A A的补是集合的补是集合A=xA=x：x Ax A。B B针对针对A A的相对补是集合的相对补是集合A-B=xA-B=x：xAxBxAxB。A A和和B B的对称差是集合的对称差是集合A B=xA B=x：xA xBxA xB。第8页，本讲稿共34页基本集合的维恩图基本集合的维恩图东北大学软件学院东北大学软件学院第9页，本讲稿共34页笛卡儿积笛卡儿积 东北大学软件学院东北大学软件学院笛笛卡卡儿儿积积取取决决于于有有序序对对偶偶的的概概念念，即即两两个个元元素素集集合合中中的的元元素素顺顺序序是重要的。无序和有序对偶的表示法一般是：是重要的。无序和有序对偶的表示法一般是：无序对偶：无序对偶：(a(a，b)b)有序对偶：有序对偶：ab 两者的差别是，对于两者的差别是，对于abab，(a (a，b)=(bb)=(b，a)a)，但是，但是 a a 第10页，本讲稿共34页笛卡儿积的定义笛卡儿积的定义东北大学软件学院东北大学软件学院定义定义 两个集合两个集合A A和和B B的笛卡儿积，是集合的笛卡儿积，是集合 AB=x AB=y：xAyBxAyB 举举例例：集集合合A A：(1(1，2 2，3)3)和和B B：ww，x x，y y，z)z)的的笛笛卡卡儿儿积积是是集合：集合：AB AB=,z,2,w，3x，3y，第11页，本讲稿共34页集合的势集合的势东北大学软件学院东北大学软件学院集合集合A A的势是的势是A A中的元素数，采用中的元素数，采用 表示。表示。对于集合对于集合A A和和B B，=AA BAB第12页，本讲稿共34页集合关系集合关系东北大学软件学院东北大学软件学院定义定义 A A是是B B的子集，记做的子集，记做A BA B，当且仅当，当且仅当aAaA=aBaB。A A是是B B的的真真子子集集，记记做做A A B B，当当且且仅仅当当A A BB-A BB-A 。A A和和B B是相等集合，记做是相等集合，记做A=BA=B，当且仅当，当且仅当A B=B AA B=B A。第13页，本讲稿共34页子集划分子集划分东北大学软件学院东北大学软件学院定义定义 给给定定集集合合B，以以及及B的的一一组组子子集集Al、A2、An，这这些子集是些子集是B的一个划分，当且仅当：的一个划分，当且仅当：AlA2 An=B，且，且 ij=AiAj=空集空集划划分分对对测测试试人人员员很很有有用用，因因为为两两个个界界定定性性质质会会产产生生重重要要保保证证：完完备备性性(任任何何事事物物都都在在某某处处)和和无无冗冗余余性。性。第14页，本讲稿共34页集合恒等式集合恒等式东北大学软件学院东北大学软件学院集集合合操操作作和和关关系系合合在在一一起起，会会产产生生一一种种重重要要的的集集合合恒恒等等式式类类，可以用于代数级地简化复杂集合的表示。可以用于代数级地简化复杂集合的表示。名称表达式等同律A=AAU=A支配律AU=UA=幂等律AA=AAA=A求反律(A)=A交换律AB=BAAB=BA结合律A(BC)=(AB)CA(BC)=(AB)C分配律A(BC)=(AB)(AC)A(BC)=(AB)(AC)迪摩根定律(AB)=AB(AB)=AB第15页，本讲稿共34页函数函数东北大学软件学院东北大学软件学院定义定义 给给定定集集合合A A和和B B，函函数数f f是是ABAB的的一一个个子子集集，使使得得a ai i、a aj jAA，b bi i、b bj jBB，f(af(ai i)=b)=bi i，f(af(aj j)=b)=bj j，b bi ibbj j=a=ai iaaj j。函数函数f f的输入是集合的输入是集合A A的元素，的元素，f f的输出是的输出是B B的元素。的元素。第16页，本讲稿共34页定义域和值域定义域和值域东北大学软件学院东北大学软件学院集集合合A A是是函函数数f f的的定定义义域域，集集合合B B是是值值域域。由由于于输输入入和和输输出出具具有有某某种种“自自然然”顺顺序序，因因此此很很容容易易进进一一步步说说函函数数f f是是一一个个有有序序对对偶偶的的集集合合，其其中中第第一一个个元元素素来来自自定定义义域域，第第二二个个元元素素来来自自值值域域。以以下下是是函函数数的两种常见表示法：的两种常见表示法：f f：A-BA-B f AB f AB 第17页，本讲稿共34页函数类型函数类型东北大学软件学院东北大学软件学院首先给出函数首先给出函数f f：A AB B，并且定义集合：，并且定义集合：f(A)=b f(A)=bi i B B：b bi i=f(a=f(ai i)对于某个对于某个a ai i A A 这个集合有时记做这个集合有时记做A A在在f f下的映象。下的映象。定义定义 f f是从是从A A到到B B的上函数，当且仅当的上函数，当且仅当f(A)=Bf(A)=B。f f是是从从A A到到B B的的中中函函数数，当当且且仅仅当当f(A)f(A)B B。(请请注注意意这这里里的真子集的真子集!)!)f f是是从从A A到到B B的的一一对对一一函函数数，当当且且仅仅当当对对于于所所有有a ai i、a aj j A A，a ai i aaj j=f(a=f(ai i)f(a)f(aj j)。f f是从是从A A到到B B的多对一函数，当且仅当存在的多对一函数，当且仅当存在a ai i、a aj j A A，a ai i aaj j 使得使得f(af(ai i)=f(a)=f(aj j)。第18页，本讲稿共34页函数合成函数合成东北大学软件学院东北大学软件学院假假设设我我们们有有集集合合和和函函数数，使使得得一一个个函函数数的的值值域域是是另另一一个个函函数数的的定定义域：义域：f：A B g：B C h：C D 如如果果出出现现这这种种情情况况，则则可可以以合合成成函函数数。为为此此，设设引引用用集集合合定定义义域域和和值值域域的的特特定定元元素素a A、b B、c C、d D，并并假假设设f(a)=b、g(b)=c和和h(c)=d，则函数，则函数g和和f的合成为：的合成为：h g f(a)=h(g(f(a)=h(g(b)=h(c)=d第19页，本讲稿共34页关系关系东北大学软件学院东北大学软件学院 函数是关系的一种特例：两者都是某个笛卡儿积的子集。函数是关系的一种特例：两者都是某个笛卡儿积的子集。但是对于函数，定义域元素不能与多个值域元素关联但是对于函数，定义域元素不能与多个值域元素关联 并不是所有关系都严格地是函数。并不是所有关系都严格地是函数。第20页，本讲稿共34页集合之间的关系集合之间的关系东北大学软件学院东北大学软件学院 定义定义 给定两个集合给定两个集合A A和和B B，关系，关系R R是笛卡儿积是笛卡儿积AXBAXB的一个子集。的一个子集。有有两两种种表表示示法法很很常常见见，如如果果希希望望描描述述整整个个关关系系，则则通通常常只只写写R(AXBR(AXB。对对于于特特定定元元素素a aj j A A、b bj j B B，我我们们记记做做a ai i R R b bi i。第21页，本讲稿共34页关系关系R的势的势东北大学软件学院东北大学软件学院定义定义给定两个集合给定两个集合A A和和B B，一个关系，一个关系R AxBR AxB，关系，关系R R的势是：的势是：一对一势，当且仅当一对一势，当且仅当R R是是A A到到B B的一对一函数。的一对一函数。多对一势，当且仅当多对一势，当且仅当R R是是A A到到B B的多对一函数。的多对一函数。一一对对多多势势，当当且且仅仅当当至至少少有有一一个个元元素素aAaA在在R R中中的的两两个个有有序序对对偶中偶中(a(a，b bj j)R)R和和(a(a，b bi i)R)R 多多对对多多势势，当当且且仅仅当当至至少少有有一一个个元元素素a a A A在在R R中中的的两两个个有有序序对对偶偶中中，即即(a(a，b bj j)R R和和(a(a，b bj j)R R。并并且且至至少少有有一一个个元元素素b b B B在在R R中中的的两两个个有有序序对对偶偶中中，(a(ai i，b)b)R R和和(a(aj j，b)Rb)R。第22页，本讲稿共34页函数参与的概念函数参与的概念东北大学软件学院东北大学软件学院函函数数映映射射到到值值域域上上或或值值域域中中之之间间的的差差别别可可以以与与关关系系类类比比，这这就就是是参与概念。参与概念。定义定义 给定两个集合给定两个集合A A和和B B，一个关系，一个关系R AXBR AXB，关系，关系R R的参与是：的参与是：全全参参与与，当当且且仅仅当当A A中中的的所所有有元元素素都都在在R R的的某某个个有有序序对对偶偶中。中。部分参与，当且仅当部分参与，当且仅当A A中有元素不在中有元素不在R R的有序对偶中。的有序对偶中。上参与，当且仅当上参与，当且仅当B B中的所有元素都在中的所有元素都在R R的某个有序对偶中。的某个有序对偶中。中参与，当且仅当中参与，当且仅当B B中有元素不在中有元素不在R R的有序对偶中。的有序对偶中。第23页，本讲稿共34页单个集合上的关系单个集合上的关系东北大学软件学院东北大学软件学院设设A A是是一一个个集集合合，设设R R AXAAXA是是定定义义在在A A上上的的一一个个关关系系，aa、ab、ba、bc、aE cE R R。关关系系具具有有四四个个特殊属性：特殊属性：定义定义 关系关系R AXAR AXA是：是：自反的，当且仅当所有自反的，当且仅当所有aAaA，a Ra R。对称的，当且仅当对称的，当且仅当a R=R=Ra R。反对称的，当且仅当反对称的，当且仅当ab、b R=a=ba R=a=b。传递的，当且仅当传递的，当且仅当ab、b R=R=Rc R。第24页，本讲稿共34页排序关系和等价关系排序关系和等价关系东北大学软件学院东北大学软件学院定义定义 关系关系R AXAR AXA是排序关系，如果是排序关系，如果R R是自反、反对称和传递的。是自反、反对称和传递的。定义定义 关系关系R AXAR AXA是等价关系，如果是等价关系，如果R R是自反、对称和传递的。是自反、对称和传递的。第25页，本讲稿共34页命题逻辑命题逻辑东北大学软件学院东北大学软件学院命题是要么真要么假的句子，我们叫做命题的真值。命题是要么真要么假的句子，我们叫做命题的真值。命命题题是是无无歧歧义义的的：给给定定一一个个命命题题，总总是是能能够够确确定定它它是是真真还还是假。是假。第26页，本讲稿共34页逻辑操作符逻辑操作符东北大学软件学院东北大学软件学院 逻逻辑辑操操作作符符(又又叫叫做做逻逻辑辑连连接接符符或或操操作作)根根据据它它们们对对命命题题真真值值的的作作用用来来定定义义。也也就就是是说说，只只使使用用两两个个值值：T(T(代代表表真真)和和F(F(代表假代表假)。三三种种基基本本逻逻辑辑操操作作符符是是与与()()、或或()()和和非非()。这这些些操操作作符有时又叫做合取、析取和非。符有时又叫做合取、析取和非。pqp qp qp pTTTTFTFFTFFTFTTFFFFT第27页，本讲稿共34页逻辑操作符逻辑操作符东北大学软件学院东北大学软件学院 异或：只有当一个命题为真时，异或为真。异或：只有当一个命题为真时，异或为真。IF-THEN IF-THEN连接（连接（）pqp qp qTTFTTFTFFTTTFFFT第28页，本讲稿共34页逻辑表达式逻辑表达式东北大学软件学院东北大学软件学院pqp qqq pp(p q)q)(q pp)(p q)q)(q pp)TTTTTFTFFTFTFTTFFTFFTTTF第29页，本讲稿共34页逻辑等价逻辑等价东北大学软件学院东北大学软件学院定定义义 两两个个命命题题p p和和q q是是等等价价的的(记记做做p pq)q)，当当且且仅仅当当其其真值表相同。真值表相同。定义定义 永远为真的命题是重言式，永远为假的命题是矛盾式。永远为真的命题是重言式，永远为假的命题是矛盾式。第30页，本讲稿共34页逻辑等价逻辑等价东北大学软件学院东北大学软件学院定律表达式等同律pTp pF p支配律pT T pF F幂等律pp p pp p求反律(p)p交换律pq qp pq qp结合律p(qr)(pq)rp(qr)(pq)r分配律p(qr)(pq)(pr)p(qr)(pq)(pr)迪摩根定律(pq)pq(pq)pq第31页，本讲稿共34页概率论概率论东北大学软件学院东北大学软件学院 定定义义 结结果果可可能能性性相相等等的的有有限限样样本本空空间间S S中中的的事事件件E E的的概概率率，是是p(E)=/p(E)=/。定定义义 命命题题p p的的真真值值集集合合T T记记做做T(p)T(p)，是是p p为为真真的的论论域域空空间间U U中中的所有元素的集合。的所有元素的集合。定义定义 命题命题p p为真的概率记做为真的概率记做Pr(p)=/Pr(p)=/。EST(p)U第32页，本讲稿共34页概率论概率论东北大学软件学院东北大学软件学院 给定论域空间，命题给定论域空间，命题p p和和q q，真值集合是，真值集合是T(p)T(p)和和T(q)T(q)：Pr(Pr(p)=1Pr(p)p)=1Pr(p)Pr(p Pr(pq)=Pr(p)X Pr(q)q)=Pr(p)X Pr(q)Pr(pVq)=Pr(p)+Pr(q)-Pr(p Pr(pVq)=Pr(p)+Pr(q)-Pr(p q)q)这这些些事事实实，结结合合集集合合论论和和命命题题恒恒等等式式表表，为为操操作作概概率率表达式提供了强有力的代数能力。表达式提供了强有力的代数能力。第33页，本讲稿共34页总结总结东北大学软件学院东北大学软件学院 集合集合 函数函数 关系关系 命题逻辑命题逻辑 概率论概率论第34页，本讲稿共34页