上游充通大皇 SJTU School Of Software 2009-2-2 Chapter 2 Prerequisites Mathematics knowledge of software test 软件学院
SJTU School Of Software 2009-2-2 软件学院 Chapter 2 Prerequisites Mathematics knowledge of software test
上游充鱼大警 SJTU School Of Software 2009-2-2 2.1集合论 集合 定义：A={元素列表；B={元素列表； 运算：A∩B交集； AUB并集； A’补集； A-B={x∈A∧XB}; A⊕B=(AUB)-(A∩B);(异或) 笛卡尔积：A×B={KX,y>:x∈A个y∈B} 软件学院
SJTU School Of Software 2009-2-2 软件学院 2.1 集合论 集合 定义:A={ 元素列表 }; B={ 元素列表}; 运算: A∩B 交集; A∪B 并集; A’补集; A-B={x∈A∧x∈B} ; A⊕B=(A∪B)-(A∩B);(异或) 笛卡尔积:A×B={:x∈A∧y∈B}
上游充鱼大 SJTU School Of Software 2009-2-2 A是B的子集：ACB; A是B的真子集：ACB; A=B:ACB∧BcA; 划分： 给定一个集合B,以及B的一组子集A1,A2…An, 它们是B的一个划分，当且仅当： A1UA2U…UAn=B,且Ai∩Aj=g(i≠j) 软件学院
SJTU School Of Software 2009-2-2 软件学院 A是B的子集:A⊆B; A是B的真子集:A⊂B; A=B: A⊆B∧B⊆A; 划分: 给定一个集合B,以及B的一组子集A1,A2……An, 它们是B的一个划分,当且仅当: A1∪A2∪…∪An=B,且 Ai∩Aj=ø(i≠j)
上游充通大 SJTU School Of Software 2009-2-2 2.2函数[离散数学中) 定义： 给定集合A和B,函数f是AxB的一个子集，使得ai、 aj∈A,bi、bj∈B,f(ai)=bi,f(aj)=bj, bi≠bj→ai≠aj。 或f:A→B f∈AxB 上函数，当且仅当f(A)=B; 中函数，当且仅当f(A)cB; 一对一函数：ai、aj∈A,ai≠aj→f(ai)f(aj): 多对一函数：存在ai、aj∈A,ai≠a但f(ai)=f(aj): 软件学院
SJTU School Of Software 2009-2-2 软件学院 2.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)=B; 中函数，当且仅当f(A)⊂B; 一对一函数： ai、aj∈A, ai≠aj ⇒f(ai)≠f(aj); 多对一函数： 存在ai、aj∈A, ai≠aj 但f(ai)=f(aj);
上游充鱼大姿 SJTU School Of Software 2009-2-2 2.3关系 给定2个集合A和B,关系R是笛卡尔积A×B的 一个子集。 关系的属性： 自反的：当且仅当所有a∈A,〈a,a>∈R; 对称的：当且仅当∈R→∈R; 反对称的：当且仅当、∈R→a=b; 传递的：当且仅当、∈R→〈a,c>∈R; 排序关系：自反、反对称和传递的；（小于等于） 等价关系：自反、对称和传递的；（同班同学） 软件学院
SJTU School Of Software 2009-2-2 软件学院 2.3 关系 给定2个集合A和B，关系R是笛卡尔积A × B的 一个子集。 关系的属性： 自反的：当且仅当所有 a∈A,∈R; 对称的：当且仅当∈R ⇒ ∈R; 反对称的：当且仅当、 ∈R ⇒ a=b; 传递的：当且仅当、 ∈R ⇒ ∈R; 排序关系：自反、反对称和传递的；（小于等于） 等价关系：自反、对称和传递的；（同班同学）
上游充鱼大 SJTU School Of Software 2009-2-2 2.4命题逻辑 命题：是要么为真、要么为假的句子。 例子：6>2、汽车会飞、人是动物等； 而：水很深、山很高、火车很快等就不是命题。 命题的逻辑运算： 与 或 V 非 异或： 6 ⊕ 如果一则（IF-THEN)：→ 软件学院
SJTU School Of Software 2009-2-2 软件学院 2.4 命题逻辑 命题：是要么为真、要么为假的句子。 例子：6>2、汽车会飞、人是动物 等； 而：水很深、山很高、火车很快等就不是命题。 命题的逻辑运算： 与 ：∧ 或 ：∨ 非 ：¬ 异或 ：⊕ 如果—则（IF-THEN）：→
上游充通大粤 SJTU School Of Software 2009-2-2 p q p p T T F T T F T F F T T T F F F T 软件学院
SJTU School Of Software 2009-2-2 软件学院 p q p⊕q p→q T T F T T F T F F T T T F F F T
上浒完通大警 SJTU School Of Software 2009-2-2 2.5概率论 概率：是期望发生方式的数量，除以总的可能方 式的数量； 例1：一个袋子中有10个红球，10个兰球；从中 任取一个球，是红球的几率？ 再取一个是红球的几率？ 连续2个是红球的几率？ 例2：一副扑克4人打，你拿到4个A的概率？ 软件学院
SJTU School Of Software 2009-2-2 软件学院 2.5 概率论 概率：是期望发生方式的数量，除以总的可能方 式的数量； 例1：一个袋子中有10个红球，10个兰球；从中 任取一个球，是红球的几率？ 再取一个是红球的几率？ 连续2个是红球的几率？ 例2：一副扑克4人打，你拿到4个A的概率？
上游充通大皇 SJTU School Of Software 2009-2-2 2.6图论 图G=(V,E)由节点的有限集合V和节点无序对偶 集合E组成。 n1 n2 例1： n3 n4 n6 n5 V={n1,n2,n3,n4,n5}; E={(n1,n2),(n1,n4),(n2,n6),(n3,n4),(n4,n5)}; 软件学院
SJTU School Of Software 2009-2-2 软件学院 图G=（V，E）由节点的有限集合V和节点无序对偶 集合E组成。 例1： V={n1,n2,n3,n4,n5}; E={(n1,n2),(n1,n4),(n2,n6),(n3,n4),(n4,n5)}; 2.6 图论 n1 n2 n3 n4 n5 n6
上游充鱼大姿 SJTU School Of Software 2009-2-2 ⑧度：节点的度是与该节点连接的边数； 关联矩阵：节点与边的矩阵； 相邻矩阵：节点与节点的矩阵； 路径：从节点A到节点B的一个边的序列； 必 连通性：A到B有路径； n1 n2 圈数：区域的划分； n3 有向图（如右图） n4 入度(Indeg) n6 n5 出度(Outdeg) 软件学院
SJTU School Of Software 2009-2-2 软件学院 度：节点的度是与该节点连接的边数； 关联矩阵：节点与边的矩阵； 相邻矩阵：节点与节点的矩阵； 路径：从节点A到节点B的一个边的序列； 连通性：A到B有路径； 圈数：区域的划分； 有向图(如右图) 入度(Indeg) 出度（Outdeg） n1 n5 n3 n4 n6 n2
