《离散数学第二章关系.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
2、元组(n-tuple);即,叉积是元组的集合; 每个n元组(a1, a2, , an)的第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
3、 ; 其元素二元组(a, b)通常称为序偶或偶对(ordered pair) ; 二元组(a, b)的第一分量上的元素a称为前者;第二分量上的元素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=(白狗,张三),(白狗,李四)
4、,(黄狗,张三),(黄狗,李四) 一般地说,关于叉积和元组我们有: (1) (a, b) (b, a); (2) AB B A ; (3)二元组不是集合,因为二元组中的分量计较顺,7,离散数学,序,而集合中的元素是不讲顺序的。但是我们为了将所有的概念都统一于集合概念,我们可采用克亚托斯基(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
5、)这样,我们也就可用二重叉积来递归的定义n维叉积如下: ABC=(AB)C A1A2 An-1An= (A1A2 An-1)An,8,离散数学,(6)利用(5)所给的定义,我们可以递归的定义集合的叉积幂如下: A2= AA A3 = A2 A An = An-1 A (7)我们规定空集与任何集合A的叉积是空集 。 即 A = = A 由于若偶对的第一分量或第二分量不存在就没有偶对存在,故规定它们的叉积集合为空集是合理的。 定理1.设A,B,C,D是四个非空的集合。那么 AB = CD A = C B = D 。,9,离散数学,证.):显然。 ):(采用逻辑法)对任何的元素a,b aAbB (a
6、,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,离散数学,(叉积对并的); (3)右分配律:(AB)C = (AC)(BC) (叉积对交的)。 证.只证(1)(采用逻辑法) 对任何的元素a,b (a,b)A(BC) aAb BC aA(bBbC) (aAbB)(aAbC) (分配律:p(qr)(pq)(pr) (a
7、,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没有关系R ,记为 或 ; 当A=B时,即RAA,则称R是A上的一个二元关系。 例1 . 设A是西安交通大学全体同学组成的集合。,12,离散数学,R=(a,b) : aAbAa与b是同乡AA 于是
8、,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就是自然数集合上的整除关系。 例4 . 设是整数集合。 R= (a,b) : aIbI(kI)(a-b =km) II 则R就是
9、整数集合上的(模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幺关系或单位关系(identical relation): 关系R= (a, a):
10、 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是自
11、然数集合。 R=小于关系=(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)(
12、aRb)A ; 后域: (R) = b : bB(aA)(aRb) B 。 例9 .设A=1,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) (条件:
13、R1 R2 ) aA(bB)(a R2 b) a (R2 ) 所以 (R1) (R2) 。,19,定理2 . 设R1, R2是AB上的两个二元关系。则 (1) (R1 R2) = (R1) (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)
14、 (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 于是 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) , (
15、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) 。 元素aA和集合A1A在关系R AB下的关联集 (1)a的R-关联集(R-relative set of a): R(a)=b : bBaRb B ; (2
16、) 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=(a,a),(a,b),(b,c),(c,a),(d,c),(c,b)。 那么 R(a)= a,b,
17、 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 .设关系 RAB ,A= a1,a2,
18、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 。 则我们
19、可用一个有向图GR=(VR,ER)来表示关系R,我们称此有向图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,并规
20、定只画表示一个集合元素的结点;表示元素间关系的有向弧也只在此一个集合的结点间画出 。 例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为上面右图。 注: 图中各结点所带的小圆圈称为自反圈;一对结点间
21、的来回边称为双向弧;否则,一对结点间只有一条边,则此边称为单向弧。 关系的表示法有三种:集合表示法,矩阵表示法,图形表示法。,29,离散数学,二 .关系的性质 设二元关系RXX(或者说RX2),这里X是一集合。则R称为是X上的 1自反关系(reflexive relation):当且仅当R满足 自反性:(xX)(xRx) ; 显然,对于自反关系R, (R) = (R) = X 。 反自反关系(irreflexive relation):当且仅当R满足 反自反性:(x X)( ) 或(x X)(xRx) ; 常见的自反关系有相等关系(=),小于等于关系(),包含关系()等; 而不相等关系(),小
22、于关系(),真包含关系()等都不是自反关系,它们都是反自反关系。,30,离散数学,注: 自反性和反自反性是关系的两个极端性质;因此,自反关系和反自反关系是两种极端关系; 从关系矩阵来看:自反关系关系矩阵的对角线上元素全是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),
23、(d,d) 是X上的自反关系,同时也是X上的幺关系; R3=(a,b),(a,c),(a,d),(c,d),31,离散数学,是X上的反自反关系。 注:由此例可知幺关系一定是自反关系,但自反关系不一定是幺关系。 2对称关系(symmetric relation):当且仅当R满足 对称性:(xX)(yX)(xRy yRx) ; 3反对称关系(antisymmetric relation):当且仅当R满足 反对称性:(xX)(yX)(xRyyRxx = y) ; 常见的对称关系有相等关系(=),不相等关系(),同余关系,朋友关系,同学关系,同乡关系等; 而小于等于关系(),包含关系(),上下级关系,
24、父子关系等都不是对称关系,它们都是反对称关系。,32,离散数学,注:对称性和反对称性是关系的两个极端性质;因此,对称关系和反对称关系是两种极端关系; 从关系矩阵来看:对称关系的关系矩阵是对称矩阵。即xij = 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上的
25、对称关系;因(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) ,(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
26、yRz ) ; 常见的传递关系有相等关系(=),小于等于关系(),包含关系(),整除关系,同余关系,上下级,34,离散数学,关系,同乡关系,后裔关系等; 而不相等关系(),父子关系,朋友关系,同学关系等都不是传递关系。 注:传递性和反传递性是关系的两个极端性质;因此,传递关系和反传递关系是两种极端关系; 概念反传递性和反传递关系一般不甚用,所以不加讨论; 例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)
27、 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 xy 由平面几何的知识知:若xy 且yz ,则 xz 。 由传递关系的定义知R是X上的传递关系。 例11. 相等关系是自反的、对称的、反对称的、传递关系。 全关系X2是自反的、对称的、传递的。 幺关系I 是自反的、对称的、反对称的、传递的。,36,离散数学,空关系是反自反的、对称的、反对
28、称的、传递的。,37,离散数学,4 .关系的运算 1关系的逆运算 定义1.逆运算(converse operation) 设A,B是两个非空的集合。我们称一元运算 : 2A B 2 B A 对任何二元关系RAB,使得 = (b,a) : bBaAaRbBA 为关系的逆运算;称 是R的逆关系(converse of relation)。 显然,对任何(b,a) BA,b a aRb ;并且 。,38,离散数学,例1.设A=a,b,c ,B=1,2。则关系 R=(a,1),(a,2),(b,2),(c,1) 的逆关系 =(1,a),(2,a),(2,b),(1,c) 。 定理1.逆运算基本定理 设
29、两个关系R AB,S AB,这里 A,B是两个非空的集合。则有 (1)反身律: =R ; (2)保序性:RS ; R=S = ; (3)分配律:RS= (逆对并的); (4)分配律:RS= (逆对交的); (5)XY=YX ;,39,离散数学,(6) = ; (7)交换律:(R)=( ) (逆与余的); (8)分配律:RS= (逆对差的); 证.只证(1),(4),(7) (采用逻辑法) (1)对任何(a,b)AB ,有 (a,b) (b,a) (a,b)R 所以 =R 。 (4)对任何(a,b)BA ,有 (a,b)RS (b,a)RS,40,离散数学, (b,a)R(b,a) S (a,b
30、) (a,b) (a,b) 所以 RS = 。 (7)对任何(a,b)BA ,有 (a,b)(R) (b,a)R (b,a)R (a,b) (a,b)( ) 所以 (R)= ( ) 。,41,离散数学,2关系的合成运算 定义2.合成运算(composition operation) 设A,B是两个非空的集合。我们称二元运算 o : 2A B 2B C 2 AC 对任何两个二元关系R AB , S BC ,使得 RoS =(a,c) : aAcC(bB)(aRbbSc)AC 为关系的合成运算;称RoS是R与S的合成关系。 显然,对任何(a,c)AC,aRoSc(bB)(aRbbSc) 。 例2
31、.设A= a1,a2,a3 ,B=b1,b2 ,C=c1, c2, c3, c4 关系 RAB , SBC R =(a1, b1),(a2, b2),(a3, b1) S =(b1, c4),(b2, c2),(b2, c3),42,离散数学,于是,我们得到R与S的合成关系为 R o S =(a1, c4),(a2, c2) ,(a2, c3),(a3, c4) 其合成关系的关系图为 例3.设A是老年男子的集合,B是中年男子的集合,C是青少年男子的集合。 R是由A到B的父子关系, R AB,43,离散数学,S 是由B到C的父子关系, SBC 则复合关系R o S是A到C的祖孙关系。 定理2.合
32、成运算基本定理 设R,R1,R2 AB, S,S1,S2 BC,T CD ,这里 A,B,C,D是四个非空的集合。则 (1)R o = o S = ; (2)( R o S ) ( R );( R o S ) (S ); (3)保序性:R1 R2 S1 S2 R1 o S1 R2 o S2 ; (4)结合律:R o (S o T) = (R o S) o T; (5)左分配律:R o (S1S2) = (R o S1) (R o S2) ; (合成运算对并的) 右分配律: (S1S2) o T = (S1 o T) (S2 o T); (合成运算对并的) (6)左分配不等式: R o (S1S
33、2) (R o S1)(R o S2);,44,离散数学,(合成运算对交的) 右分配不等式: (S1 S2) o T (S1 o T)(S2 o T); (合成运算对交的) (7) 鞋袜律:(R o S) = S o R 。 证.只证(4),(5) (采用逻辑法) (4)对任何元素aA,dD ,有 a R o (S o T)d (bB)(aRb b(S o T)d) (bB)(aRb (cC)(bSccTd) (bB)(cC)(aRb(bSccTd) (量词前移:pxA(x) x(pA(x) ) (cC)(bB)(aRb(bSccTd) (量词交换:xyA(x,y)yxA(x,y) ),45,
34、离散数学, (cC)(bB)(aRbbSc)cTd) (的结合律:p(q r)(p q ) r ) (cC)(bB)(aRbbSc)cTd) (量词后移:x(pA(x) pxA(x) ) (cC)(a(R o S)ccTd) a(R o S) o Td 所以 R o (S o T) = (R o S) o T; (5)对任何元素aA,cC ,有 a R o (S1S2)c (bB)(aRb b(S1S2)c) (bB)(aRb (bS1cbS2c) (bB)(aRbbS1c)(aRbbS2c) (对的分配律:p(qr)(p q ) (p r ) ),46,离散数学,(bB)(aRbbS1c)(
35、bB)(aRbbS2c) (量词对的分配律:x(A(x)B(x) x(A(x)xB(x) ) a(R o S1)c a (R o S2)c a(R o S1)(R o S2)c 所以 R o (S1S2) = (R o S1)(R o S2) 。 但是合成运算不满足交换律。即,一般 R o SS o R 例4.设A=a,b,c,d,e 。则关系 R=(a,b),(c,d),(b,b),S=(b,e),(c,a),(a,c),(d,b) 的合成关系为,47,离散数学,R o S= (a,e),(b,e),(c,b),So R =(a,d),(c,b),(d,b) 所以 R o SS o R 。
36、3关系矩阵的合成运算 设R AB , SBC 是两个二元关系,其合成关系为R o S。这里A= a1,a2,am ,B=b1,b2 , , bl ,C=c1, c2, ,cn。 并设它们的关系矩阵分别为 MR=(xij)ml , MS=(yij)ln , MR o S =(uij)mn 则我们有: MR o S = MR o MS 其中:我们令 MR o MS = (tij)mn tij = (xik ykj) (1i m,1 j n),48,离散数学,注:这里关系矩阵的合成运算与线性代数中的一般矩阵的乘法运算颇为相似。所不同的是:乘法现在换成布尔乘();加法现在换成布尔加()。值得注意的是:
37、这里的布尔加1 1=1(不进位),而非1 1=0(进位)。 例5.设A=a,b,c,d,e 。则关系 R=(a,b),(c,d),(b,b),S=(b,e),(c,a),(a,c),(d,b) 的合成关系 R o S= (a,e),(b,e),(c,b) 其关系矩阵分别为 MR = MS= MR o S =,49,离散数学,现在我们计算 MR o MS = = 其中: t25= (x2k yk5) =(x21y15)(x22y25)(x23y35)(x24y45)(x25y55) =(0 0) (11) (0 0) (0 0) (0 0) =0 1 0 0 0 =1 这说明 MR o S =
38、MR o MS 。 下面我们就来证明这个等式: 证.(采用逻辑法),50,离散数学,对任何的i ,j (1i m,1 j n) ,有 uij =1 aiR o Scj (bB)(aiRb bScj ) (aiRb1 b1Scj ) (aiRb2 b2Scj ) (aiRblblScj ) (xi1 =1 y1j =1) (xi2 =1 y2j =1) (xil =1 ylj =1) (这里: 是命题的真值联结词且; 是命题的真值联结词或。) (xi1 y1j ) (xi2 y2j ) (xil ylj ) =1 (这里: 是布尔乘; 是布尔加。) (xik ykj)=1 tij = 1 即 u
39、ij = tij 因此 (uij)mn = (tij)mn 所以 MR o S = MR o MS 。,51,离散数学,4关系的闭包运算(宏运算) 定义3.关系的合成幂(nth power) 设二元关系R AA,nN 。这里A 是一个非空的集合, N 是自然数集。我们规定: (1) R0 =I (这里I=IA=(a,a) : aA是A上的幺关系); (2) R1 =R; (3) Rn+1 =RnoR (特别地:R2 =RoR )。 定理3.指数律 设二元关系R AA,m ,nN 。这里 A是一个非空的集合, N 是自然数集。则 (1)交换律: RmoRn = RnoRm= Rm+n ; 特别地
40、: IoR = RoI= R (幺关系是合成运算的幺元); (2)交换律: (Rm)n = (Rn)m= Rmn 。,52,离散数学,证. (采用数学归纳法) 只证(1)的一个等式: RmoRn = Rm+n ;另一个等式: RnoRm= Rm+n 同理可证。 归纳变量选取n(让m固定) n=0时, RmoR0 = RmoI (定义3的(1):R0 =I) = Rm n=1时, RmoR1 = RmoR (定义3的(2):R1 =R) = Rm+1 (定义3的(3) 结论成立; n=k时,假设结论成立。即 RmoRk = Rm+k ; n=k+1时, RmoRk+1= Rmo(RkoR) (定
41、义3的(3) = (RmoRk )oR (结合律) = Rm+koR (归纳假设) = Rm+k+1 (定义3的(3),53,离散数学,结论成立; 根据数学归纳法,即证明了该结论。 例6.设二元关系R AA,这里A=a,b,c ,R=(a,b),(c,b)。从而有 I=(a,a),(b,b),(c,c) , =(b,a),(b,c) o R=(b,b) ,R o =(a,a),(a,c),(c,a),(c,c) 于是 o R I ,R o I , o R R o 。 注: 这个例子说明一般情况下逆关系不是关系合成运算的逆元; 由定理2的(1)有: o R = R o = ,这说明空集是合成运算
42、的零元。 一般地 a Rnb (c1)(c2) (cn-1)(aRc1 c1Rc2 cn-1Rb) ; 特别地 a Rb (c) (aRc cR b) 。,54,离散数学,定义4.闭包运算(closure operation) 设二元关系R AA 。这里A 是一个非空的集合。我们定义: (1)传递闭包(transitive closure): R = Rk =R R R3 Rk ; (2)自反传递闭包(reflexive and transitive closure): R = Rk =IR R R3 Rk 。,55,离散数学,注:传递闭包有时也记为t( R);自反传递闭包有时也记为rt( R
43、);其实还有别的闭包; a Rb (kN)(k 1)(aRkb) ; a R b (kN)(aRkb) (a=b)(kN)(k 1)(aRkb)(a=b)(aRb) 。 定理4.传递闭包基本定理 设二元关系R AA,R 。则 (1)若 mN,m 1 ,则 Rm R ;特别地 R R ; (2) R是传递关系:即,对任何元素 a,b,c A , aRbbRcaRc ; (3) R是包含R的最小传递关系:即,对任何二元关系SAA,若RS且S也是传递关系,那么 RS ; (4)若|A|=n ,则 R = Rk ;这时,56,离散数学,a Rb (kN)(1k n)(aRkb) ; (5)若R是传递关系, 则 R = R 。 证.只证(2)(采用逻辑法) (2)对任何元素a,b,c A ,有 aRbbRc (k)(aRkb)(l)(bRlc) (这里k 1, l 1) (x1)(x2) (xk-1)(aRx1 x1Rx2 xk-1Rb) (y1)(y2) (yl-1)(bRy1 y1Ry2 yl-1Rc) (x1)(x2) (xk-1)(aRx1 x1Rx2
链接地址:https://www.31doc.com/p-2096465.html