离散数学第4章-二元关系
46页1、第四章 关系,4.1 二元关系 4.2 关系的性质 4 .3 关系的运算 4 .5 关系的闭包 4.6 等价关系与划分,4.1 二元关系,一 定义4.1(二元关系) 设A和B是任意两个集合,AB的子集R称为从A到B的二元关系。当A=B时,称R为A上的二元关系。若(a, b)R,则称a与b有关系R,记为aRb。 (a, b)R:a与b没有关系R R=:空关系 R=AB:全关系,4.1 二元关系,二 定义4.2(定义域,值域) 设R是从A到B的二元关系,A的一个子集a|存在b,使得(a, b)R称为R的定义域,记为Dom R。B的一个子集b|存在a,使得 (a, b)R称为R的值域,记为Ran R。 A称为R的前域,B称为R的培域,并且Dom RA,Ran RB。,4.1 二元关系,三 定义4.3 (n元关系) 设A1,An是n个任意集合,定义A1An的子集R为A1,An的n元关系。 当A1=An时,R称为A上的n元关系。,4.2 关系的性质,一 定义4.4(关系的性质) 设R是集合A上的二元关系。 (1)如果对任意aA,有aRa,则称R是自反的。 (2)如果对任意aA,有(a, a)R,
2、则称R是反自反的。 (3) 对任意a, bA,如果aRb必有bRa,则称R是 对称的。 (4)对任意a, bA,如果aRb且bRa,必有a=b,则称R是反对称的。 (5)对任意a, b, cA,如果aRb且bRc,必有aRc,则称R是传递的。,4.2 关系的性质,二 定义4.5(关系矩阵) 设A和B是两个有限集A=a1, , am,B=b1, , bn,R是从A到B的二元关系,称m n阶矩阵MR=(mij)为R的关系矩阵,其中 若(ai, bj)R, mij =1 若(ai, bj) R,mij =0,4.2 关系的性质,三 关系图 设A=a1, , an,R是A上的二元关系。A中每个元素ai用一个点表示,称该点为顶点ai 。 如果ai R aj,则从顶点ai到顶点aj存在一条弧。 如果ai R ai,则从顶点ai到顶点ai存在一条封闭弧。 这样表示R中关系的图形,称为R的关系图。,4 .3 关系的运算,定义4.6 设R1和R2是从A到B的两个二元关系,对于aA,bB,定义: R1R2:a(R1R2)b aR1b或aR2b; R1R2:a(R1R2)b aR1b且aR2b; R1-R2
3、: a(R1-R2)b aR1b且(a, b)R2; 1:a 1b(a,b)(AB)-R1。,4 .3 关系的运算,一 逆运算 定义4.7(逆关系) 设R是从A到B的二元关系,则从B到A的二元关系记为R-1,定义为R-1 =(b,a)|(a,b)R,称为R的逆关系。 定理2.1 (1)(R-1)-1=R; (2)(R1R2)-1= R1-1 R2-1; (3)(R1R2)-1= R1-1 R2-1; (4) (AB)-1= BA;,4 .3 关系的运算,定理4.1 (5)-1=; (6)()-1= AB-R-1; (7) (R1-R2)-1= R1-1-R2-1; (8)若R1R2,则R1-1 R2-1 。 证明,4 .3 关系的运算,定理4.2 R是A上的二元关系,则R是对称的R=R-1。,4 .3 关系的运算,二 复合运算 定义4.8(复合关系) 设R1是从A到B的二元关系, R2是从B到C的二元关系,则从A到C的二元关系记为R1R2,定义为R1R2 =(a, c) | aA, cC, 且存在bB使(a, b) R1, (b, c) R2称为R1和R2的复合关系。 定理4.3(结合
4、律) (R1R2)R3 = R1(R2R3) 不满足交换律,4 .3 关系的运算,三 幂运算 定义4.9(幂运算) 设R是A上的二元关系,nN,R的n次幂记为Rn,定义如下: (1) R0是A上的恒等关系(即R0 =(a, a)|aA),记为IA,又R1=R; (2)Rn+1= RnR。 定理4.4 (1) Rm Rn=Rm+n (2) (Rm)n= Rmn,4.4 关系数据库,表格 线性表 关系数据库 属性 键,4 .5 关系的闭包,一 自反,对称,传递闭包 定义4.11(自反,对称,传递闭包) 设R是A上的二元关系,定义R的自反(对称,传递)闭包记为 R,满足下列三个条件: (1)R是自反的(对称的,传递的); (2)RR; (3)对任一自反(对称,传递关系)R”,RR”,则RR”。 分别记为r( R ),s( R ),t( R )。,4 .5 关系的闭包,二 基本性质 定理4.5 设R是A上的二元关系,则 R是自反的 r( R )=R; R是对称的 s( R )=R; R是传递的 t( R )=R; 定理4.6 设R1和R2是A上的二元关系,若R1R2则 r(R1) r(R2);
《离散数学第4章-二元关系》由会员n****分享,可在线阅读,更多相关《离散数学第4章-二元关系》请在金锄头文库上搜索。
项目二财务管理价值观念
山东省安全生产风险分级管控与隐患排查治理信息化系统交流材料-2018.9.26
人教版高中地理必修3第一章地理环境与区域发展第二节《地理信息技术在区域地理环境研究中的应用》
第三章2房地产抵押贷款-固定利率抵押贷款
第八章工程质量法律制度
第25讲家庭电路与安全用电
餐厅点餐系统项目
项目7水箱水位控制
框架完整个人年度工作总结范文模板
科目名称-国土交通省
金融工程09课件
高校自主招生之结构化面试
房地产私募股权投资基金(PE)专题研究.
房地产基础知识培训2012
第一章食品检测技术基础知识
第10章网站设计与建设综合实例
第5章尝试迷人的机器人项目机器人灭火项目
自考英语二unit3
企业人力资源管理师第六章劳动法与劳动关系管理
第三章市场营销宏观环境分析
2023-12-11 28页
2023-12-11 28页
2023-12-11 27页
2023-12-11 31页
2023-12-11 27页
2023-12-11 27页
2023-12-11 33页
2023-12-11 28页
2023-12-11 26页
2023-12-11 29页