中学数学等价关泵和偏序关系嘉应学院.pptVIP

第四章 二元关系和函数 本章主要内容: 集合的笛卡尔积与二元关系 关系的运算 关系的性质 关系的闭包 等价关系和偏序关系 函数的定义和性质 函数的复合和反函数 关系的闭包 定义4.11 设R是非空集合A上的关系,R的自反闭包(对称闭包或传递闭包)是A上的关系R’,且R’满足以下条件: (1)R’是自反的(对称的或传递的)； (2)R?R’； (3)对A上的任何包含R的自反关系(对称或传递关系)R”都有R’ ? R”. 一般将R的自反reflexive闭包记作r(R),对称symmetric闭包记作s(R),传递transitive闭包记作t(R)。 A上关系R的闭包 定理4.4 设R为非空集合A上的关系,则有 (1)r(R)＝R∪R0； (2)s(R)＝R∪R-1； (3)t(R)=R∪R2∪R3∪… (4)A是含有n个元素的集合t(R)=R∪R2∪R3∪…∪Rk , k≤n 例4.10 设A＝{a,b,c,d},R＝{a,b,b,a,b,c,c,d},则r(R),s(R),t(R)有 解: (1)r(R)＝R∪R0 ={a,b,b,a,b,c,c,d}∪{a,a,b,b,c,c,d,d} ={a,b,b,a,b,c,c,d,a,a.b,b,c,c,d,d} (2)s(R)＝R∪R-1 ={a,b,b,a,b,c,c,d}∪{b,a,a,b,c,b,d,c} ={a,b,b,a,b,c,c,d,c,b,d,c} (3)t(R)=R∪R2∪R3∪… ={a,b,b,a,b,c,c,d}∪{a,a,a,c,b,b,b,d} ∪{a,b,a,d,b,a,b,c} ={a,a,a,b,a,c,a,d,b,a,b,b,b,c,b,d, c,d} 闭包的矩阵表示(定理4.4的公式转换成矩阵表示） Mr＝M＋E Ms=M+M’ Mt=M+M2+M3+… 其中E表示同阶的单位矩阵(主对角线元素为1,其他元素都是0) M表示M的转置,而+均表示矩阵中对应元素的逻辑加。 4.5 等价关系和偏序关系 定义4.12 设R为非空集合A上的关系,如果R是自反的、对称的和传递的,则称R为A上的等价关系.对任何x,y∈A,如果x,y)∈等价关系R,则记作x~y. 下面是一些等价关系的例子. (1)在一群人的集合上年龄相等的关系是等价关系,而朋友关系不一定是等价关系,因为它可能不是传递的.一般称这种自反的对称的关系为相容关系.显然等价关系都是相容关系,但相容关系不一定是等价关系. (2)动物是按种属分类的；“具有相同种属”的关系是动物集合上的等价关系. (3)集合上的恒等关系和全域关系都是等价关系. (4)在同一平面上三角形之间的相似关系是等价关系,但直线间的平行关系不是等价关系,因为它不是自反的. 例4.11 A＝{1,2,…,8},R＝{x,y|x,y∈A∧x≡y(mod 3)},其中x-y(mod 3)的含义就是x-y可以被3整除. R为A上的等价关系,它的关系图如下所示,其中1~4~7,2~5~8,3~6. 把模3的等价关系推广,对任何正整数n可以定义整数集合Z上模n的等价关系. R＝｛x,y|x,y∈Z∧x≡y(mod n)} 例如,当n＝5时,整数之间的等价性满足: ···~－10~－5~0~5~10~…, …~－9~－4~1~6~11~… …~－8~－3~2~7~12~… ···~－7~－2~3~8~13~…, …~－6~－1~4~9~14~…. 设R是非空集合A上的等价关系,则A上互相等价的元素构成了A的若干个子集,叫做等价类. 定义4.13 设R是非空集合A上的等价关系,对任意的x∈A,令 称 为x关于R的等价类,简称为x等价类,简记为[x]. 在例4.11中有 [1]＝[4]＝[7]＝{1,4,7}, [2]＝[5]＝[8]＝{2,5,8}, [3]＝[6]= {3,6}. 等价类的性质. 定理4.5 设R是非空集合A上的等价关系,对任意的x,y∈A,下面的结论成立. (1) [x]≠?,且[x]?A； (2) 若xRy,则[x]=[y]； (3) 若xRy,则[x]∩[y]＝?； (4) =A. 商集 定义4.14 设R为非空集合A上的等价