《2022年《计算机数学基础》离散数学辅导-关系与函数》由会员分享，可在线阅读，更多相关《2022年《计算机数学基础》离散数学辅导-关系与函数（9页珍藏版）》请在金锄头文库上搜索。
1、计算机数学基础离散数学辅导(4) 第 4 章二元关系与函数(20XX 级用 ) 中央电大冯泰本章重点 ：关系概念与其性质，等价关系和偏序关系，函数. 一、重点内容1. 关系的概念包括定义、关系的表示方法：集合表示、矩阵表示、图形表示. 二元关系，是一个有序对集合，设集合A,B，,ByAxyxR，记作 xRy 二元关系的定义域：Dom( R)A； 二元关系的值域：Ran(R)B关系的表示方法：集合表示法：关系是集合，有类似于集合的表示方法. 列举法，如R, ；描述法：如,ByAxyxR关系矩阵：RAB，R 的矩阵njmibRaRbarrMjijiijnmijR,.,2, 1,.,2, 101,)
2、(关系图：R 是集合上的二元关系，若R，由结点aI画有向弧到bj构成的图形 . 2. 几个特殊的关系空关系；唯一是任何关系的子集的关系. 全关系AAAbabaEA,恒等关系,AaaaIA，MI是单位矩阵 . 3. 关系的运算关系的集合运算，有并、交、补、差和对称差. 复合关系,2121RcbRbabcaRRR使，有复合关系矩阵：21RRRMMM(布尔运算 )，有结合律： (R S) TR (S T) 逆关系,1RyxxyR，TRRMM1，(R S)1=S1R1. 4. 关系的性质自反性RxxAx,；矩阵RM的主对角线元素全为1；关系图的每个结点都有自回路 . 反自反性RxxAx,；矩阵RM的主
3、对角线元素全为0；关系图的每个结点都没有自回路. 对称性若Ryx,，则Rxy,；矩阵RM是对称矩阵，即jiijrr；关系图中有向弧成对出现,方向相反 . 反对称性若Ryx,且Rxy,，则x=y 或若yxRyx,，则Rxy,；矩阵RM不出现对称元素. 传递性若Rba,且Rcb,，则Rca,；在关系图中，有从a 到 b 的弧，有从b 到 c 的弧，则有从a 到 c 的弧 . 判断传递性较为困难. 可以证明： R 是集合 A 上的二元关系，(1)R是自反的IAR; (2)R是反自反的IAR; (3)R是对称的RR1；(4)R是反对称的RR 1IA；(5)R是传递的R RR. 关系的性质所具有的运算见
4、表4 1. 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 1 页，共 9 页 - - - - - - - - - 表 41 二元运算的并、交、补、差、逆、复合具有的性质表运算关系性质自反性反自反性对称性反对称性传递性R1 R1R2 R1R2 R1R2 R1R2 IA 由表可见，IA具有自反性，对称性、反对称性和传递性.EA具有自反性，对称性和传递性.故IA，EA是等价关系 .具有反自反性、对称性、反对称性和传递性。是偏序关系 . 关系性质的判定，可以用定义、关系矩
5、阵或关系图.传递性的判定， 难度稍大 . 也常如下判定： 不破坏传递性的定义，可认为具有传递性. 例如可认为具有传递性，同时具有对称性和反对称性，但是不具有自反性；5. 关系的闭包设 R 是非空集合A 上的二元关系，在关系R 中，添加最少的有序对，新关系用R表示，使得R 具有关系的自反(对称、传递 )性质， R 就是 R 的自反 (对称、传递 )闭包，记作r(R) ，s(R)和 t(R)。闭包的求法 ：定理 12：AIRRr)(；定理 13：1)(RRRs；定理 14 的推论：niiRRt1)(6. 等价关系和偏序关系极大 (小)元、最大 (小)元问题等价关系和偏序关系是具有不同性质的两个关系
6、. 偏 序 关 系等 价 关 系传递性反对称性对称性自反性等价关系图的特点：每一个结点都有一个自回路；两个结点间如有有向弧线，则是双向弧线，如果从a 到 b，从 b 到 c 各有一条有向弧线，则从a 到 c 一定有有向弧线。等价类 ，若 R 是等价关系，与R 中的某个元素等价的元素组成的集合，就是R 的一个等价类， aR= b bA aRb.偏序集的哈斯图偏序集概念和偏序集的哈斯图。哈斯图的画法：(1) 用空心点表示结点，自环不画； (2) 若 a b，则结点 b 画在上边， a 画在下边， 并画 a 到 b 的无向弧； (3) 若,则R，此时， a 到 c 的有向弧不画出. 确定任一子集的最
7、大(小)元，极大 (小)元 . 极大 (小 ) 元、最大 ( 小) 元、界 一个子集的极大( 小) 元可以有多个， 而最大 ( 小) 元若有，只能惟一 . 且极元、最元只在该子集内；而上界与下界可在子集之外确定，最小上界是所有上界中最小者， 最小上界再小也不会小于子集中的任一元素；可以与某一元素相等，最大下界也是同样 . 7. 函数函数 , 设 f 是集合 A 到 B 的二元关系，a A, b B,且f，且 Dom( f)=A，f 是一个函数 (映射 ). 函数是一种特殊的关系.集合 A B 的任何子集都是关系，但不一定是函数. 函数要求对于定义域A 中每一个元名师归纳总结 精品学习资料 -
8、- - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 2 页，共 9 页 - - - - - - - - - 素 a，B 中有且仅有一个元素与a 对应，而关系没有这个限制. 二函数相等是指：定义域相同，对应关系相同，而且定义域内每个对应值都相同. 函数的类型单射若)()(2121afafaa满射f(A)=B. 即)(,xfyAxBy使得双射单射且满射 . 复合函数,:,:,:CAgfCBgBAf则即)()(xfgxgf. 复合成立的条件是：)(Dom)(Rangf一般fggf，但)()(hgfhgf复合
9、函数的性质：如果 f,g 都是单射的，则f g 是单射的；如果 f,g 都是满射的，则f g 是满射的；如果 f,g 都是双射的，则f g 是双射的；如果 f,g 是单射的，则f 是单射的；如果 f,g 是满射的，则g 是满射的；如果 f ,g 是双射的，则f 是单射的， g 是满射的 . 反函数若 f：AB 是双射，则有反函数f1：BA,)(,1AabafBbabf，fffggf11111)(,)(二、实例例 4.1 设集合 Aa,b,R 是 P(A)上的包含关系，写出R 的表达式和关系矩阵. 解 用描述法表示；)(,yxAPyxyxR用列举法表示：因为, ,)(AbaAP，所以, , ,A
10、AAbbbAaaaAbaR关系矩阵：1000110010101111RM，关系图如图41 例 4.2 设 A1,2,3, 用列举法给出A 上的恒等关系IA，全关系EA，A 上的小于关系,yxAyxyxLA及其逆关系和关系矩阵. 解3, 3,2 ,2,1 , 1AIAAIE ,2, 3,1 , 3,3, 2,1 ,2,3 , 1,2, 13 ,2,3 , 1,2, 1AL, LA的逆关系2, 3,1 , 3,1 , 21AL000100110ALM0110010001ALM. 有TLLAAMM1例 4.3 设集合 A2,3,4, B=4,6,7, C=8,9,12,14 . R1是由 A 到 B
11、 的二元关系， R2是由B 到 C 的二元关系，定义如下：,1baabaR整除是素数且,2cbcbR整除求复合关系21RR，并用关系矩阵表示. 解6, 3,6, 2,4, 21R,14, 7,12,6,12,4,8 , 42R因此21RR, ab A图 41 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 3 页，共 9 页 - - - - - - - - - 0000100114327641RM1000010001017641412982RM21RRRMMM000
12、010011100001000101(布尔运算 )000001000101432141298例 4.4 试判断图42 中关系的性质：1 1 1 2 3 2 3 2 3 (a) (b) (c) 图 42 例 4.4 图解图 42 中(a)的关系在集合 1,2,3 上是对称的，因为结点1 与 2，1 与 3 之间的有向弧是成对出现且方向相反.图 42 中(b)是反自反的，因为每个结点都没有自回路. 它也是反对称的，因为两条边都是单向边，它又是传递的，容易求出R, 满足 R R=R. 图 42 中(c)的关系自反的，反对称的、但不是传递的. 因为 2 到 1 有边， 1 到 3 有边，但 2 到 3
13、 没有边 . 例 4.5 设 R 是实数集， R 上的二元关系S为S x,yR x=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)= R IA=,， 其中下画线者为添加元素. s(R)=1RR=R,= , t(R)=432RRRR=R , =, , 例 4.7 设集合 Aa,b,c
14、,d,e ，定义 A 上的二元关系AIdeedabbaR,1,2edddccbbabbaR判断 R1，R2是否为等价关系？分析判断等价关系，就是验证是否具有自反性、对称性和传递性. 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 4 页，共 9 页 - - - - - - - - - 解 写出 R1的关系矩阵，11000110000010000011000111RM图 44 由关系矩阵可知，R1具有自反性和对称性. 由关系图 (图 44)可知它具有传递性，故R1是等
15、价关系 . R2不是等价关系，因为),(),(22ReeRaa或，故 R 不具有自反性. 注意：自反性，对称性和传递性之一不具备，就是破坏了等价关系的定义. 事实上22,RdeRed但，故 R2不具有对称性；2,Rab，2,Raa但，R2也不具有传递性. 对例 4.7 的 R1进行分类： 元素 a，因为bbabbaaa,均属于 R1，所以a 生成的等价类,1baaR或记作1Rb. 元素 c，因为1,Rcc，所以 c 生成的等价类1ccR; 类似地，d 生成的等价类,1eddR1Re. 例 4.8 设集合 A18 的正整数因子 ， 为整除关系，说明是偏序关系 . 分析偏序关系只需验证自反性、反对
16、称性和传递性.解 集合 A1,2,3,6,9,18 ，整除关系为IA, , , 容易验证IA，故有自反性；(a,b), a b, 则(b,a)， 有反对称性；x,y,z A, 且,则，具有传递性 . 所以 是偏序关系 . 画的关系图和哈斯图如图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 1 9 6 9 2 6 2 3 3 1 (a) 的关系图(b) 的哈斯图图 45 abecd名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 5 页，共 9 页 - - - - - - - - - 若子集 B3=1,2,3, 则极大元2,
