离散数学第二章关系.ppt
《离散数学第二章关系.ppt》由会员分享,可在线阅读,更多相关《离散数学第二章关系.ppt(108页珍藏版)》请在三一办公上搜索。
1、1,离散数学,西安交通大学电子与信息工程学院计算机软件所刘国荣,2,3,离散数学,第二章 关系(relation)1.集合的叉积n元组 2.关系 3.关系的表示关系的性质 4.关系的运算 5.等价关系 6.半序关系,4,离散数学,1.集合的叉积n元组 定义1.叉积,笛卡尔积(cross product,Cartesian product(1637)n个集合A1,A2,An的 n 维叉积定义为=A1 A2 An=(a1,a2,an):ai Ai(1i n);n 维叉积A1 A2 An的每个元素(a1,a2,an)都称为一个n元组(n-tuple);即,叉积是元组的集合;每个n元组(a1,a2,a
2、n)的第i个位置上的元素ai称为该n元组的第i个分量(坐标或投影);元组各分量的顺序不能改变;n 称为该叉积及其元组的维数;两个元组相等它们的维数相同且对应的分量相等。,5,离散数学,即(a1,a2,an)=(b1,b2,bm)n=m(iN)(1i n)(ai=bi);注:笛卡尔(1596-1650),法国数学家,1637年发表方法论之一几何学,首次提出坐标及变量概念。这里是其概念的推广。定义2.二个集合A,B的(二维或二重)叉积定义为 AB=(a,b):a A bB;其元素二元组(a,b)通常称为序偶或偶对(ordered pair);二元组(a,b)的第一分量上的元素a称为前者;第二分量上
3、的元素b称为后者;二重叉积的A B第一集合A称为前集;第二集合B称为后集。,6,离散数学,例1.A=a,b,c,B=0,1 AB=(a,0),(a,1),(b,0),(b,1),(c,0),(c,1)BA=(0,a),(0,b),(0,c),(1,a),(1,b),(1,c)例2.A=张三,李四,B=白狗,黄狗 AB=(张三,白狗),(张三,黄狗),(李四,白狗),(李四,黄狗)BA=(白狗,张三),(白狗,李四),(黄狗,张三),(黄狗,李四)一般地说,关于叉积和元组我们有:(1)(a,b)(b,a);(2)AB B A;(3)二元组不是集合,因为二元组中的分量计较顺,7,离散数学,序,而集
4、合中的元素是不讲顺序的。但是我们为了将所有的概念都统一于集合概念,我们可采用克亚托斯基(Kazimierz Kurafowski)在1921年给出的定义(a,b)=a,a,b将二元组定义为比其元素高二层的集合;(4)我们也可用二元组来递归的定义n元组如下:(a,b,c)=(a,b),c)(a1,a2,an-1,an)=(a1,a2,an-1),an)(5)这样,我们也就可用二重叉积来递归的定义n维叉积如下:ABC=(AB)C A1A2 An-1An=(A1A2 An-1)An,8,离散数学,(6)利用(5)所给的定义,我们可以递归的定义集合的叉积幂如下:A2=AA A3=A2 A An=An-
5、1 A(7)我们规定空集与任何集合A的叉积是空集。即 A=A由于若偶对的第一分量或第二分量不存在就没有偶对存在,故规定它们的叉积集合为空集是合理的。定理1.设A,B,C,D是四个非空的集合。那么AB=CD A=C B=D。,9,离散数学,证.):显然。):(采用逻辑法)对任何的元素a,b aAbB(a,b)AB(a,b)CD(条件:AB=CD)aCbD 所以A=C B=D。定理2.设A,B,C是三个集合。则(1)左分配律:A(BC)=(AB)(AC)(叉积对并的);(2)左分配律:A(BC)=(AB)(AC)(叉积对交的);(3)右分配律:(AB)C=(AC)(BC),10,离散数学,(叉积对
6、并的);(3)右分配律:(AB)C=(AC)(BC)(叉积对交的)。证.只证(1)(采用逻辑法)对任何的元素a,b(a,b)A(BC)aAb BC aA(bBbC)(aAbB)(aAbC)(分配律:p(qr)(pq)(pr)(a,b)AB(a,b)AC(a,b)(AB)(AC)所以 A(BC)=(AB)(AC)。,11,离散数学,2.关系一.关系的基本概念定义1.二元关系(binary relation)设A,B是两个非空的集合。二重叉集AB 的任何一个子集R都称为是从集合A到集合B的一种二元关系。即 RAB;当(a,b)R 时,称a与b有关系R,记为 aRb;当(a,b)R 时,称a与b没有
7、关系R,记为 或;当A=B时,即RAA,则称R是A上的一个二元关系。例1.设A是西安交通大学全体同学组成的集合。,12,离散数学,R=(a,b):aAbAa与b是同乡AA 于是,R是西安交通大学同学之间的同乡关系。例2.设A是某一大家庭。R1=(a,b):aAbAa是b的父亲或母亲AA R2=(a,b):aAbAa是b的哥哥或姐姐AA R3=(a,b):aAbAa是b的丈夫或妻子AA 于是,R1是父母与儿女之间的关系,即父母子女关系;R2是兄弟姐妹之间的关系,即兄弟姊妹关系;R3是夫妻之间的关系,即夫妻关系。例3.设N是自然数集合。,13,离散数学,R=(a,b):aNbNa|b NN 则R就
8、是自然数集合上的整除关系。例4.设是整数集合。R=(a,b):aIbI(kI)(a-b=km)II 则R就是整数集合上的(模m)同余关系。例5.设A是某一大型FORTRAN程序中诸程序块的集合。R=(a,b):aAbBa调用(call)b AA 则R就是程序块集合上的调用关系。例6.设A=风,马,牛,R=(风,马),(马,牛)AA 则R是A上的一个二元关系。,14,离散数学,关于关系概念,我们还有如下的几个定义和说明:1全关系(full relation):关系R=AB称为全关系;2空关系(empty relation):关系R=称为空关系;空关系和全关系都是平凡关系;3幺关系或单位关系(id
9、entical relation):关系R=(a,a):aA AA称为A上的幺关系;例7.设A=1,2,3,4,则 R1=(1,1),(2,2),(3,3),(4,4)是幺关系;R2=(1,1),(2,3),(3,4),(4,4)不是;R3=(1,1),(2,2),(3,3),(4,4),(1,2)也不是;,15,离散数学,4关系的交,并,余运算:叉积是一种(新型的)集合;关系是叉积的子集;因此,关系也是一种(新型的)集合;从而,有关集合论的一切概念、论述、运算也都适合于关系;尤其是集合的交,并,余,差运算也都适合于关系;因此,关系也有交,并,余,差运算;例8.设N是自然数集合。R=小于关系=
10、(m,n):mNnNmnNN S=整除关系=(m,n):mNnNm|nN N 则 R=大于等于关系();RS=小于等于关系();,16,离散数学,RS=不相等的整除关系();RS=小于又不整除关系();SR=相等关系(=)。5关系的扩充(expansion):若R1 R2,则称关系R2 是关系R1的一个扩充;6 n元关系:n元关系R是n 维叉积的一个子集;即 R A1A2 An,17,定义3.前域(domain)后域(codomain)设A,B是两个非空集合,R AB是一关系。则关系R的 前域:(R)=a:a A(bB)(aRb)A;后域:(R)=b:bB(aA)(aRb)B。例9.设A=1,
11、2,3,4,B=2,4,6,8,10。R=(1,2),(2,4),(3,6)。则(R)=1,2,3A,(R)=2,4,6B。二.关系的一些关联性质,离散数学,18,离散数学,定理1.设R1,R2 AB是两个关系。若 R1 R2,则(1)保序性:(R1)(R2);(2)保序性:(R1)(R2);证.只证(1)(采用逻辑法)对任何元素a A,a(R1)aA(bB)(a R1 b)aA(bB)(a,b)R1)aA(bB)(a,b)R2)(条件:R1 R2)aA(bB)(a R2 b)a(R2)所以(R1)(R2)。,19,定理2.设R1,R2是AB上的两个二元关系。则(1)(R1 R2)=(R1)(
12、R2)(2)(R1 R2)=(R1)(R2)(3)(R1 R2)(R1)(R2)(4)(R1 R2)(R1)(R2)证.只证(1),(3)(1)先证:(R1)(R2)(R1 R2)(采用包含法)由于R1 R1 R2,R2 R1 R2,依定理1,有(R1)(R1R2),(R2)(R1R2)故根据第一章2定理2的(3),就可得(R1)(R2)(R1 R2)。次证:(R1 R2)(R1)(R2)(采用元素,离散数学,20,离散数学,法)对任何元素a A,若a(R1 R2),则存在 bB,使得a R1 R2 b因此(a,b)R1 R2,从而有(a,b)R1或者(a,b)R2 即 aR1b或者 aR2b
13、于是 a(R)或者a(R2)故此 a(R1)(R2),21,离散数学,所以(R1 R2)(R1)(R2)。(3)先证:(R1 R2)(R1)(R2)(采用包含法)由于 R1R2 R1,R1R2 R2,依定理1,有(R1 R2)(R1),(R1 R2)(R2)故 根据第一章2定理2的(3),就可得(R1 R2)(R1)(R2)。其次,反方向的包含不成立。且看下面的反例。例9.设 R1=(1,1),(2,2),R2=(1,2),(2,1)。则,由于R1 R2=,故(R1 R2)=但是,由于(R1)=1,2,(R2)=1,2故(R1)(R2)=1,2,22,离散数学,所以(R1)(R2)(R1 R2
14、)。元素aA和集合A1A在关系R AB下的关联集(1)a的R-关联集(R-relative set of a):R(a)=b:bBaRb B;(2)A1的R-关联集(R-relative set of A1):R(A1)=b:bB(aA1)(aRb)B。于是,类似于定理1(2),定理2(2)(4),我们有定理.设R AB是一个二元关系,A1,A2 A。则(1)保序性:A1 A2 R(A1)R(A2);(2)R(A1A2)=R(A1)R(A2);(3)R(A1A2)R(A1)R(A2)。,23,离散数学,证.仿定理1(2),定理2(2)(4)可证。留给读者。例.设A=a,b,c,d,并且设 R=
15、(a,a),(a,b),(b,c),(c,a),(d,c),(c,b)。那么 R(a)=a,b,R(b)=c;并且如果 A1=c,d,那么 R(A1)=a,b,c。,24,离散数学,3.关系的表示关系的性质 一.关系表示法 1关系的矩阵表示法 设关系RAB,这里A,B是两个非空的有限集合,A=a1,a2,a3,am,B=b1,b2,b3,bn。则我们可用一个mn阶01矩阵MR来表示关系R,我们称此矩阵MR为关系R的关系矩阵(relation matrix)。MR=(xij)mn,其中 1 当(ai,bj)R时 xij=(i=1,m;j=1,n)0 当(ai,bj)R时,25,离散数学,例1.设
16、关系RAB,A=a1,a2,a3,a4,B=b1,b2,b3 R=(a1,b2),(a1,b3),(a2,b3),(a3,b1),(a4,b2)。于是,我们得到R的关系矩阵MR为(下面左矩阵)MR=;MS=例2.设关系SAA,A=a1,a2,a3,S=(a1,a1),(a2,a2),(a3,a3),(a1,a3),(a3,a1),(a2,a3),(a3,a2)于是,我们得到S的关系矩阵MS为(上面右矩阵),26,离散数学,2关系的图形表示法 设关系RAB,这里A,B是两个非空的有限集合,A=a1,a2,a3,am,B=b1,b2,b3,bn。则我们可用一个有向图GR=(VR,ER)来表示关系R
17、,我们称此有向图GR为关系R的关系图(relation digraph)。VR=AB,ER=R;VR中的元素称为结点,用小圆点表示;表示A中元素的结点放在左边一块;表示B中元素的结点放在右边一块;ER中的元素称为边,用有向弧表示;若aRb(即(a,b)R),则在表示a的结点和表示b的结点之间连一条有向弧。有向弧的始端与结点a相连,有向弧的终端与结点b相连;,27,离散数学,有时我们会用两个圆圈分别将表示两个集合A和B中元素的结点圈起来。所有有向弧的始端结点构成(R);所有有向弧的终端结点构成(R)。若A=B,这时令VR=A,并规定只画表示一个集合元素的结点;表示元素间关系的有向弧也只在此一个集
18、合的结点间画出。例3.设关系 RAB,A=a1,a2,a3,a4,B=b1,b2,b3 R=(a1,b2),(a1,b3),(a2,b3),(a3,b1),(a4,b2)于是,我们得到R的关系图GR为下面左图。,28,离散数学,例4.设关系SAA,A=a1,a2,a3,S=(a1,a1),(a2,a2),(a3,a3),(a1,a3),(a3,a1),(a2,a3),(a3,a2)于是,我们得到S的关系图GS为上面右图。注:图中各结点所带的小圆圈称为自反圈;一对结点间的来回边称为双向弧;否则,一对结点间只有一条边,则此边称为单向弧。关系的表示法有三种:集合表示法,矩阵表示法,图形表示法。,29
19、,离散数学,二.关系的性质 设二元关系RXX(或者说RX2),这里X是一集合。则R称为是X上的 1自反关系(reflexive relation):当且仅当R满足 自反性:(xX)(xRx);显然,对于自反关系R,(R)=(R)=X。反自反关系(irreflexive relation):当且仅当R满足 反自反性:(x X)()或(x X)(xRx);常见的自反关系有相等关系(=),小于等于关系(),包含关系()等;而不相等关系(),小于关系(),真包含关系()等都不是自反关系,它们都是反自反关系。,30,离散数学,注:自反性和反自反性是关系的两个极端性质;因此,自反关系和反自反关系是两种极端
20、关系;从关系矩阵来看:自反关系关系矩阵的对角线上元素全是1;反自反关系关系矩阵的对角线上元素全是0;从关系图来看:自反关系关系图的各结点上全都有自反圈;反自反关系关系图的各结点上全都没有自反圈。例5.设 X=a,b,c,d。则关系R1=(a,b),(a,a),(b,b),(c,d),(c,c),(d,d)是X上的自反关系,但不是X上的幺关系,因(a,b),(c,d)R1;而关系 R2=(a,a),(b,b),(c,c),(d,d)是X上的自反关系,同时也是X上的幺关系;R3=(a,b),(a,c),(a,d),(c,d),31,离散数学,是X上的反自反关系。注:由此例可知幺关系一定是自反关系,
21、但自反关系不一定是幺关系。2对称关系(symmetric relation):当且仅当R满足 对称性:(xX)(yX)(xRy yRx);3反对称关系(antisymmetric relation):当且仅当R满足 反对称性:(xX)(yX)(xRyyRxx=y);常见的对称关系有相等关系(=),不相等关系(),同余关系,朋友关系,同学关系,同乡关系等;而小于等于关系(),包含关系(),上下级关系,父子关系等都不是对称关系,它们都是反对称关系。,32,离散数学,注:对称性和反对称性是关系的两个极端性质;因此,对称关系和反对称关系是两种极端关系;从关系矩阵来看:对称关系的关系矩阵是对称矩阵。即x
22、ij=xji(1i,j n);反对称关系的关系矩阵满足如下性质 xij=1 xji=0(1i,j n);从关系图来看:对称关系关系图的结点间若有弧则都是双向弧;反对称关系关系图的结点间若有弧则都是单向弧;例6.设X=a,b,c。则关系 R1=(a,b),(b,a),R2=(a,a),(b,b)都是X上的对称关系;而关系 R3=(a,b),(b,a),(b,c)不是X上的对称关系;因(b,c)R3,但(c,b)R3。,33,离散数学,例7.设X=a,b,c。则关系 R1=(a,a),(a,b),(a,c),(c,b),(c,c)是X上的反对称关系;而关系 R2=(a,a),(a,b),(a,c)
23、,(b,a),(c,b)不是X上的反对称关系;因(a,b)R2 且(b,a)R2,但ab。4传递关系(transitive relation):当且仅当R满足传递性:(xX)(yX)(zX)(xRy yRzxRz);反传递关系(antisymmetric relation):当且仅当R满足 反传递性:(xX)(yX)(zX)(xRy yRz);常见的传递关系有相等关系(=),小于等于关系(),包含关系(),整除关系,同余关系,上下级,34,离散数学,关系,同乡关系,后裔关系等;而不相等关系(),父子关系,朋友关系,同学关系等都不是传递关系。注:传递性和反传递性是关系的两个极端性质;因此,传递关
24、系和反传递关系是两种极端关系;概念反传递性和反传递关系一般不甚用,所以不加讨论;例8.设X=a,b,c,d。则关系 R1=(a,b),(b,c),(a,c),(c,d),(a,d),(b,d)是X上的传递关系;而关系 R2=(a,b),(b,c),(a,c),(c,d),(a,d)不是X上的传递关系;因(b,c)R2且(c,d)R2,但(b,d)R2。,35,离散数学,例9.设X是平面上直线的集合。平行关系 R=(x,y):xX yX xy 由平面几何的知识知:若xy且yz,则 xz。由传递关系的定义知R是X上的传递关系。例10.设X是平面上三角形的集合。相似关系 R=(x,y):xX yX
25、xy 由平面几何的知识知:若xy 且yz,则 xz。由传递关系的定义知R是X上的传递关系。例11.相等关系是自反的、对称的、反对称的、传递关系。全关系X2是自反的、对称的、传递的。幺关系I 是自反的、对称的、反对称的、传递的。,36,离散数学,空关系是反自反的、对称的、反对称的、传递的。,37,离散数学,4.关系的运算 1关系的逆运算定义1.逆运算(converse operation)设A,B是两个非空的集合。我们称一元运算:2A B 2 B A 对任何二元关系RAB,使得=(b,a):bBaAaRbBA为关系的逆运算;称 是R的逆关系(converse of relation)。显然,对任
![离散数学第二章关系.ppt_第1页](https://www.31ppt.com/fileroot1/2023-5/28/5d1d84e0-d045-4df5-add7-41cc2abe21bd/5d1d84e0-d045-4df5-add7-41cc2abe21bd1.gif)
![离散数学第二章关系.ppt_第2页](https://www.31ppt.com/fileroot1/2023-5/28/5d1d84e0-d045-4df5-add7-41cc2abe21bd/5d1d84e0-d045-4df5-add7-41cc2abe21bd2.gif)
![离散数学第二章关系.ppt_第3页](https://www.31ppt.com/fileroot1/2023-5/28/5d1d84e0-d045-4df5-add7-41cc2abe21bd/5d1d84e0-d045-4df5-add7-41cc2abe21bd3.gif)
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学 第二 关系
![提示](https://www.31ppt.com/images/bang_tan.gif)
链接地址:https://www.31ppt.com/p-6010490.html