第三章集合与关系-复习2概述.pptVIP

第*页 * 实例 例 设 A={1, 2, 3, 4}，在 A?A上定义二元关系R： x,y,u,v?R ? x+y = u+v， 求证R具有自反、对称、传递，R各元素的等价类， 导出的划分。 解 A?A={1,1, 1,2, 1,3, 1,4, 2,1, 2,2, 2,3,2,4,3,1, 3,2, 3,3, 3,4, 4,1, 4,2, 4,3, 4 ,4} 第*页 * 实例（续） 根据 x,y 的 x + y = 2,3,4,5,6,7,8 将A?A划分成7个 等价类： (A?A)/R={ {1,1}, {1,2,2,1}, {1,3, 2,2, 3,1}, {1,4, 2,3, 3,2, 4,1}, {2,4, 3,3, 4,2}, {3,4, 4,3}, {4,4} } 第*页 3-11 相容关系 相容关系是另一种常见关系， 如朋友关系、同学关系等。 这些关系的共性是自反的、对称的。 本节要点： 相容关系 定义、性质 相容类 概念，画图 完全覆盖的计算 第*页 等价关系 有向图 等价类 商集 划分 相容类 最大相容类 完全覆盖 简化图 二元关系 性质 自反 对称 传递 反对称 反自反 相容关系 第*页 3-12 次序关系 次序关系也是常遇到的重要关系，例如： 数值的≤、＜、≥、＞关系； 集合的?、?关系； 图书馆的图书按书名的字母次序排序； 词典中的字(词)的排序； 计算机中文件按文件名排序； 程序按语句次序执行；……. 要求掌握如下概念： 偏序关系、盖住关系、 Hasse图、链、反链、全序集、极大元、极小元、最大元、最小元、上界、下界、最小上界（上确界）、最大下界（下确界）、良序集 第*页 等价关系 有向图 等价类 商集 划分 相容类 最大相容类 完全覆盖 简化图 二元关系 性质 自反 对称 传递 反对称 反自反 相容关系 偏序关系 全序 哈斯图 重要元素 第*页 0 1 0 0 0 1 0 0 0 0 0 1 1 1 0 0 0 3×4 。 1 0 1 0 0 0 0 0 1 0 0 1 0 0 1 = 4×5 1 0 1 0 0 0 1 0 1 1 0 1 0 0 0 3 × 5 （3）矩阵法（续） R ={1,b,2,c,2,d,3,a} S={a,y,b,x,b,z,c,s,d,y,d,t} 即 R?S={ 1,x , 1,z ,2,s,2,y,2,t,3,y} 第*页 令R是A上关系，由于复合运算可结合，所以关系的复合可以写成乘幂形式。即 R ? R=R2， R2 ? R=R ? R2 =R3，… Rn+1＝Rn ? R R0＝{x,x|x∈A}＝IA R0＝IA 二、关系的乘幂 P115 若|X|=n，则X中的二元关系R的幂次值是有限的，一般不用求超出X的n的次幂。 第*页 二、逆关系 逆关系(反关系)也是我们经常遇到的概念，例如≤与≥就是互为逆关系。 （一）定义3-7.2 R是从A到B的关系，如果将R中的所有序偶的两个元素的位置互换，得到一个从B到A的关系，称之为R的逆关系，记作RC，或 R-1。 RC={y,x|x,y?R} y,x∈RC ?x,y?R 或者 xRy?yRCx 例如，小于关系的逆关系是大于关系，大于关系的逆关系为小于关系，相等关系的逆关系仍是相等关系。 ?C=? A B R B A RC 第*页 A={1,2,3}, B={1,2,3,4}，R ? A×B R={1,2,2,3,3,1,3,3,3,4} 1、枚举法求RC RC ={2,1,3,2,1,3,3,3,4,3} 2. RC的有向图： 将R的有向图的所有边的方向颠倒一下即可。 3. RC的矩阵 MRC =(MR)T 即为R矩阵的转置。如 （二）逆关系的计算方法 1 0 1 0 0 0 0 1 1 0 1 1 MR= 3×4 1 0 1 0 0 0 1 0 1 0 1 1 MR = c 4×3 第*页 定理： 设R是集合A上的二元关系，则： 1）R是自反的?IA?R； 2）R是反自反的?R∩IA＝Φ； 3）R是对称的?R＝RC； 4）R是反对称的?R∩RC?IA； 5）R是传递的?R ? R?R 重要：三、利用集合运算来判断