测试人员的离散数学

1、Software Testing 软件测试Software Testing 第第3章章 测试人员的离散数学测试人员的离散数学学习目标 集合论（掌握） 函数（了解） 关系（了解） 命题逻辑（掌握）3.1集合论集合：作为一个单位，或一个整体引用多个事物。 集合成员关系集合中的项叫做集合的元素或成员，这种关系采用符号表示。集合定义集合定义简单列出集合的元素简单列出集合的元素给出辨别规则给出辨别规则通过其他集合构建通过其他集合构建 无歧义定义清晰无歧义定义清晰很难列举很难列举空集空集空集采用符号空集采用符号表示表示 。空集不。空集不包含元素。包含元素。空集空集是惟一的，即不会有两是惟一的，即不会有两个

2、空集个空集。如果集合被决策规则定义为永如果集合被决策规则定义为永远失败，则该集合是空集。远失败，则该集合是空集。 维恩图维恩图 在维恩图中，集合被表示为一个圆圈，在维恩图中，集合被表示为一个圆圈，圆圈中的点表示集合元素圆圈中的点表示集合元素 维恩图以直观方式表示各种集合关系，维恩图以直观方式表示各种集合关系，但存在一些但存在一些问题问题：无限集合、空集等无限集合、空集等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。 无序和有序对偶 无序和有序对偶的表示法一般是： 无序对偶：（a，b） 有序对偶： 两者的差别是，对于ab， （a，b）（ b，a），但是 这种差别对于图论很重要。两个集合的笛卡儿集 定义 两个集合A和B的笛卡儿积（又叫叉积），是集合AB：x Ay B 笛卡儿积与运算有直观的联系。集合A的势是势是A A中元素数，用中元素数，用|A|A|表示表示，对于集合A和B , |AB|=|A|B|。维恩图不能显示笛卡儿积维恩图不能显示笛卡儿积集合关系 定义定义 A A是是B B的的子集子集，记做，记做A BA B， 当且仅当当且仅当a a Aa Aa B B A A是是B B的的

5、真子集真子集，记做，记做A BA B， 当且仅当当且仅当A BA BB BAA A A和和B B是是相等集合相等集合，记做，记做A AB B， 当且仅当当且仅当A BA BB AB A子集划分 划分划分划分是将一个整体分成小块，使得所有事物都在划分是将一个整体分成小块，使得所有事物都在某个小块中，不会遗漏某个小块中，不会遗漏。 定义定义 给定集合给定集合B B，以及，以及B B的一组子集的一组子集A1A1、A2A2、 、AnAn，这些子集是，这些子集是B B的一个划分，的一个划分，当且仅当：当且仅当： 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结合律结合律 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 函数函数 函数是软件开发和测试的核心概念函数是软件开发和测试的核心概念函数定义函数定义给定集合给定集合A A和和B B，函数，函数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 函数映射：给出函数函数映射：给出函数f f：ABAB，并且定义，并且定义集合：集合： f(A) f(A) bi biB B：bibif(

8、ai)f(ai)对于某个对于某个aiaiA A ，这个集合有时记做这个集合有时记做A A在在f f下的映象。下的映象。函数类型 类型定义：类型定义： f f是从是从A A到到B B的的上函数上函数，当且仅当，当且仅当f f（A A）B B f f是从是从A A到到B B的的中函数中函数，当且仅当，当且仅当f f（A A） B B f f是从是从A A到到B B的的一对一函数一对一函数，当且仅当对于所有，当且仅当对于所有aiai、ajajA A，aiaj faiaj f（aiai） f f（ajaj）。）。 f f是从是从A A到到B B的的多对一函数多对一函数，当且仅当存在，当且仅当存在aia

9、i、aj aj A A，aiajaiaj使得使得f f（aiai） f f（ajaj）。）。 函数合成 设引用集合定义域和值域的特定元素a A、bB、cC、dD，并假设f(a) b、g(b)c和h(c) d，则函数g和f的合成为： h g f（a） h（g（f（a） h（g（b） h（c） dfgfgBabcabbbc因果流因果流非因果流非因果流函数合成函数合成3.3关系关系 函数是关系的一种特例函数是关系的一种特例 集合之间的关系集合之间的关系 定义：给定两个集合定义：给定两个集合A A和和B B，关系，关系R R是笛卡儿积是笛卡儿积A AB B的一个子集。的一个子集。势：指集合中的元素个数

10、势：指集合中的元素个数 给定两个集合给定两个集合A A和和B B，一个关系，一个关系R AR AB B，关，关系系R R的势是：的势是： 一对一势一对一势，当且仅当，当且仅当R R是是A A到到B B的一对一函数。的一对一函数。 多对一势多对一势，当且仅当，当且仅当R R是是A A到到B B的多对一函数。的多对一函数。 一对多势一对多势，当且仅当至少有一个元素，当且仅当至少有一个元素a aA A在在R R中的两中的两个有序对偶中，即（个有序对偶中，即（ a a，b bi i）R R和（和（a a，b bj j）R R 多对多势多对多势，当且仅当至少有一个元素，当且仅当至少有一个元素a aA A

11、在在R R中的两中的两个有序对偶中，即（个有序对偶中，即（ a a，b bi i）R R和（和（a a，b bj j）R R。并且至少有一个元素并且至少有一个元素b b B B在在R R中的两个有序对偶中，中的两个有序对偶中，（a ai i，b b） R R和（和（a ai i，b b） R R。 单个集合上的关系 定义定义 关系关系R AR AA A是：是：自反的自反的， 当且仅当所有当且仅当所有a a A A， R R 对称的对称的， 当且仅当当且仅当 R R R R 反对称的反对称的， 当且仅当当且仅当、 R a R ab b 传递的传递的 当且仅当当且仅当、 R R R R续 定义 关

12、系R AA是排序关系排序关系，如果R是自反、反对称和传递的 定义 关系R AA是等价关系等价关系，如果R是自反、对称和传递的3.4命题逻辑命题逻辑 逻辑操作符逻辑操作符 两个值：两个值：T T（代表真）和（代表真）和F F（代表假）（代表假） 三种基本逻辑操作符：与三种基本逻辑操作符：与( (合取合取)”)” ”、或或( (析取析取)” )” ” ”和非和非”非是惟一一个一元（一个操作数）逻辑非是惟一一个一元（一个操作数）逻辑操作符，其他都是二元操作符操作符，其他都是二元操作符。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逻辑操作定义如下：逻辑操作定义如下： 逻辑表达式逻辑表达式 采用逻辑操作运算符构建逻辑表达式的采用逻辑操作运算符构建逻辑表达式的方式，与使用算术操作符构建代数表达方式，与使用算术操作符构建代数表达式的方式完全一样。式的方式完全一样。可以使用括号，也可以使用括号，也可以使用优先顺序可以使用优先顺序。 逻辑运算的优先顺序是：逻辑运算的优先顺序是：非最先，然后非最先，然后是合取，最后是析取。是合取，最后是析取。例：p pq qpqpqqpqp(pq) (pq) ( qp)( qp)(pq) (pq