《二元关系 讲稿.ppt》由会员分享,可在线阅读,更多相关《二元关系 讲稿.ppt(33页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、二元关系二元关系 第一页,讲稿共三十三页哦第第4章章 二元关系二元关系第二页,讲稿共三十三页哦集合论及二元关系集合论及二元关系第三页,讲稿共三十三页哦二元关系二元关系4.1二元关系基本概念二元关系基本概念 (重点重点)4.2 关系的运算关系的运算4.3 关系的性质关系的性质 (重点重点)4.4 关系的闭包关系的闭包4.5 等价关系和偏序关系等价关系和偏序关系(重点及难点重点及难点)4.6 函数的基本概念函数的基本概念第四页,讲稿共三十三页哦二元关系基本概念二元关系基本概念l世间万物都存在着联系。世间万物都存在着联系。l集合中的元素有什么联系,用集合中的元素有什么联系,用“关系关系”来表达。来表
2、达。第五页,讲稿共三十三页哦二元关系基本概念二元关系基本概念l二元关系定义及举例二元关系定义及举例l特殊的二元关系特殊的二元关系l二元关系表示方法二元关系表示方法 第六页,讲稿共三十三页哦二元关系二元关系引例引例 1.设集合设集合A=张红,李明,王强,程飞张红,李明,王强,程飞,B=离散数学,操作系统,计算机图形学离散数学,操作系统,计算机图形学,C=优,良,中,及格,不及格优,良,中,及格,不及格请写出学生选修课程情况及课程的成绩。请写出学生选修课程情况及课程的成绩。R=,“关系关系”都可以对应到都可以对应到一张关系表,反之亦然一张关系表,反之亦然 学生学生课程课程成绩成绩张红张红离散数学离
3、散数学优优张红张红操作系统操作系统良良李明李明操作系统操作系统良良李明李明计算机图形学计算机图形学中中王强王强离散数学离散数学中中王强王强操作系统操作系统及格及格王强王强计算机图形学计算机图形学良良程飞程飞计算机图形学计算机图形学优优第七页,讲稿共三十三页哦二元关系二元关系引例引例2.令令A1=x|x是学号是学号 A2=x|x是姓名是姓名 A3=男男,女女 A4=x|x是出生日期是出生日期 A5=x|x是是班级班级 A6=x|x是是籍贯籍贯 则则A1 A2 A3 A4 A5 A6中一个元素:中一个元素:这就是学生档案数据库的一条信息,所以学生这就是学生档案数据库的一条信息,所以学生的档案就是的
4、档案就是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于亮于亮男男19
5、92.12.08计计113山东山东第八页,讲稿共三十三页哦二元关系二元关系l二元关系二元关系有序对的集合有序对的集合lA到到B的二元关系的二元关系R ABlA上的二元关系上的二元关系R AAln元关系元关系称称 S A1A2An为为 A1,A2,An 上的上的 n 元关系元关系l R x R y R x R y 第九页,讲稿共三十三页哦二元关系二元关系例例1 几个二元关系的例子几个二元关系的例子1.程序间的调用关系,其中软件系统程序间的调用关系,其中软件系统 P=P1,P2,P3,P4 R=|x,y P,x调用调用y =,2.正整数的小于等于关系。正整数的小于等于关系。R =|x,y Z+,x
6、 y =,.,.,.R 第十页,讲稿共三十三页哦二元关系二元关系例例1 几个二元关系的例子几个二元关系的例子3.A=0,1,2,3,4,5,6,7,8,A上的模上的模3同余关系。同余关系。R=|x,y A,x y(mod3)=,IA,其中其中IA=|x A =,x y(mod3)x(mod3)=y(mod3)3|(a-b)第十一页,讲稿共三十三页哦二元关系二元关系例例1 几个二元关系的例子几个二元关系的例子4.P(A)上的包含关系。上的包含关系。R=|x,yP(A),x y 若若A=a,b,请写出请写出R。R =,IP(A),R =|A1,A2P(A),A1 A2 第十二页,讲稿共三十三页哦A
7、上的特殊二元关系上的特殊二元关系l空关系空关系 R=l恒等关系恒等关系 R=|xA,记为,记为IAl全域关系全域关系 R=AA,记为,记为EA显然:显然:IA EA 第十三页,讲稿共三十三页哦A上的特殊二元关系上的特殊二元关系例例2 设设A=1,2,3,B=1,2,则,则R1=空关系空关系R2=,A上恒等关系上恒等关系R3=,B上恒等关系上恒等关系R4=,=,IA A上全域关系上全域关系 第十四页,讲稿共三十三页哦二元关系的个数二元关系的个数思考思考 若若|A|=m,|B|=n,则,则A到到B的关系有多少个?的关系有多少个?|AB|=mn,R AB,则则A到到B的关系的个数即是的关系的个数即是
8、AB 的子的子集的个数,即集的个数,即Cmn0+Cmn1+Cmn2+Cmnmn =2mn第十五页,讲稿共三十三页哦二元关系的表示方法二元关系的表示方法l集合法集合法l矩阵法矩阵法设设Aa1,a2,.,an,Bb1,b2,.,bm,R是从是从A到到B的一个二元关的一个二元关系,称矩系,称矩阵阵MR(rij)nm为为关系关系R的关系矩的关系矩阵阵.l关系图法关系图法第十六页,讲稿共三十三页哦二元关系的表示方法二元关系的表示方法例例3 将例将例1、例、例2中的几个二元关系用各种方法来表示。中的几个二元关系用各种方法来表示。1.程序间的调用关系,其中软件系统程序间的调用关系,其中软件系统 P=P1,P
9、2,P3,P4 R=,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上的恒等关系和全域关系。上的恒等关系和全域关系。第十七页,讲稿共三十三页哦小结小结l理解现实世界中理解现实世界中“关系关系”的概念与数学中的概念与数学中“关系关系”概念的区概念的区别与联系。别与联系。l初步了解几个特殊关系及典型关系的性质。初步了解几个特殊关系及典型关系的性质。l掌握二元关系的表示方法,尤其是矩阵法。掌握二元关系的表示方法,尤其是矩阵法。第十八页,讲稿共
10、三十三页哦作业作业1.给定集合给定集合A=1,2,3,4,且,且A中的关系中的关系R:R=,请写出请写出R的关系矩阵及画出的关系矩阵及画出R的关系图。的关系图。2.设设X=1,2,3,4,H=|(x-y)/2是整数是整数,S=|(x-y)/3是整数是整数,求,求H S,H S,H S,H,S-H第十九页,讲稿共三十三页哦二元关系二元关系4.1二元关系基本概念二元关系基本概念 (重点重点)4.2 关系的运算关系的运算4.3 关系的性质关系的性质 (重点重点)4.4 关系的闭包关系的闭包4.5 等价关系和偏序关系等价关系和偏序关系(重点及难点重点及难点)4.6 函数的基本概念函数的基本概念第二十页
11、,讲稿共三十三页哦二元关系的运算二元关系的运算引例引例 有如下两张表,存货表和进货表,有如下两张表,存货表和进货表,(1)如何将两个表合为一个表?如何将两个表合为一个表?(2)如何从存货表中删除某些货品信息?如何从存货表中删除某些货品信息?(3)如何从总表中显示某些货品信息?如何从总表中显示某些货品信息?品名品名数量数量冰箱冰箱19彩电彩电30空调空调20存货表存货表品名品名数量数量电熨斗电熨斗30微波炉微波炉18进货表进货表品名品名数量数量冰箱冰箱19彩彩电电30空空调调20电电熨斗熨斗30微波炉微波炉18第二十一页,讲稿共三十三页哦二元关系的运算二元关系的运算l关系的关系的并并,交交,补补
12、,差差运算运算(略略)l关系的关系的值域值域、定义域定义域、域域l关系的关系的逆逆、限制限制和和像像运算运算l关系的关系的合成合成运算(运算(重点重点)l关系的关系的幂幂运算(运算(重点重点)第二十二页,讲稿共三十三页哦二元关系的运算二元关系的运算设设R是集合是集合A到到B上的关系,则上的关系,则lR的的定义域定义域domR,值域值域ranR和和域域fldR:domR=x|x A y(R).ranR=y|y B x(R).fldR=domRranR.l关系关系R的的逆关系逆关系:R-1=|yRx=|xRyl关系关系R在在A上的上的限制限制及及A在在R下的下的像像第二十三页,讲稿共三十三页哦二元
13、关系的运算二元关系的运算例例1 请写出如下关系的定义域,值域及逆关系。请写出如下关系的定义域,值域及逆关系。A=1,2,3,4,5,6,(1)R1=|x|y;(2)R2=|x是是y的倍数的倍数;(3)R3=|(x-y)2 A。第二十四页,讲稿共三十三页哦二元关系的运算二元关系的运算lF与与G的的合成(复合)合成(复合):F G=|z(xGzzFy)=|z(G F)注:左复合注:左复合第二十五页,讲稿共三十三页哦二元关系的运算二元关系的运算例例2 设设R和和S定义在定义在P上,上,P是所有人的集合。是所有人的集合。R=|x,y P x是是y的父亲的父亲,S=|x,y P x是是y的母亲的母亲。则
14、则(1)R R 表示的是什么关系?表示的是什么关系?(2)S-1 R表示的是什么关系?表示的是什么关系?第二十六页,讲稿共三十三页哦二元关系的运算二元关系的运算例例3 设设A=1,2,3,4,R=,S=,T=,是是A上的三个关系。上的三个关系。计计算算(1)R S和和S R;(2)(R S)T和和R(S T)。集合法集合法 图图示法示法 矩矩阵阵法法第二十七页,讲稿共三十三页哦关系矩阵与关系运算关系矩阵与关系运算l关系矩阵是关系矩阵是0-1阵(阵(布尔阵布尔阵)l若若MR=(aij),MS=(bij),则则MRS=(cij),MRS=(dij),其中其中cij=aij bij,dij=aij
15、bijlM R S=MS MR,其中的矩阵乘法为布尔矩阵乘法,即,其中的矩阵乘法为布尔矩阵乘法,即0+0=0,0+1=1+0=1+1=1 ()0 0=1 0=0 1=0,1 1=1 ()lM R-1=MRT ,其中,其中MRT是矩阵是矩阵 MR 的转置。的转置。第二十八页,讲稿共三十三页哦二元关系的运算二元关系的运算l关系的关系的幂幂运算:运算:设设R为为A上的二元关系,上的二元关系,n为为自然数,自然数,则则R的的n次次幂幂规规定如下:定如下:(1)R0=IA=xA;(2)Rn=Rn-1 R,n 1.集合法集合法 关系关系图图法法 矩矩阵阵法法第二十九页,讲稿共三十三页哦二元关系的运算二元关
16、系的运算Rn的关系图的构造:的关系图的构造:可由可由R的关系图来构造,从的关系图来构造,从R的每个结点的每个结点xi出发,数出发,数n条条边。若通过数边。若通过数n条边能到达结点条边能到达结点xj,则有,则有Rn。关系图。关系图中从中从xi出发到出发到xj的边是存在的。的边是存在的。但这样处理容易出错,用但这样处理容易出错,用相关矩阵的布尔型乘法相关矩阵的布尔型乘法来做,简来做,简单,又不容易错,还适宜于计算机处理。单,又不容易错,还适宜于计算机处理。第三十页,讲稿共三十三页哦二元关系的运算二元关系的运算例例4 设设A=1,2,3,4,5,6,定义在,定义在A上的关系上的关系R=,,计算:,计
17、算:(1)Rn(n=1,2,3,4,)(2)和和 可以看到可以看到:(1)对对于有于有穷穷集集A上的关系上的关系R,R的不同的的不同的幂幂只有有限个。只有有限个。(2)当)当n|A|时时,则则Rn 第三十一页,讲稿共三十三页哦二元关系的运算二元关系的运算定理定理 设设A是有限集合,且是有限集合,且|A|n,R是是A上的二元关系,则:上的二元关系,则:第三十二页,讲稿共三十三页哦二元关系的运算二元关系的运算举例:举例:上图若表示一个计算机网络,数据中心之间通过单向的电话线链上图若表示一个计算机网络,数据中心之间通过单向的电话线链接,如何确定两个中心之间是否有一条电话线接,如何确定两个中心之间是否有一条电话线(可能不直接可能不直接)链链接?或者更一般的,如何确定一个有向图中每对顶点是否接?或者更一般的,如何确定一个有向图中每对顶点是否“连通连通”?波士顿芝加哥丹佛底特律圣地亚哥纽约第三十三页,讲稿共三十三页哦
限制150内