离散数学课件第3章.

第3章二元关系3.1基本概念3.2关系的合成3.3关系上的闭包运算3.4次序关系3.5等价关系和划分第3章二元关系第3章二元关系3.1基本概念3.1.1关系关系的数学概念是建立在日常生活中关系的概念之上的.让我们先看两个例子例3.1-1设A={a,b,c,d}是某乒乓球队的男队员集合,B={e,f,g}是女队员集合.如果A和B元素之间有混双配对关系的是a和g,d和e.我们可表达为:R={〈a,g〉,〈d,e〉}第3章二元关系这里R表示具有混双配对关系的序偶集合.所有可能具有混双配对关系的序偶集合是:A×B={〈x,y〉|x∈A∧y∈B}={〈a,e〉,〈a,f〉,〈a,g〉,〈b,e〉,〈b,f〉,〈b,g〉,〈c,e〉,〈c,f〉,〈c,g〉,〈d,e〉,〈d,f〉,〈d,g〉}第3章二元关系例3.1-2设学生集合A1={a,b,c,d},选修课集合A2={日语,法语},成绩等级集合A3={甲,乙,丙}.如果四人的选修内容及成绩如下:a日乙b法甲c日丙d法乙我们可表达为S={〈a,日,乙〉,〈b,法,甲〉,〈c,日,丙〉,〈d,法,乙〉}第3章二元关系这里S表示学生和选修课及成绩间的关系.而可能出现的全部情况为A1×A2×A3={〈x,y,z〉|x∈A1∧y∈A2∧z∈A3}={〈a,日,甲〉,〈a,日,乙〉,〈a,日,丙〉,〈a,法,甲〉,〈a,法,乙〉,=〈a,法,丙〉,〈b,日,甲〉,〈b,日,乙〉,〈b,日,丙〉,〈b,法,甲〉,=〈b,法,乙〉,〈b,法,丙〉,〈c,日,甲〉,〈c,日,乙〉,〈c,日,丙〉,=〈c,法,甲〉,〈c,法,乙〉,〈c,法,丙〉,〈d,日,甲〉,〈d,日,乙〉,=〈d,日,丙〉,〈d,法,甲〉,〈d,法,乙〉,〈d,法,丙〉}第3章二元关系定义3.1―1(1)A×B的子集叫做A到B的一个二元关系.(2)A1×A2×…×An(n≥1)的子集叫做A1×A2×…×An上的一个n元关系.(3)(1)nAAAAn的子集叫做A上的n元关系n个第3章二元关系从定义可看出,关系是一个集合,所有定义集合的方法,都可用来定义关系例3.1-1和例3.1-2是列举法的例子。一个谓词P(x1,x2,…,xn)可以定义一个n元关系R:R={〈x1,x2,…,xn〉|P(x1,x2,…,xn)}例如,实数R上的二元关系＞可定义如下:＞={〈x,y〉|x∈R∧y∈R∧x＞y}反之,一个n元关系也可定义一个谓词:P(x1,x2,…,xn)=1(真),当〈x1,x2,…,xn〉∈R时0(假),当〈x1,x2,…,xn∈R时第3章二元关系当n=1时,R={〈x〉|P(x)}称为一元关系.它是一重组集合,表示论述域上具有性质P的元素集合,其意义与R={x|P(x)}相同,仅记法不同而已。例如,设P(x)表示“x是质数”,论述域是N,则质数集合可表示为{〈x〉｜P(x)}或{x｜P(x)}第3章二元关系关系也可归纳地定义.自然数上的小于关系可定义如下:(1)(基础)〈0,1〉∈＜(2)(归纳)如果〈x,y〉∈＜,那么(i)〈x,y+1〉∈＜(ii)〈x+1,y+1〉∈＜(3)(极小性)对一切x,y∈N,x＜y当且仅当〈x,y〉是由有限次应用条款(1)和(2)构成。第3章二元关系定义3.1―2设R是的子集,如果R=,则称R为空关系,如果,则称R为全域关系.现在定义关系相等的概念,在关系相等的概念中不仅需要n重组集合相等,还需其叉积扩集也相同.定义3.1―3设R1是上的n元关系,R2是上的m元关系.那么R1=R2,当且仅当n=m,且对一切i,1≤i≤n,Ai=Bi,并且R1和R2是相等的有序n重组集合1niiA1niiA1niiA1niiB第3章二元关系3.1.2二元关系最重要的关系是二元关系.本章主要讨论二元关系,今后术语“关系”都指二元关系.若非二元关系将用“三元”或“n元”一类术语指出.二元关系有自己专用的记法和若干新术语设A={x1,x2,…,x7},B={y1,y2,…,y6}R={〈x3,y1〉,〈x3,y2〉,〈x4,y4〉,〈x6,y2〉}A到B的二元关系R可如图3.1―1那样形象地表示.〈x3,y1〉∈R,也可写成x3Ry1,称为中缀记法,读做x3和y1有关系R.中缀记法常用来表示诸如“=”,“＜”,“＞”等关系,例如〈3,5〉∈＜,通常写作3＜5.第3章二元关系图3.1―1第3章二元关系A叫做关系R的前域,B叫做关系R的陪域D(R)={x｜y(〈x,y〉∈R)}叫做关系R的定义域R(R)={y｜x(〈x,y〉∈R)}叫做关系R的值域关系是序偶的集合,对它可进行集合运算,运算结果定义一个新关系.设R和S是给定集合上的两个二元关系,则R∪S,R∩S,R-S,等可分别定义如下:x(R∪S)yxRy∨xSyx(R∩S)yxRy∧xSyx(R-S)yxRy∧x$yxyxRyRR第3章二元关系例3.1-3平面上的几何图形是平面R2的子集,也是一种关系.设(参看图3.1―2)R1={〈x,y〉｜〈x,y〉∈R2∧x2+y2≤9}R2={〈x,y〉｜〈x,y〉∈R2∧1≤x≤3)∧(0≤y≤3)}R3={〈x,y〉｜〈x,y〉∈R2∧x2+y2≥4}则R1∪R2={〈x,y〉｜〈x,y〉∈R2∧(x2+y2≤9∨(1≤x≤3∧0≤y≤3))}第3章二元关系R1∩R3={〈x,y〉｜〈x,y〉∈R2∧(x2+y2≤9∧x2+y2≥4)}R1-R3={〈x,y〉｜〈x,y〉∈R2∧(x2+y2≤9∧L(x2+y2≥4))}={〈x,y〉｜〈x,y〉∈R2∧(x2+y2≥4)}3R第3章二元关系图3.1―2第3章二元关系3.1.3关系矩阵和关系图表达有限集合到有限集合的二元关系时,矩阵是一有力工具定义3.1―4给定集合A={a1,a2,…,am}和B={b1,b2,…,bn},及一个A到B的二元关系R.使.rij=1,如果aiRbj0,如aiRbj则称MR=［rij］矩阵是R的关系矩阵.第3章二元关系例3.1-4设A={a1,a2},B={b1,b2,b3},R={〈a1,b1〉,〈a2,b1〉,〈a1,b3〉,〈a2,b2〉},则其关系矩阵为b1b2b3a1101a2110即101110RM第3章二元关系例3.1-5设A={1,2,3,4},A上的二元关系R={〈x,y〉｜x＞y},试求出关系矩阵解R={〈4,1〉,〈4,2〉,〈4,3〉,〈3,1〉,〈3,2〉,〈2,1〉}0000100011001111RM第3章二元关系集合A上的二元关系也可用有向图表示。具体方法如下:一般用小圆圈标上ai表示元素ai，小圆圈叫图的结点(node)，如果〈ai，aj〉∈R，则从结点ai到aj画一带箭头的弧(注意ai是始点，aj是终点，次序不能颠倒);如果〈ai，ai〉∈R，则通过结点ai画一个叫做自回路的带箭头的圆弧。称带箭头的弧为弧或边。这样所得的图叫做关系R的图示，又称关系图。正规的说法应该是有向图〈A，R〉的图示，所谓有向是指每条边都有方向。第3章二元关系图3.1―3第3章二元关系例3.1-6设A={1,2,3,4,5},R={〈1,2〉,〈2,2〉,〈3,2〉,〈3,4〉,〈4,3〉},其图示如图3.1―3所示.图中结点5叫做孤立点。利用关系R的图示,也可写出关系R.第3章二元关系3.1.4关系的特性在研究各种二元关系中,关系的某些特性扮演着重要角色,我们将定义这些特性,并给出它的图示和矩阵的特点定义3.1―5设R是A上的二元关系,(1)如果对A中每一x,xRx,那么R是自反的.即A上的关系R是自反的x(x∈A→xRx)A={1,2,3},R1={〈1,1〉,〈2,2〉,〈3,3〉,〈1,2〉}是自反的.其关系图和关系矩阵的特点如图3.1―4所示.第3章二元关系图3.1―4第3章二元关系(2)如果对A中每一x,xRx,那么R是反自反的.即A上的关系R是反自反的x(x∈A→xRx)例如,A={1,2,3},R2={〈2,1〉,〈1,3〉,〈3,2〉}是反自反的,其关系图和关系矩阵的特点如图3.1―5所示.有些关系既不是自反的,又不是反自反的(如图3.1―6),例如,R3={〈1,1〉,〈1,2〉,〈3,2〉,〈2,3〉,〈3,3〉}第3章二元关系图3.1―5第3章二元关系图3.1―6第3章二元关系(3)如果对每一x,y∈A,xRy蕴含着yRx,那么R是对称的.即A上的关系R是对称的xy(x∈A∧y∈A∧xRy→yRx)例如,A={1,2,3},R4={〈1,2〉,〈2,1〉,〈1,3〉,〈3,1〉,〈1,1〉}是对称的.其关系图和关系矩阵的特点如图3.1―7所示第3章二元关系图3.1―7第3章二元关系(4)如果对每一x,y∈A,xRy,yRx蕴含着x=y,那么R是反对称的.即A上的关系R是反对称的xy(x∈A∧y∈A∧xRy∧yRx→x=y)例如,A={1,2,3},R5={〈1,2〉,〈2,3〉}是反对称的,其关系图和关系矩阵的特点如图3.1―8所示.第3章二元关系图3.1―8第3章二元关系(5)如果对每一x,y,z∈A,xRy,yRz蕴含着xRz,那么R是传递的.即A上的关系R是传递的xyz(x∈A∧y∈A∧z=∈A∧xRy∧yRz→xRz)例如,A={1,2,3,4},R5={〈4,1〉,〈4,3〉,〈4,2〉,〈3,2〉,〈3,1〉,〈2,1〉}是传递的.其关系图和关系矩阵如图3.1―10所示.第3章二元关系图3.1―9第3章二元关系图3.1―10第3章二元关系例3.1-7(1)任何集合上的相等关系是自反的,对称的,反对称的和传递的,但不是反自反的(2)整数集合I上,关系≤是自反的,反对称的,可传递的.但不是反自反的和对称的.关系＜是反自反的,反对称的,可传递的,但不是自反的和对称的(3)={a,b},试考察上的下列关系:(i)关系“与……有同样长度”是自反的,对称的,可传递的,但不是反自反的和反对称的第3章二元关系(ii)“xRy”当且仅当x是y的真词头”,这里R是反自反的,反对称的,可传递的,但不是自反的和对称的(iii)“xRy”当且仅当x的某真词头是y的一个真词尾”,这里R既不是自反的又不是反自反的,因为aaRaa,但abRab,既不是对称的也不是反对称的,并且不是传递的。(4)非空集合上的空关系是反自反的,对称的,反对称的和传递的,但不是自反的.空集合上的空关系则是自反的,反自反的,对称的,反对称的和可传递的。(5)基数大于1的集合上的全域关系是自反的,对称的和传递的,但不是反自反的和反对称的.例如图3.1―11所示的关系。第3章二元关系图3.1―11第3章二元关系例题1、设A是具有n个元素的集合，求出A上具有对称性的二元关系的数目。（06年华中科技术大学研究生入学试题）2、求关系R的自反、对称和传递闭包，并画出相应的关系图。R={1,2、2,1、2,2、2,3、4,3}（大连理工大学08年入学试题）3、设集合A={1，2，3}，定义A上的关系R={1,2、3,1、2,3}（1）判断关系R的性质（2）求集合A上具有关系R的性质的关系共有多少个？（河海大学2005年入学试题）第3章二元关系4、在下图中给出了一个有向图，试求D={1,4,2,5,3,6}此有向图对应的关系是否可传递的？如果不是可传递的，试求此图的传递闭包。并且说明此有向图是否是弱连通图单向连通图和强连通图？(河海大学2004年入学试题)第3章二元关系3.2.1关系的合成前边已经指出，关系是序偶的集合，因此可以进行集合运算。本节介绍一种对关系来说更为重要的运算——合成运算。假设R1是A到B的关系，R2是B到C的关系(参看图3.2-1)。合成关系R1R2是一个A到C的关系:如果在关系图上，从a∈A到c∈C有一长度(路径中弧的条数)为2的路径，其第一条弧属于R1，其第二条弧属于R2，那么〈a，c〉∈R