离散数学教学课件03-集合与关系-3.4~3.5.pptVIP

第三章 集合与关系 Sets and Relations 关系 给定一个集合，其元素间往往存在某些关系。 例如，某一个家庭集合 {父亲、母亲、大儿子、小女儿} 成员间存在着夫妻关系、兄妹关系和上下辈关系 研究关系，主要是研究事物之间的结构 关系 例3.4.1 设A={a, b, c, d}是某乒乓球队的男队员集合，B={e, f, g}是女队员集合。 若A和B之间有混双配对关系的是a和g，d和e，则可以表达为： R = {a, g, d, e}这里R表示具有混双配对关系的序偶集合。 而所有可能具有混双配对关系的序偶集合是：{a,e, a,f, a,g, b,e, b,f, b,g, c,e, c,f, c,g, d,e, d,f, d,g} 关系 例3.4.2 设学生集合S={a, b, c, d}， 选修课集合C={日语, 法语}，成绩G={甲、乙、丙}。 若四个人选修内容及成绩如下： a 日语 乙 b 法语 甲 c 日语 丙 d 法语 乙 可表达为：R={a,日语,乙,b,法语,甲,c,日语,丙,d,法语,乙} 第四节 关系及其表示方法 一、关系概述 定义： 给定任意集合A和B，若R ? A×B，则称R为从A到B的二元关系特别当A=B时， R ? A×A，称R为A上的二元关系 给定任意集合A1,A2, …,An，若R ? A1×A2×…×An ，则称R为A1×A2×…×An的n元关系当A1＝A2＝…＝An＝A时，称R为A上的n元关系 关系 从定义上看，关系是一个集合，所有定义集合的方法，都可以用来定义关系： 前面的例子，使用的是列举法 用谓词P(x1, x2, …, xn)定义关系R R={x1, x2, …, xn| P(x1, x2, …, xn)} 例如：实数R上的二元关系G（…大于…）可以定义为： G={x,y|x ? R ∧ y ? R ∧ x y} 关系 反之，一个n元关系也可以定义谓词： 关系 给定任意集合A1,A2, …,An，设R ? A1×A2×…×An 若R= ? ，则称R为空关系 若R= A1×A2×…×An ，则称R为全域关系 例3.4.1 设 A={a, b, c, d}是某乒乓球队的男队员集合， B={e, f, g}是女队员集合 R表示具有混双配对关系的序偶集合。 若没有任何混双的组合，即R= ? ，R为空关系 若R为所有可能的组合（略），R为全域关系 二元关系 二、二元关系 定义： 二元关系R是有序对的集合， 若R ? A×B，称R为从A到B的二元关系 二元关系 二、二元关系 定义： 二元关系R是有序对的集合， 若R ? A×B，称R为从A到B的二元关系 二元关系 二元关系 令R ? A×B，且 二元关系 关系是有序对的集合，对它进行集合运算后，得到的结果仍然是有序对的集合，即定义了一个新关系： x (R ? S) y ? xRy ∨ xSy x (R ? S) y ? xRy ∧ xSy x (R - S) y ? xRy ∧ xSy x (R ? S) y ? xRy ? xSy x (R’) y ? xRy 二元关系 例3.4.3 平面上的几何图形是集合R2的子集，也是一种关系。设 关系数据库* 一个二元关系R写成一张表，其中的“二元”就对应表的两列。 如果一个表中有n列，相应的关系是一个n元关系 关系矩阵 三、关系矩阵和关系图 定义： 给定集合A={a1, a2, …, am}和B={b1, b2, …, bn} R ? A×B，若称矩阵MR=[rij]m×n为R的关系矩阵 关系矩阵 例3.4.4 令A={a1, a2}，B={b1, b2 , b3}， R={ a1, b1, a2, b1, a1, b3, a2, b2} 则 关系图 关系R也可以用有向图表示，具体方法是： 用小圆圈ο标上ai表示A中的元素ai ， ο 称为结点 关系图 这样得到的有向图A, R叫作关系R的图示简称关系图正规说法为：有向图A, R的图示所谓有向是指每条边都有方向记作GR 关系图 例3.4.6 设A={1, 2, 3, 4, 5}R={1,2, 2,2, 3,2, 3,4, 4,3}其图示为： 第五节 关系的性质 关系的五种特殊性质： 自反性 (Reflexive) 反自反性(Irreflexive) 对称性 (Symmetric) 反对称性 (Anti-Symmetric) 传递性 (Transitive) 自反性 设R是A上的二元关系（即R ? A×A ）： 若对于A中的每个元素x，都有xRx，则称R是自反的。即：