二元关系 .ppt

《二元关系 .ppt》由会员分享，可在线阅读，更多相关《二元关系 .ppt（33页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、二元关系二元关系 现在学习的是第1页，共33页第第4章章 二元关系二元关系现在学习的是第2页，共33页集合论及二元关系集合论及二元关系现在学习的是第3页，共33页二元关系二元关系4.1二元关系基本概念二元关系基本概念 (重点重点)4.2 关系的运算关系的运算4.3 关系的性质关系的性质 (重点重点)4.4 关系的闭包关系的闭包4.5 等价关系和偏序关系等价关系和偏序关系 (重点及难点重点及难点)4.6 函数的基本概念函数的基本概念现在学习的是第4页，共33页二元关系基本概念二元关系基本概念l世间万物都存在着联系。世间万物都存在着联系。l集合中的元素有什么联系，用集合中的元素有什么联系，用“关系

2、关系”来表达。来表达。现在学习的是第5页，共33页二元关系基本概念二元关系基本概念l二元关系定义及举例二元关系定义及举例l特殊的二元关系特殊的二元关系l二元关系表示方法二元关系表示方法 现在学习的是第6页，共33页二元关系二元关系引例引例 1.设集合设集合A = 张红，李明，王强，程飞张红，李明，王强，程飞， B = 离散数学，操作系统，计算机图形学离散数学，操作系统，计算机图形学， C=优，良，中，及格，不及格优，良，中，及格，不及格请写出学生选修课程情况及课程的成绩。请写出学生选修课程情况及课程的成绩。R = ， ， ， “关系关系”都都可以对应到一张关系表，反之亦然可以对应到一张关系表，

3、反之亦然 学生学生课程课程成绩成绩张红张红离散数学离散数学优优张红张红操作系统操作系统良良李明李明操作系统操作系统良良李明李明计算机图形学计算机图形学中中王强王强离散数学离散数学中中王强王强操作系统操作系统及格及格王强王强计算机图形学计算机图形学良良程飞程飞计算机图形学计算机图形学优优现在学习的是第7页，共33页二元关系二元关系引例引例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.

5、11.15计计113山西山西2011008于亮于亮男男1992.12.08计计113山东山东现在学习的是第8页，共33页二元关系二元关系l二元关系二元关系有序对的集合有序对的集合lA到到B的二元关系的二元关系R ABlA上的二元关系上的二元关系R AAln元关系元关系称称 S A1A2An为为 A1 , A2 , , An 上的上的 n 元关系元关系l R x R y R x R y 现在学习的是第9页，共33页二元关系二元关系例例1 几个二元关系的例子几个二元关系的例子1. 程序间的调用关系，其中软件系统程序间的调用关系，其中软件系统 P=P1,P2,P3,P4 R = |x,y P , x

6、调用调用y =,2.正整数的小于等于关系。正整数的小于等于关系。 R = |x,y Z+,x y =,.,.,.R 现在学习的是第10页，共33页二元关系二元关系例例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)现在学习的是第11页，共33页二元关系二元关系例例1 几个二元关系的例子几个二元关系的例子4.P(A)上的包含关系。上的包含关系。 R =|

7、x,yP(A), x y 若若A=a,b,请写出请写出R。 R =, IP(A) ,R = | A1,A2P(A), A1A2 现在学习的是第12页，共33页A上的特殊二元关系上的特殊二元关系l空关系空关系 R=l恒等关系恒等关系 R=|xA，记为，记为IAl全域关系全域关系 R=AA，记为，记为EA显然：显然： IA EA 现在学习的是第13页，共33页A上的特殊二元关系上的特殊二元关系例例2 设设A = 1,2,3 ，B = 1,2，则，则R1 = 空关系空关系R2 = , A上恒等关系上恒等关系R3 = , B上恒等关系上恒等关系R4 = , , = , , IA A上全域关系上全域关系

8、 现在学习的是第14页，共33页二元关系的个数二元关系的个数思考思考 若若|A|=m，|B|=n，则，则A到到B的关系有多少个？的关系有多少个？|AB|=mn，R AB ， 则则A到到B的关系的个数即是的关系的个数即是AB 的子集的个数，即的子集的个数，即Cmn0 + Cmn1 + Cmn2 + + Cmnmn = 2mn现在学习的是第15页，共33页二元关系的表示方法二元关系的表示方法l集合法集合法l矩阵法矩阵法设设Aa1,a2,.,an,Bb1,b2,.,bm,R是从是从A到到B的一个二元关系的一个二元关系，称矩阵，称矩阵MR（rij)nm为关系为关系R的关系矩阵的关系矩阵.l关系图法关系

9、图法1 ,R(1,2,., ,1,2,.,)0,Rijijija bin jma br现在学习的是第16页，共33页二元关系的表示方法二元关系的表示方法例例3 将例将例1、例、例2中的几个二元关系用各种方法来表示。中的几个二元关系用各种方法来表示。1. 程序间的调用关系，其中软件系统程序间的调用关系，其中软件系统 P=P1,P2,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上的恒等关系和全域关系。上的恒等关系和

10、全域关系。现在学习的是第17页，共33页小结小结l理解现实世界中理解现实世界中“关系关系”的概念与数学中的概念与数学中“关系关系”概念的区别概念的区别与联系。与联系。l初步了解几个特殊关系及典型关系的性质。初步了解几个特殊关系及典型关系的性质。l掌握二元关系的表示方法，尤其是矩阵法。掌握二元关系的表示方法，尤其是矩阵法。现在学习的是第18页，共33页作业作业1.给定集合给定集合A=1, 2, 3, 4，且，且A中的关系中的关系R：R =, , , , , 请写出请写出R的关系矩阵及画出的关系矩阵及画出R的关系图。的关系图。2.设设X=1,2,3,4，H=|(x-y)/2是整数是整数，S=|(x

11、-y)/3是整数是整数，求，求H S，H S，H S，H，S-H现在学习的是第19页，共33页二元关系二元关系4.1二元关系基本概念二元关系基本概念 (重点重点)4.2 关系的运算关系的运算4.3 关系的性质关系的性质 (重点重点)4.4 关系的闭包关系的闭包4.5 等价关系和偏序关系等价关系和偏序关系 (重点及难点重点及难点)4.6 函数的基本概念函数的基本概念现在学习的是第20页，共33页二元关系的运算二元关系的运算引例引例 有如下两张表，存货表和进货表，有如下两张表，存货表和进货表，(1)如何将两个表合为一个表？如何将两个表合为一个表？(2)如何从存货表中删除某些货品信息？如何从存货表中

12、删除某些货品信息？(3)如何从总表中显示某些货品信息？如何从总表中显示某些货品信息？品品名名数数量量冰冰箱箱19彩彩电电30空空调调20存货表进货表品名品名数量数量冰箱冰箱19彩电彩电30空调空调20电熨斗电熨斗30微波炉微波炉18现在学习的是第21页，共33页二元关系的运算二元关系的运算l关系的关系的并并，交交，补补，差差运算运算(略略)l关系的关系的值域值域、定义域定义域、域域l关系的关系的逆逆、限制限制和和像像运算运算l关系的关系的合成合成运算（运算（重点重点）l关系的关系的幂幂运算（运算（重点重点）现在学习的是第22页，共33页二元关系的运算二元关系的运算设设R是集合是集合A到到B上的

13、关系，则上的关系，则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下的下的像像现在学习的是第23页，共33页二元关系的运算二元关系的运算例例1 请写出如下关系的定义域，值域及逆关系。请写出如下关系的定义域，值域及逆关系。A=1,2,3,4,5,6，(1) R1=|x|y；(2) R2=|x是是y的倍数的倍数；(3) R3=|(x-y)2 A。 现在学习的是第24

14、页，共33页二元关系的运算二元关系的运算lF与与G的的合成（复合）合成（复合）： F G = | z(xGzzFy) =| z( G F)注：左复合注：左复合现在学习的是第25页，共33页二元关系的运算二元关系的运算例例2 设设R和和S定义在定义在P上，上，P是所有人的集合。是所有人的集合。R=|x,y P x是是y的父亲的父亲，S=| x,y P x是是y的母亲的母亲。则则(1) R R 表示的是什么关系？表示的是什么关系？ (2) S-1 R表示的是什么关系？表示的是什么关系？现在学习的是第26页，共33页二元关系的运算二元关系的运算例例3 设设A=1,2,3,4， R=,S=, T=,是

15、是A上的三个关系。计算上的三个关系。计算（1）R S和和S R；（2）(R S) T和和R (S T)。 集合法集合法 图示法图示法 矩阵法矩阵法现在学习的是第27页，共33页关系矩阵与关系运算关系矩阵与关系运算l关系矩阵是关系矩阵是0-1阵（阵（布尔阵布尔阵）l若若MR=(aij), MS=(bij), 则则MRS=(cij)， MRS=(dij), 其中其中cij=aij bij, dij=aij bijlM R S = MS MR，其中的矩阵乘法为布尔矩阵乘法，即，其中的矩阵乘法为布尔矩阵乘法，即0 + 0 = 0, 0 +1 = 1 + 0 = 1 + 1 = 1 () 0 0 = 1

16、 0 = 0 1 = 0, 1 1 =1 ()lM R-1 = MRT ，其中，其中MRT是矩阵是矩阵 MR 的转置。的转置。 现在学习的是第28页，共33页二元关系的运算二元关系的运算l关系的幂运算：关系的幂运算：设设R为为A上的二元关系，上的二元关系，n为自然数，则为自然数，则R的的n次幂次幂规定如规定如下：下：(1) R0=IA=xA；(2) Rn= Rn-1 R, n 1. 集合法集合法 关系图法关系图法 矩阵法矩阵法现在学习的是第29页，共33页二元关系的运算二元关系的运算Rn的关系图的构造：的关系图的构造： 可由可由R的关系图来构造，从的关系图来构造，从R的每个结点的每个结点xi出

17、发，数出发，数n条边。条边。若通过数若通过数n条边能到达结点条边能到达结点xj，则有，则有Rn。关系图中从。关系图中从xi出发到出发到xj的边是存在的。的边是存在的。 但这样处理容易出错，用但这样处理容易出错，用相关矩阵的布尔型乘法相关矩阵的布尔型乘法来做，来做，简单，又不容易错，还适宜于计算机处理。简单，又不容易错，还适宜于计算机处理。现在学习的是第30页，共33页二元关系的运算二元关系的运算例例4 设设A=1,2,3,4,5,6，定义在，定义在A上的关系上的关系R=,，计算：，计算：(1)Rn(n=1,2,3,4,)(2) 和和 可以看到可以看到：（1）对于有穷集）对于有穷集A上的关系上的

18、关系R，R的不同的幂只有有限个。的不同的幂只有有限个。（2）当）当n|A|时，则时，则Rn 6ii 1Rii 1R6ii 1R现在学习的是第31页，共33页二元关系的运算二元关系的运算定理定理 设设A是有限集合，且是有限集合，且|A|n，R是是A上的二元关系，上的二元关系，则：则：RRiniii11 UU现在学习的是第32页，共33页二元关系的运算二元关系的运算举例：举例：上图若表示一个计算机网络，数据中心之间通过单向的电话线链接，上图若表示一个计算机网络，数据中心之间通过单向的电话线链接，如何确定两个中心之间是否有一条电话线如何确定两个中心之间是否有一条电话线(可能不直接可能不直接)链接？或者更链接？或者更一般的，如何确定一个有向图中每对顶点是否一般的，如何确定一个有向图中每对顶点是否“连通连通”？波士顿芝加哥丹佛底特律圣地亚哥纽约现在学习的是第33页，共33页