Chap3-离散数学共82页PPT资料

软件测试—数学背景2020/3/61软件测试华中科技大学软件学院WuJianjie2019.11.软件测试—数学背景2020/3/62测试人员的离散数学测试本身要进行数学描述和分析。即以数学方法为工具，使得测试人员变得严格、精确和高效，并改进测试。对离散数学的非正式讨论。下一章学习图论。离散数学更适用于功能性测试，而图论更适用于结构性测试。软件测试—数学背景2020/3/63测试人员的离散数学集合论二元关系函数命题逻辑概率论软件测试—数学背景2020/3/641集合论集合的基本概念集合的基本运算集合的定义方式维恩图有限集合的元素数目两集合之间的关系集合的划分小结软件测试—数学背景2020/3/651集合论—基本概念不能精确定义耿素云徐洁磬对于给定的集合和事物，可判定这个特定事物是否属于该集合，若属于，称它为这个集合的元素集合指的是一些可确定的可分辨的事物构成的整体。一个集合是指所研究对象的全体。每个对象是该集合中的一个元素。软件测试—数学背景2020/3/661集合论—基本概念集合通常用大写英文字母标记，集合中的元素通常用小写英文字母标记全体26个英文字母的集合，S1={a,b,c,d,…}二维坐标平面上所有点的集合，S2={(0,0),(0.2,1.8),…}华中科技大学软件学院全体教职工的集合S3={陈传波，陈业美，肖来元，。。。}或记做：S3={M,F}，M是所有男性教职工的集合，M={陈传波，陈业美。。。}，F是所有女性教职工的集合，F={蒋清荣，石桂林。。。}SMFMAMBFBFA陈传波牛慧娟蒋清荣肖来元MA,MB,FA,FB分别表示40岁以下和以上男性教职工、30岁以下和以上女性教职工的集合软件测试—数学背景2020/3/671集合论—基本概念任意一个元素要么属于某一个集合，要么不属于某一个集合，二者必居其一。集合元素的特点集合元素之间彼此相异，且没有次序关系。几种特定集合的符号表示N：自然数集合Z：整数集合（也有的书上用I表示，但一般用I表示区间[0,1]）Q：有理数集合R：实数集合C：复数集合{3,4,5}{3,4,4,4,5}{5,3,4}软件测试—数学背景2020/3/681集合论—定义方式集合的定义方式有三种列举法：列举已知集合中的所有元素，元素之间用逗号隔开，S3={陈传波，陈业美，肖来元，。。。},NextDate的年份集合Y={1812,1813,…,2019}描述法：给出判别规则，利用元素特性刻画的方法表示，适用于元素很多或无穷的情况，S={人|他是华中科技大学软件学院姓陈的教职工之一}={陈传波，陈业美，陈长清},NextDate的年份集合Y={年|1812=年=2019}递归指定集合：通过其他集合构建，通常是通过计算规则定义集合中的元素。例如：设，则有01111,1,,1iiiaaaaai{|0}{1,1,2,3,5,8,}kSak软件测试—数学背景2020/3/691集合论—定义方式用描述法定义集合的两点说明判别规则必须无歧义，使得定义清晰。有可能在逻辑上太复杂，使得客户被带有谓词演算量词和的语句弄糊涂。常常与自引用有关。S＝{华中科技大学软件学院长的胖的男性教职工}，应改为S＝{华中科技大学软件学院的男性教职工，且其体重超过其标准体重20％以上}，标准体重（按公斤计算）由其身高（按厘米计算）减去100所得到。如Seville的理发师“是为所有不刮自己胡子的人刮胡子的人”软件测试—数学背景2020/3/6101集合论—定义方式集合的4个性质确定性。对一个具体集合来说，其元素是确定的，一个元素或在此集合中，或不在此集合中，两者必居其一。无重复性。集合中元素彼此不同，没有重复的元素，这与后面图论中涉及的多重集合不同，那里因为特殊的原因允许有重复的元素。集合元素的无次序性。集合元素是抽象的，甚至可以是集合。如NextDate的年份集合Y={Y1,Y2}，Y1={闰年|1812=闰年=2019}，Y2={平年|1812=平年=2019}软件测试—数学背景2020/3/6111集合论—集合之间的关系子集真子集集合相等空集全集幂集设A,B为两个集合，若B中每个元素都是A中的元素，称B为A的子集合，简称子集，或B被A包含，或A包含B，记做。符号化表示：BA()BAxxBxA设A,B为集合，如果且，则称A与B相等，记做A=B。符号化表示为：。如果二者不相等，记做。BABAABABBAAB设A,B为集合，若且，则B是A的真子集，记做。BAABBA真子集集合相等有限/无限集软件测试—数学背景2020/3/6121集合论—集合之间的关系子集真子集集合相等空集全集幂集有限/无限集空集是客观存在的。不含任何元素的集合称空集，记做。2{|10}SxxRx定理：空集是一切集合的子集。如果集合被决策规则定义为永远失败，则该集合是空集＝华中科技大学软件学院所有年龄低于20岁的教职工。软件测试—数学背景2020/3/6131集合论—集合之间的关系子集真子集集合相等空集全集幂集有限/无限集如果一个集合包含了我们所考虑的每一个集合，则称该集合为全集。在一个具体问题中，如果所涉及的集合都是某个集合的子集，则称该集合为全集，记做E或U。全集是相对性概念。研究华中科技大学：其全体教职工为全集，研究武汉高校：则武汉高校全体教职工为全集。软件测试—数学背景2020/3/6141集合论—集合之间的关系子集真子集集合相等空集全集幂集有限/无限集设A为集合，则A的全体子集构成的集合称为A的幂集，记做P(A)，符号化表示为：(){|}PAxxA软件测试—数学背景2020/3/615子集真子集集合相等空集全集幂集有限/无限集1集合论—集合之间的关系如果一个集合的元素有限，称为有限集，反之是无限集。设A是有限集，则A中元素的数目用n(A)或|A|表示，称为集合的基数或集合的势。软件测试—数学背景2020/3/6161集合论—维恩图MAMAFU华中科技大学软件学院全体教职工集合的维恩图1月U12月3月5月NextDate中有31天的月份集合的维恩图7月8月10月M:所有男性教职工的集合F:所有女性教职工的集合A:所有年龄大于40岁的教职工集合MA:所有年龄大于40岁的男性教职工集合软件测试—数学背景2020/3/617为特定元素加标签1集合论—维恩图存在的问题如何表示有限和无限集合如何显示集合或集合的一部分是空集对空集部分加阴影，或给出图例，表明阴影部分的实际含义只是为突出所感兴趣的部分软件测试—数学背景2020/3/6181集合论—基本运算A和B的并A和B的交A的补A和B的差A和B的对称差设A、B是两个集合，则{|}ABxxAxBABA和B的并{|}ABxxAxBA和B的交软件测试—数学背景2020/3/6191集合论—基本运算A和B的并A和B的交A的补A和B的差A和B的对称差设A、B是两个集合，则{|}AAxxUxAAB{|}ABxxAxBA的补A和B的差软件测试—数学背景2020/3/6201集合论—基本运算A和B的并A和B的交A的补A和B的差A和B的对称差设A、B是两个集合，则ABA和B的对称差{|()()}ABxxAxBxBxA软件测试—数学背景2020/3/6211集合论—基本运算对任意两集合A和B()()()()ABABBAABAB并、交运算可推广到n个集合的情形121211,nnininiiAAAAAAAA并、交运算可推广到无穷集合的情形00{|,},{|,}ijjjjJjJAxjJxAAxjJxA若A和B无公共元素，则，称它们是分离的AB软件测试—数学背景2020/3/6221集合论—基本运算等同律：支配律：幂等律：求反律：交换律：结合律：分配律：迪摩根定律：吸收律：取补律：集合运算的恒等式(),()AABAAABA,,,AAUAAUU软件测试—数学背景2020/3/6231集合论—基本运算包含对称差的恒等式()()ABCABCABBA,,,AAAAAUAAAU()()()ABCABAC()()()ABCABAC不一定成立运算优先权取补交并括号软件测试—数学背景2020/3/6241集合论—元素数目含有n个元素的集合简称n元素，它的含有m个(m=n)元素的子集称为它的m元素子集，且n元素有2n个子集。对于幂集，若A是有限集，其基数为|A|，则|P(A)|=2|A|。如果A和B是分离的有限集，则有。如果A和B是有限集，则有。对于任意三个有限集合A、B、C，有||||||ABAB||||||||ABABAB||||||||||||||||ABCABCABACBCABC如何计算集合的元素数目？软件测试—数学背景2020/3/6251集合论—元素数目抽屉原理：把n个物体放入m个盒子里，则至少有一个盒子里至少有个物体包含排斥原理：设S为有穷集，P1,P2,…,Pm是m条性质，S中的任何一个元素x对于性质Pi(I=1,2,…m,m=2)具有或者不具有，两种情况必居其一，令Ai表示S中具有性质Pi的元素构成的集合，则S中不具有性质P1,P2,…,Pm的元素数是有限集合元素数目的计算可采用维恩图进行求取，也可利用包含排斥定理求取11nm1211||||||||mmiijiijmAAASAAA121||(1)||mijkmijkmAAAAAA软件测试—数学背景2020/3/6261集合论—划分划分的含义是将整体分成小块，使得所有事物都在某个小块中，不会遗漏。1234给定集合B以及B的一组子集A1,A2,…,An，这些子集是B的一个划分，当且仅当：，且，这样的一个划分是一组子集：，所以我们常把单个子集看作是划分的元素。12AAAnBijijAA{|,}iiiAABA软件测试—数学背景2020/3/6271集合论—划分对于华中科技大学软件学院全体教职工，有4种划分方法：所有男性教职工和所有女性教职工所有年龄大于四十岁的教职工和所有年龄不大于四十岁的教职工所有教工和所有职工所有办公室在二楼的教职工、所有办公室在三楼的教职工和所有办公室在四楼的教职工软件测试—数学背景2020/3/6281集合论—划分划分的含义是将整体分成小块，使得所有事物都在某个小块中，不会遗漏。1234给定集合B以及B的一组子集A1,A2,…,An，这些子集是B的一个划分，当且仅当：，且，这样的一个划分是一组子集：，所以我们常把单个子集看作是划分的元素。12AAAnBijijAA{|,}iiiAABA完备性无冗余性如何找出合适的划分？而功能性测试的固有弱点是漏洞和冗余性软件测试—数学背景2020/3/6291集合论—划分对于三角形例子，有3种划分方法：三角形和非三角形等边三角形、等腰三角形、不等边三角形和非三角形等边三角形、等腰三角形、不等边三角形、直角三角形和非三角形a=3b=4c=5软件测试—数学背景2020/3/6301集合论—小结基本要求掌握集合、子集、全集、空集等概念，熟悉常用集合表示方法，能用维恩图表示集合，能判定元素与集合、集合与集合之间的关系。懂得两集合间相等关系和包含关系的定义和性质。掌握集合的五种基本运算：并、交、补、差和对称差的定义。了解幂集定义及计算有限集的幂集所含元素个数、所使用的方法和思想。了解抽屉原理和简单情形的容斥原理。理解划分的定义。软件测试—数学背景2020/3/6311集合论—小结疑难点解析集合中无重复元素。注意维恩图只是对某些集合之间的关系及运算结果给出的一种直观而形象的示意性的表示，不能用于证明集合等式及包含关系。注意空集和集合本身一定在该集合的