测试人员的离散数学

软件测试第3章

测试人员的离散数学学习目标集合论（掌握）函数（了解）关系（了解）命题逻辑（掌握）3.1集合论集合：作为一个单位，或一个整体引用多个事物。集合成员关系集合中的项叫做集合的元素或成员，这种关系采用符号∈表示。集合定义简单列出集合的元素给出辨别规则通过其他集合构建

无歧义定义清晰很难列举空集空集采用符号Φ表示。空集不包含元素。空集Φ是惟一的，即不会有两个空集Φ。如果集合被决策规则定义为永远失败，则该集合是空集。维恩图在维恩图中，集合被表示为一个圆圈，圆圈中的点表示集合元素维恩图以直观方式表示各种集合关系，但存在一些问题：无限集合、空集等4月11月9月6月U集合操作

集合基本操作：并、交和补

定义给定集合A和B，其并是集合A∪B＝{x：x∈A∨x∈B}。其交是集合A∩B＝{x：x∈A∧x∈B}。

A的补是集合A’＝{x：x不属于A}。

B针对A的相对补是集合A－B＝{x：x∈A∧x不属于B}A和B的对称差是集合A⊕B＝{x：x∈A⊕x∈B}A∪BABABA∩BAA’ABA-BABA⊕BA⊕B＝（A∪B）-（A∩B）举例给定两个集合：A={1，3，4，7，8，10，11}B={2，3，5，6，8，9，11}；求A∪B，A∩B，A－B，A⊕B。无序和有序对偶无序和有序对偶的表示法一般是：无序对偶：（a，b）有序对偶：<a，b>两者的差别是，对于a≠b，（a，b）＝（b，a），但是<a，b>≠<b，a>这种差别对于图论很重要。两个集合的笛卡儿集定义两个集合A和B的笛卡儿积（又叫叉积），是集合A×B＝{<x，y>：x∈A∧y∈B}笛卡儿积与运算有直观的联系。集合A的势是A中元素数，用|A|表示，对于集合A和B,|A×B|=|A|×|B|。维恩图不能显示笛卡儿积集合关系定义A是B的子集，记做AB， 当且仅当a∈A→a∈BA是B的真子集，记做AB， 当且仅当AB∧B－A≠ΦA和B是相等集合，记做A＝B， 当且仅当AB∧BA子集划分划分划分是将一个整体分成小块，使得所有事物都在某个小块中，不会遗漏。定义给定集合B，以及B的一组子集A1、A2、⋯⋯、An，这些子集是B的一个划分， 当且仅当：A1∪A2∪⋯∪An＝Bi≠j

→Ai∩Aj＝Φ完备性（未测试）无冗余性（多次测试）集合恒等式名称表达式等同律A∪Φ＝AA∩U＝A支配律A∪U＝UA∩Φ＝Φ幂等律A∪A＝AA∩A＝A求反律（A'）'＝A交换律A∪B＝B∪AA∩B＝B∩A结合律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'3.2函数函数是软件开发和测试的核心概念函数定义 给定集合A和B，函数f是A×B的一个子集，使得对于ai、aj∈A，bi、bj∈B，f(ai)＝bi，f(aj)＝bj，bi≠bj

→ai≠aj。记为：f：A→B函数映射：给出函数f：A→B，并且定义集合：f(A)＝{bi∈B：bi＝f(ai)对于某个ai∈A}，这个集合有时记做A在f下的映象。函数类型类型定义：f是从A到B的上函数，当且仅当f（A）＝Bf是从A到B的中函数，当且仅当f（A）Bf是从A到B的一对一函数，当且仅当对于所有ai、aj∈A，ai≠aj→f（ai）≠f（aj）。f是从A到B的多对一函数，当且仅当存在ai、aj∈A，ai≠aj使得f（ai）＝f（aj）。函数合成设引用集合定义域和值域的特定元素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）＝dfgfgBabcabbbc因果流非因果流函数合成3.3关系函数是关系的一种特例集合之间的关系定义：给定两个集合A和B，关系R是笛卡儿积A×B的一个子集。势：指集合中的元素个数给定两个集合A和B，一个关系RA×B，关系R的势是：一对一势，当且仅当R是A到B的一对一函数。多对一势，当且仅当R是A到B的多对一函数。一对多势，当且仅当至少有一个元素a∈A在R中的两个有序对偶中，即（a，bi）∈R和（a，bj）∈R多对多势，当且仅当至少有一个元素a∈A在R中的两个有序对偶中，即（a，bi）∈R和（a，bj）∈R。并且至少有一个元素b∈B在R中的两个有序对偶中，（ai，b）∈R和（ai，b）∈R。单个集合上的关系定义关系RA×A是：自反的，当且仅当所有a∈A，<a,a>∈R对称的，当且仅当<a,b>∈R→<b,a>∈R反对称的，当且仅当<a,b>、<b,a>∈R→a＝b传递的当且仅当<a,b>、<b,c>∈R→<a,c>∈R续……定义关系RA×A是排序关系，如果R是自反、反对称和传递的定义关系RA×A是等价关系，如果R是自反、对称和传递的3.4命题逻辑逻辑操作符两个值：T（代表真）和F（代表假）三种基本逻辑操作符：与(合取)”∧”、或(析取)”∨”和非”~” 非是惟一一个一元（一个操作数）逻辑操作符，其他都是二元操作符。pqp∧qp∨q~p

p⊕q

p→qTTTTFFTTFFTFTFFTFTTTTFFFFTFT逻辑操作定义如下：逻辑表达式采用逻辑操作运算符构建逻辑表达式的方式，与使用算术操作符构建代数表达式的方式完全一样。可以使用括号，也可以使用优先顺序。逻辑运算的优先顺序是：非最先，然后是合取，最后是析取。例：pqp→qq→p(p→q)∧(q→p)~((p