《《计算机数学基础》离散数学辅导-关系与函数》由会员分享，可在线阅读，更多相关《《计算机数学基础》离散数学辅导-关系与函数（9页珍藏版）》请在金锄头文库上搜索。
1、1计算机数学基础离散数学辅导(4) 第 4 章 二元关系与函数(2002 级用) 中央电大 冯 泰本章重点：关系概念与其性质，等价关系和偏序关系，函数. 一、重点内容1. 关系的概念 包括定义、关系的表示方法：集合表示、矩阵表示、图形表示.二元关系，是一个有序对集合，设集合 A,B， ， 记作 xRy,ByAxyR二元关系的定义域：Dom(R) ； 二元关系的值域：Ran(R)关系的表示方法：集合表示法：关系是集合，有类似于集合的表示方法. 列举法，如 R,；描述法：如 ,yxy关系矩阵： RAB， R 的矩阵 njmibRarMiijnmijR ,.2101)(关系图： R 是集合上的二元关
2、系，若R，由结点 aI 画有向弧到 bj 构成的图形.2. 几个特殊的关系空关系；唯一是任何关系的子集的关系. 全关系 AbEA,恒等关系 ，M I 是单位矩阵. aI3. 关系的运算关系的集合运算，有并、交、补、差和对称差.复合关系 ，有, 2121 RcbabcR使复合关系矩阵： (布尔运算)，有结合律：(RS)TR (ST)21逆关系 ， ，(RS) 1 =S1 R1 . ,yx 14. 关系的性质自反性 ；矩阵 的主对角线元素全为 1；关系图的每个结Ax,RM点都有自回路.反自反性 ；矩阵 的主对角线元素全为 0；关系图的每个结,点都没有自回路.对称性 若 ，则 ；矩阵 是对称矩阵，即
3、 ；关Ryx,xy,Rjiijr系图中有向弧成对出现,方向相反.反对称性 若 且 ，则 x=y 或若 ，则, yx,；矩阵 不出现对称元素.Rxy,RM传递性 若 且 ，则 ；在关系图中，有从 a 到 b 的ba,c,ca,弧，有从 b 到 c 的弧，则有从 a 到 c 的弧. 判断传递性较为困难.可以证明：R 是集合 A 上的二元关系，(1) R 是自反的 IAR; (2)R 是反自反的I AR ;(3)R 是对 称的 RR 1 ； (4)R 是反对称的 RR1 IA；(5)R 是传递 的RR R. 关系的性质所具有的运算见表 41. 2表 41 二元运算的并、交、补、差、逆、复合具有的性质
4、表运算 关系性质 自反性 反自反性 对称性 反对称性 传递性R1 R1R2 R1R2 R1R 2 R1R2 IA 由表可见，I A 具有自反性， 对称性、反 对称性和传递性.E A 具有自反性，对称性和传递性.故 IA，EA 是等价关系 .具有反自反性、 对称性、反对称性和传递性。是偏序关系.关系性质的判定，可以用定义 、关系矩 阵或关系图. 传递性的判定，难度稍大. 也常如下判定：不破坏传递性的定义，可认为具有传递性. 例如 可认为 具有 传递性，同时 具有对称性和反对称性，但是不具有自反性； 5. 关系的闭包设 R 是非空集合 A 上的二元关系，在关系 R 中，添加最少的有序对，新关系用
5、R表示，使得 R具有关系的自反 (对称、传递)性质，R就是 R 的自反( 对称、传递)闭包，记作r(R) ，s (R)和 t(R)。闭包的求法：定理 12： ；定理 13： ；定理 14 的推论：AIr1)(snit1)(6. 等价关系和偏序关系 极大(小) 元、最大(小) 元问题等价关系和偏序关系是具有不同性质的两个关系. 偏 序 关 系等 价 关 系传 递 性反 对 称 性对 称 性自 反 性等价关系图的特点：每一个结点都有一个自回路；两个结点间如有有向弧线，则是双向弧线，如果从 a 到 b，从 b 到 c 各有一条有向弧线，则从 a 到 c 一定有有向弧线。等价类，若 R 是等价关系，与
6、 R 中的某个元素等价的元素组成的集合，就是 R 的一个等价类，a R=bbAaRb. 偏序集的哈斯图 偏序集概念和偏序集的哈斯图。哈斯图的画法：(1) 用空心点表示结点，自环不画；(2) 若 ab，则结点 b 画在上边，a 画在下边，并画 a 到 b 的无向弧；(3) 若,则R，此时，a 到 c 的有向弧不画出.确定任一子集的最大(小)元，极大(小) 元.极大(小)元、最大(小)元、界 一个子集的极大(小)元可以有多个，而最大(小)元若有，只能惟一. 且极元、最元只在该子集内；而上界与下界可在子集之外确定，最小上界是所有上界中最小者，最小上界再小也不会小于子集中的任一元素；可以与某一元素相等
7、，最大下界也是同样.7. 函数函数, 设 f 是集合 A 到 B 的二元关系，aA,bB,且 f，且 Dom(f)=A，f 是一个函数(映射). 函数是一种特殊的关系.集合 AB 的任何子集都是关系，但不一定是函数. 函数要求对于定义域 A 中每一个元素 a，B 中有且仅有一个元素与 a 对应，而关系没有 这个限制 . 二函数相等是指：定义域相同，对应关系相同，而且定义域内每个对应值都相同. 函数的类型单射 若 )(2121ff3满射 f(A)=B. 即 )(,xfyAxy使 得双射 单射且满射. 复合函数 即 . 复合成立的条,:,:,: Cgfgf 则 )()(xfgf件是： )(Dom)
8、(Ran一般 ，但fgf)()hff复合函数的性质： 如果 f,g 都是单射的，则 fg 是单射的； 如果 f,g 都是满射的，则 fg 是满射的；如果 f,g 都是双射的，则 fg 是双射的； 如果 f,g 是单射的，则 f 是单射的；如果 f,g 是满射的，则 g 是满射的；如果 f,g 是双射的，则 f 是单射的，g 是满射的. 反函数 若 f：AB 是双射，则有反函数 f1 ：BA，,)(,1 abba fffg11)(,)(二、实例例 4.1 设集合 Aa,b,R 是 P(A)上的包含关系，写出 R 的表达式和关系矩阵. 解 用描述法表示； )(,yxyx用列举法表示：因为 ，所以,
9、ba, , ba aR关系矩阵： ，关系图如图 4110RM例 4.2 设 A1,2,3,用列举法给出 A 上的恒等关系 IA，全关系 EA，A 上的小于关系 ,yxyxL及其逆关系和关系矩阵. 解 3,2,1,AIAIE ,23,1,1, LA 的逆关系, 2,31,1. 有 0ALM011ALMTLAM1例 4.3 设集合 A2,3,4,B=4,6,7,C=8,9,12,14. R 1 是由 A 到 B 的二元关系，R 2 是由B 到 C 的二元关系，定义如下：,1 babaR整 除是 素 数 且 ,2cb整 除求复合关系 ，并用关系矩阵表示. 2解 ,63,4 14,72,61,48,
10、因此 ,1 a bA 图 41401432761RM1076442982RM (布尔运算) 21RR01101432498例 4.4 试判断图 42 中关系的性质： 1 1 12 3 2 3 2 3 (a) (b) (c) 图 42 例 4.4 图解 图 42 中(a)的关系在集合1,2,3上是对称的，因为结点 1 与 2，1 与 3 之间的有向弧是成对出现且方向相反. 图 42 中(b) 是反自反的，因为每个结点都没有自回路. 它也是反对称的，因为两条边都是单向边，它又是传递的，容易求出 R, 满足 RR=R. 图 42 中(c) 的关系自反的， 反对称的、但不是传递的. 因为 2 到 1
11、有边，1 到 3 有边，但 2 到 3 没有边.例 4.5 设 R 是实数集， R 上的二元关系 S 为Sx,yRx=y试问二元关系 S 具有哪些性质？简单说明理由解 S 具有自反性，显然S； S 具有对称性，S，有 x=y，则S； S 具有反对称性，,S，有 x=y； S 具有传递性，,S,因为 x=y=z，故S 例 4.6 设集合 Aa,b,c,d, 定义 R,求 r(R),s(R),t(R). 解 求自反闭包，R 不具有自反性，由自反性的定义，只需在 R 上添加 IA，于是r(R)=RIA=,， 其中下画线者为添加元素. s(R)= =R,= ,1t(R)= =R,432=, ,例 4.
12、7 设集合 Aa,b,c,d,e，定义 A 上的二元关系I1,2 e判断 R1，R 2 是否为等价关系？分析 判断等价关系，就是验证是否具有自反性、对称性和传递性. 5解 写出 R1 的关系矩阵， 1001RM图 44由关系矩阵可知，R 1 具有自反性和对称性. 由关系图(图 44) 可知它具有传递性，故R1 是等价关系. R2 不是等价关系，因为 ，故 R 不具有自反性. ),(),(22eRa或注意：自反性，对称性和传递 性之一不具备，就是破坏了等价关系的定义. 事实上 ，故 R2 不具有对称性； ，2,deed但 2,Rab，R2 也不具有传递性. ,a但对例 4.7 的 R1 进行分类
13、：元素 a，因为 均属于 R1，所a,以 a 生成的等价类 或记作 .,b1R元素 c，因为 ，所以 c 生成的等价类 ;1,c1cR类似地， d 生成的等价类 .,ed1例 4.8 设集合 A18 的正整数因子 ，为整除关系，说明 是偏序关系. 分析 偏序关系只需验证自反性、反对称性和传递性.解 集合 A1,2,3,6,9,18，整除关系为I A, , ,容易验证 IA，故 有自反性；( a,b), ab, 则(b,a)，有反对称性； x,y,zA,且,则， 具有传递性. 所以是偏序关系. 画的关系图和哈斯图如图 45( a)和(b) ：(关系图与哈斯图不是一回事 ) 的最大元是 18，极大元是 18，最小元、极小元均为 1. 若子集 B12,3,6，则 B1 最大元和极大元都是 6，无极小元 . 上界为 6，18; 下界为1，上确界为 6，下确界为 1. 若子集 B23,6,9, 则 B2 无最大元，极大元为 6,9，最小元和极小元都是 3, 上界为18，下界为 3,1，上确界为 18，下确界为 3.18 18
