19二元关系

1离散数学DiscreteMathematics主讲：陈哲云青岛理工大学计算机工程学院2012.09第4章二元关系集合论及二元关系二元关系4.1二元关系基本概念(重点)4.2关系的运算4.3关系的性质(重点)4.4关系的闭包4.5等价关系和偏序关系(重点及难点)4.6函数的基本概念二元关系基本概念世间万物都存在着联系。集合中的元素有什么联系，用“关系”来表达。二元关系基本概念二元关系定义及举例特殊的二元关系二元关系表示方法二元关系引例1.设集合A={张红，李明，王强，程飞}，B={离散数学，操作系统，计算机图形学}，C={优，良，中，及格，不及格}请写出学生选修课程情况及课程的成绩。R={张红，离散数学，优，张红，操作系统，良，李明，操作系统，良，李明，计算机图形学，中，王强，离散数学，中，王强，操作系统，及格，王强,计算机图形学，良，程飞,计算机图形学，优}“关系”都可以对应到一张关系表，反之亦然学生课程成绩张红离散数学优张红操作系统良李明操作系统良李明计算机图形学中王强离散数学中王强操作系统及格王强计算机图形学良程飞计算机图形学优二元关系引例2.令A1={x|x是学号}A2={x|x是姓名}A3={男,女}A4={x|x是出生日期}A5={x|x是班级}A6={x|x是籍贯}则A1A2A3A4A5A6中一个元素：2011001，王强，男，1991.05.04，计111，四川这就是学生档案数据库的一条信息，所以学生的档案就是A1A2A3A4A5A6的一个子集。学号姓名性别出生日期班级籍贯2011001张红女1992.02.13计111辽宁2011002王强男1991.05.04计111四川2011003程飞男1992.08.12计111山东2011004李明男1991.09.24计112江西2011005刘艳女1992.04.18计112海南2011006马明男1991.07.27计112宁夏2011007王芳女1990.11.15计113山西2011008于亮男1992.12.08计113山东二元关系二元关系——有序对的集合给定任意集合A和B，若RA×B，则称R为从A到B的二元关系，若RA×A，则称R为A上的二元关系。x,y∈RxRyx,yRxRyn元关系称SA1×A2×…×An为A1,A2,…,An上的n元关系二元关系例1几个二元关系的例子1.程序间的调用关系，其中软件系统P={P1,P2,P3,P4}R={x,y|x,y∈P,x调用y}={P1,P2,P2,P3,P1,P4}2.正整数的小于等于关系。R={x,y|x,y∈Z+,x≤y}={1,1,1,2,...,2,2,2,3,...,3,3,3,4,....}R≤二元关系例1几个二元关系的例子3.A={0,1,2,3,4,5,6,7,8}，A上的模3同余关系。R={x,y|x,y∈A,x≡y(mod3)}={0,3,0,6,1,4,1,7,2,5,2,8,3,0,3,6,4,1,4,7,5,2,5,8,6,0,6,3,7,1,7,4,8,2,8,5}∪IA,其中IA={x,x|x∈A}={0,0,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8}x≡y(mod3)x(mod3)=y(mod3)3|(a-b)二元关系例1几个二元关系的例子4.P(A)上的包含关系。R={x,y|}x,y∈P(A),xy}若A={a,b},请写出R。R={Φ,{a},Φ,{b},Φ,{a,b},{a},{a,b},{b},{a,b}}∪IP(A),R={A1,A2|A1,A2∈P(A),A1A2}A上的特殊二元关系空关系R=Φ恒等关系R={x,x|x∈A}，记为IA全域关系R=A×A，记为EA显然：ΦIAEAA上的特殊二元关系例2设A={1,2,3}，B={1,2}，则R1=Φ空关系R2={1,1,2,2,3,3}A上恒等关系R3={1,1,2,2}B上恒等关系R4={1,1,1,2,1,3,2,1,2,2,2,3,3,1,3,2,3,3}={1,2,1,3,2,1,2,3,3,1,3,2}∪IAA上全域关系二元关系的个数思考若|A|=m，|B|=n，则A到B的关系有多少个？|A×B|=mn，RA×B，则A到B的关系的个数即是A×B的子集的个数，即Cmn0+Cmn1+Cmn2+…+Cmnmn=2mn二元关系的表示方法集合法矩阵法关系图法二元关系的表示方法例3将例1、例2中的几个二元关系用各种方法来表示。1.程序间的调用关系，其中软件系统P={P1,P2,P3,P4}R={P1,P2,P2,P3,P1,P4}2.正整数的小于等于关系。3.A={0,1,2,3,4,5,6,7,8}，A上的模3同余关系。4.P(A)上的包含关系，其中A={a,b}。5.A={1,2,3}上的恒等关系和全域关系。思考：集合A到B上的二元关系如何表示？小结理解现实世界中“关系”的概念与数学中“关系”概念的区别与联系。初步了解几个特殊关系及典型关系的性质。掌握二元关系的表示方法，尤其是矩阵法。作业1.给定集合A={1,2,3,4}，且A中的关系R：R={1,1,1,3,2,2,3,4,4,1,4,4}请写出R的关系矩阵及画出R的关系图。2.课本4.11（4选2）二元关系4.1二元关系基本概念(重点)4.2关系的运算4.3关系的性质(重点)4.4关系的闭包4.5等价关系和偏序关系(重点及难点)4.6函数的基本概念二元关系的运算引例有如下两张表，存货表和进货表，(1)如何将两个表合为一个表？(2)如何从存货表中删除某些货品信息？(3)如何从总表中显示某些货品信息？品名数量冰箱19彩电30空调20存货表品名数量电熨斗30微波炉18进货表品名数量冰箱19彩电30空调20电熨斗30微波炉18二元关系的运算关系的并，交，补，差运算(略)关系的值域、定义域、域关系的逆、限制和像运算关系的合成运算（重点）关系的幂运算（重点）二元关系的运算设R是集合A到B上的关系，则R的定义域domR，值域ranR和域fldR：domR={x|x∈A∧y(x,y∈R)}.ranR={y|y∈B∧x(x,y∈R)}.fldR=domR∪ranR.关系R的逆关系：R-1={x,y|yRx}={y,x|xRy}关系R在A上的限制及A在R下的像二元关系的运算例1请写出如下关系的定义域，值域及逆关系。A={1,2,3,4,5,6}，(1)R1={x,y|x|y}；(2)R2={x,y|x是y的倍数}；(3)R3={x,y|(x-y)2∈A}。二元关系的运算F与G的合成（复合）：F◦G={x,y|z(xGz∧zFy)}={x,y|z(x,z∈G∧z,y∈F)}注：左复合二元关系的运算例2设R和S定义在P上，P是所有人的集合。R={x,y|x,y∈P∧x是y的父亲}，S={x,y|x,y∈P∧x是y的母亲}。则(1)R◦R表示的是什么关系？(2)S-1◦R表示的是什么关系？二元关系的运算例3设A={1,2,3,4}，R={1,2,2,2,3,4},S={2,4,3,1,4,2},T={1,4,2,1,4,2}是A上的三个关系。计算（1）R◦S和S◦R；（2）(R◦S)◦T和R◦(S◦T)。集合法图示法矩阵法关系矩阵与关系运算关系矩阵是0-1阵（布尔阵）若MR=(aij),MS=(bij),则MR∪S=(cij)，MR∩S=(dij),其中cij=aij∨bij,dij=aij∧bijMR◦S=MS·MR，其中的矩阵乘法为布尔矩阵乘法，即0+0=0,0+1=1+0=1+1=1(∨)0·0=1·0=0·1=0,1·1=1(∧)MR-1=MRT，其中MRT是矩阵MR的转置。二元关系的运算关系的幂运算：设R为A上的二元关系，n为自然数，则R的n次幂规定如下：(1)R0=IA={x,x｜x∈A}；(2)Rn=Rn-1◦R,n1.集合法关系图法矩阵法二元关系的运算Rn的关系图的构造：可由R的关系图来构造，从R的每个结点xi出发，数n条边。若通过数n条边能到达结点xj，则有xi,xj∈Rn。关系图中从xi出发到xj的边是存在的。但这样处理容易出错，用相关矩阵的布尔型乘法来做，简单，又不容易错，还适宜于计算机处理。（回忆图论中邻接矩阵关于求通路条数的应用）二元关系的运算例4设A={1,2,3,4,5,6}，定义在A上的关系R={1,1,1,2,2,3,3,4,4,5,5,6}，计算：(1)Rn(n=1,2,3,4,…)(2)和可以看到：（1）对于有穷集A上的关系R，R的不同的幂只有有限个。（2）当n≥|A|时，则Rn6ii1Rii1R6ii1R二元关系的运算定理设A是有限集合，且|A|＝n，R是A上的二元关系，则：RRiniii11UU二元关系的运算合成运算的主要性质：(1)(F◦G)◦H=F◦(G◦H)；(2)(F◦G)-1=G-1◦F-1；(3)Rm◦Rn＝Rm+n,(Rm)n＝Rmn小结初步了解关系的并、交、补、差、限制、像等运算与数据库中对关系表的操作的关系。掌握二元关系的合成（幂）运算，主要是集合法与矩阵法。掌握合成（幂）运算的主要性质。作业1.（续4.1节）给定集合A={1,2,3,4}，且A中的关系R：R={1,1,1,3,2,2,3,4,4,1,4,4}计算R2（矩阵法）。2.分别对下图中所给的两个关系，求Rn，nN。bdcaacbed