离散数学 第二章 关系.ppt

《离散数学 第二章 关系.ppt》由会员分享，可在线阅读，更多相关《离散数学 第二章 关系.ppt（108页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、离散数学离散数学西安交通大学西安交通大学电子与信息工程学院电子与信息工程学院计算机软件所计算机软件所刘国荣刘国荣1 等价关系等价关系叉积叉积关系关系幺关系幺关系元组元组全关系全关系传递闭包传递闭包逆关系逆关系复合关系复合关系关系幂关系幂自反传递闭包自反传递闭包自反关系自反关系对称关系对称关系反对称关系反对称关系传递关系传递关系半序关系半序关系空关系空关系余关系余关系并关系并关系差关系差关系交关系交关系2离散数学 第二章第二章 关系关系 (relation)1.集合的叉积集合的叉积n元组元组 2.关系关系 3.关系的关系的表示表示关系的性质关系的性质 4.关系的运算关系的运算 5.等价关系等价关

2、系 6.半序关系半序关系3离散数学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,an)的第i个位置上的元素ai称为该n元组的第i个分量（坐标或投影）；元组各分量的顺序不能改变；n 称为该叉积及其元组的维数；两个元组相等它们的维数相同且对应的分量相等。4离

3、散数学即(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称为前者；第二分量上的元素b称为后者；二重叉积的A B第一集合A称为前集；第二集合B称为后集。5离散数学例例1.A=a,b,c,B=0,1 AB=(a,0),(a,1),(b,0),(b,1),

4、(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)二元组不是集合，因为二元组中的分量计较顺6离散数学序,而集合中的元素是不讲顺序的。但是我们为了将所有的概念都统一于集合概念，我们可采用克亚托斯基(Kazimierz Kurafowski)在1921年给出的定义(a,b)=a,a,b将二元组

5、定义为比其元素高二层的集合；(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)An7离散数学 (6)利用(5)所给的定义，我们可以递归的定义集合的叉积幂如下：A2=AA A3=A2 A An=An-1 A (7)我们规定空集与任何集合A的叉积是空集。即 A=A由于若偶对的第一分量或第二分量不存在就没有偶对存在，故规定它们的叉积集合为空集是合理的。定理定理1.设A,B,C,D是四个非

6、空的集合。那么AB=CD A=C B=D。8离散数学证.):显然。)：（采用逻辑法）对任何的元素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)9离散数学 (叉积对并的)；(3)右分配律：(AB)C=(AC)(BC)(叉积对交的)。证.只证(1)（采用逻辑法）对任何的元素a,b(a,b)A(BC)aAb BC aA(bBbC)(aAbB)(a

7、AbC)(分配律：p(qr)(pq)(pr)(a,b)AB(a,b)AC (a,b)(AB)(AC)所以 A(BC)=(AB)(AC)。10离散数学 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是西安交通大学全体同学组成的集合。11离散数学 R=(a,b):aAbAa与

8、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是自然数集合。12离散数学 R=(a,b):aNbNa|b NN 则R就是自然数集合上的整除关系。例例4.设是整数集合。R=(a,b):aIbI(kI)(a-b=km)II 则R就是整数集合上的(模m)同余关系。例例5.设A是某一

9、大型FORTRAN程序中诸程序块的集合。R=(a,b):aAbBa调用(call)b AA 则R就是程序块集合上的调用关系。例例6.设A=风，马，牛，R=(风,马)，(马,牛)AA 则R是A上的一个二元关系。13离散数学 关于关系概念，我们还有如下的几个定义和说明：1全关系(full relation)：关系R=AB称为全关系；2空关系(empty relation)：关系R=称为空关系；空关系和全关系都是平凡关系；3幺关系或单位关系(identical relation)：关系R=(a,a):aA AA称为A上的幺关系；例例7.设A=1,2,3,4，则 R1=(1,1),(2,2),(3,3

10、),(4,4)是幺关系；R2=(1,1),(2,3),(3,4),(4,4)不是；R3=(1,1),(2,2),(3,3),(4,4),(1,2)也不是；14离散数学 4关系的交，并，余运算：叉积是一种（新型的）集合；关系是叉积的子集；因此，关系也是一种（新型的）集合；从而，有关集合论的一切概念、论述、运算也都适合于关系；尤其是集合的交，并，余，差运算也都适合于关系；因此，关系也有交，并，余，差运算；例例8.设N是自然数集合。R=小于关系=(m,n):mNnNmnNN S=整除关系=(m,n):mNnNm|nN N 则 R=大于等于关系()；RS=小于等于关系()；15离散数学 RS=不相等的

11、整除关系()；RS=小于又不整除关系()；SR=相等关系(=)。5关系的扩充(expansion)：若R1 R2，则称关系R2 是关系R1的一个扩充；6 n元关系：n元关系R是n 维叉积的一个子集；即 R A1A2 AnR1R216定义定义3.前域(domain)后域(codomain)设A,B是两个非空集合，R AB是一关系。则关系R的 前域：(R)=a:a A(bB)(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 。二二.关系的一些关联性

12、质关系的一些关联性质离散数学A(R)B(R)abR17离散数学定理定理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)。18定理定理2.设R1,R2是AB上的两个二元关系。则 (1)(R1 R2)=(R1)(R2)(2)(R1 R2)=(R1)(R2)(3)(R1 R2)(R1)(R2)(4)(R1 R2

13、)(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)(采用元素离散数学19 离散数学法)对任何元素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)20离散数学 所以 (R1 R2)(R1

14、)(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 21离散数学 所以 (R1)(R2)(R1 R2)。w元素元素a A和集合和集合A1 A在关系在关系R AB下的关联集下的关联集 (1)

15、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)。22离散数学证.仿定理1(2)，定理2(2)(4)可证。留给读者。例例.设A=a,b,c,d，并且设 R=(a,a),(a,b),(b,c),(c,a),(d

16、,c),(c,b)。那么 R(a)=a,b，R(b)=c；并且如果 A1=c,d，那么 R(A1)=a,b,c。23离散数学 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时24离散数学例例1.设关系RAB ，A=a1,

17、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为(上面右矩阵)b1b2b31a1a2a3a4001011010010a1a2a31a1a2a3011125离散数学 2关系的图形表示法 设关系RAB，这里A,B是两个非空的有限集合，A=a1,a2,a3,am ，B=b1,

18、b2,b3,bn 。则我们可用一个有向图GR=(VR,ER)来表示关系R，我们称此有向图GR为关系R的关系图(relation digraph)。VR=AB，ER=R；VR中的元素称为结点，用小圆点表示；表示A中元素的结点放在左边一块；表示B中元素的结点放在右边一块；ER中的元素称为边，用有向弧表示；若aRb(即(a,b)R)，则在表示a的结点和表示b的结点之间连一条有向弧。有向弧的始端与结点a相连，有向弧的终端与结点b相连；26离散数学 有时我们会用两个圆圈分别将表示两个集合A和B中元素的结点圈起来。所有有向弧的始端结点构成(R)；所有有向弧的终端结点构成(R)。若A=B，这时令VR=A，并

19、规定只画表示一个集合元素的结点；表示元素间关系的有向弧也只在此一个集合的结点间画出。例例3.设关系 RAB，A=a1,a2,a3,a4，B=b1,b2,b3 R=(a1,b2),(a1,b3),(a2,b3),(a3,b1),(a4,b2)于是，我们得到R的关系图GR为下面左图。27离散数学例例4.设关系SAA ，A=a1,a2,a3，S=(a1,a1),(a2,a2),(a3,a3),(a1,a3),(a3,a1),(a2,a3),(a3,a2)于是，我们得到S的关系图GS为上面右图。注：图中各结点所带的小圆圈称为自反圈；一对结点间的来回边称为双向弧；否则，一对结点间只有一条边，则此边称为单

20、向弧。关系的表示法有三种:集合表示法,矩阵表示法,图形表示法。a1a2a3a4b1b2b3RABGRa1a2a3GS28离散数学 二二.关系的性质关系的性质 设二元关系RXX(或者说RX2)，这里X是一集合。则R称为是X上的 1自反关系(reflexive relation)：当且仅当R满足 自反性：(xX)(xRx)；显然，对于自反关系R，(R)=(R)=X。反自反关系(irreflexive relation)：当且仅当R满足 反自反性：(x X)()或(x X)(xRx)；常见的自反关系有相等关系(=)，小于等于关系()，包含关系()等；而不相等关系()，小于关系()，真包含关系()等都

21、不是自反关系，它们都是反自反关系。29离散数学注：自反性和反自反性是关系的两个极端性质；因此，自反关系和反自反关系是两种极端关系；从关系矩阵来看：自反关系关系矩阵的对角线上元素全是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上的幺关系；

22、R3=(a,b),(a,c),(a,d),(c,d)30离散数学是X上的反自反关系。注：由此例可知幺关系一定是自反关系，但自反关系不一定是幺关系。2对称关系(symmetric relation)：当且仅当R满足 对称性：(xX)(yX)(xRy yRx)；3反对称关系(antisymmetric relation)：当且仅当R满足 反对称性：(xX)(yX)(xRyyRxx=y)；常见的对称关系有相等关系(=)，不相等关系()，同余关系，朋友关系，同学关系，同乡关系等；而小于等于关系()，包含关系()，上下级关系，父子关系等都不是对称关系，它们都是反对称关系。31离散数学注：对称性和反对称性

23、是关系的两个极端性质；因此，对称关系和反对称关系是两种极端关系；从关系矩阵来看：对称关系的关系矩阵是对称矩阵。即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上的对称关系；因(b,c)R3,但(c,b)R3。32离散数学例例7.设X=a,b,c。则关系 R1=(a,a),

24、(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 yRz )；常见的传递关系有相等关系(=)，小于等于关系()，包含关系()，整除关系，同余关系，上下级33离散数学关系，同乡关系，后裔关系等；而不相等

25、关系()，父子关系，朋友关系，同学关系等都不是传递关系。注：传递性和反传递性是关系的两个极端性质；因此，传递关系和反传递关系是两种极端关系；概念反传递性和反传递关系一般不甚用，所以不加讨论；例例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。34离散数学例例9.设X是平面上直线的集合。平行关系 R=(x,y):xX yX xy 由平面几何的知识知:若xy且yz，则 xz。由

26、传递关系的定义知R是X上的传递关系。例例10.设X是平面上三角形的集合。相似关系 R=(x,y):xX yX xy 由平面几何的知识知:若xy 且yz，则 xz。由传递关系的定义知R是X上的传递关系。例例11.相等关系是自反的、对称的、反对称的、传递关系。全关系X2是自反的、对称的、传递的。幺关系I 是自反的、对称的、反对称的、传递的。35离散数学 空关系是反自反的、对称的、反对称的、传递的。36离散数学 4.关系的运算关系的运算 1关系的逆运算关系的逆运算定义定义1.逆运算(converse operation)设A，B是两个非空的集合。我们称一元运算 :2A B 2 B A 对任何二元关系

27、RAB，使得 =(b,a):bBaAaRbBA为关系的逆运算；称 是R的逆关系(converse of relation)。显然，对任何(b,a)BA，b a aRb；并且 。37离散数学例例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.逆运算基本定理 设两个关系R AB，S AB，这里 A,B是两个非空的集合。则有 (1)反身律：=R；(2)保序性：RS ；R=S =；(3)分配律：RS=（逆对并的）；(4)分配律：RS=（逆对交的）；(5)XY=YX；38离散数学 (6)=；

28、(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)RS39离散数学 (b,a)R(b,a)S (a,b)(a,b)(a,b)所以 RS=。(7)对任何(a,b)BA，有 (a,b)(R)(b,a)R (b,a)R (a,b)(a,b)()所以 (R)=()。40离散数学 2关系的合成运算关系的合成运算定义定义2.合成运算(composition operation)设A，B是两个非空的集合。我

29、们称二元运算 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.设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)41离散数学 于是，我们得到R与S的合成关系为 R o S=(a1,c4),(a2,c2),(a2,c3),(a3,c4)其合成关系的关系图为例

30、例3.3.设A是老年男子的集合，B是中年男子的集合，C是青少年男子的集合。R是由A到B的父子关系，R AB b1b2Ba1a2a3Ac1c2c3c4CRSRoS42离散数学 S 是由B到C的父子关系，SBC 则复合关系R o S是A到C的祖孙关系。定理定理2.合成运算基本定理 设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

31、o(S1S2)=(R o S1)(R o S2)；(合成运算对并的)右分配律：(S1S2)o T=(S1 o T)(S2 o T)；(合成运算对并的)(6)左分配不等式：R o(S1S2)(R o S1)(R o S2)；43离散数学(合成运算对交的)右分配不等式：(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)(量词

32、前移：pxA(x)x(pA(x)(cC)(bB)(aRb(bSccTd)(量词交换：xyA(x,y)yxA(x,y)44离散数学 (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

33、 q)(p r)45离散数学 (bB)(aRbbS1c)(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)的合成关系为 46离散数学 R o S=(a,e),(b,e),(c,b)，So R=(a,d),(c,b),(d,b)所以 R

34、o SS o R 。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)47离散数学注：这里关系矩阵的合成运算与线性代数中的一般矩阵的乘法运算颇为相似。所不同的是：乘法现在换成布尔乘()；加法现在换成布尔加()。值得注意的是：这里的布尔加1 1=

35、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=48离散数学现在我们计算 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=MR o MS。下面我们就来证明这个等式：证.（采用逻辑法）49离散数学对

36、任何的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 即 uij=tij因此(uij)mn=(tij)mn 所以MR o S=MR o MS。50离散数学 4关系的闭包运算（宏运算）关系的闭包运算（宏运算）定义定义3

37、.关系的合成幂(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；特别地：IoR=RoI=R(幺关系是合成运算的幺元)；(2)交换律：(Rm)n=(Rn)m=Rmn。51离散数学证.（采用数学归纳法）只证(1)的一个等式：RmoRn=Rm+n；另一个等式：RnoRm=Rm+n

38、 同理可证。归纳变量选取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)(定义3的(3)=(RmoRk)oR (结合律)=Rm+koR (归纳假设)=Rm+k+1 (定义3的(3)52离散数学 结论成立；根据数学归纳法，即证明了该结论。例例6.设二元关系R AA,这里A=a,b,c,R=(a,b),(c,b)。从而有 I=(a,a),(b,b),(c,c)，=(b,a

39、),(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 =，这说明空集是合成运算的零元。一般地 a Rnb(c1)(c2)(cn-1)(aRc1 c1Rc2 cn-1Rb)；特别地a Rb(c)(aRc cR b)。53离散数学定义定义4.闭包运算(closure operation)设二元关系R AA。这里A 是一个非空的集合。我们定义：(1)传递闭包(transitive closure)：R=Rk=R R R3 R

40、k ；(2)自反传递闭包(reflexive and transitive closure)：R=Rk=IR R R3 Rk 。ac1c2bcn-1cn-2RnRRRRRabcRRR54离散数学注：传递闭包有时也记为t(R)；自反传递闭包有时也记为rt(R)；其实还有别的闭包；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

41、)R是包含R的最小传递关系：即，对任何二元关系SAA，若RS且S也是传递关系，那么 RS；(4)若|A|=n，则 R=Rk；这时55离散数学 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 xk-1Rb (y1)(y2)(yl-1)(bRy1 y1R

42、y2 yl-1Rc)(量词前移：xA(x)px(A(x)p)(x1)(x2)(xk-1)(y1)(y2)(yl-1)(aRx1 x1Rx2 xk-1Rb bRy1 y1Ry2 yl-1Rc)56离散数学 (量词前移：pxA(x)x(pA(x)(x1)(x2)(xk-1)(xk)(xk+1)(xk+2)(xk+l-1)(aRx1 x1Rx2 xk-1RxkxkRxk+1xk+1Rxk+2 xk+l-1Rc)(这里，我们令：xk=b,xk+1=y1,xk+2=y2,xk+l-1=yl-1)(n)(aRnc)(这里，我们令：n=k+l 1+1 1)aRc 所以，R是传递的。定理定理5.自反传递闭包基

43、本定理 设二元关系R AA，R。则 (1)若 mN，则 Rm R*；特别地 I R*，R R*；(2)R*是自反传递关系：即，对任何元素 aA，aR*a；57离散数学 对任何元素 a，b，c A，aR*bbR*caR*c；(3)R*是包含R的最小自反传递关系：即，对任何二元关系SAA，若RS且S也是自反传递关系，那么 R*S；(4)若|A|=n，则 R*=Rk；这时a R*b (kN)(0kn)(aRkb)(a=b)(kN)(1kn)(aRkb)；(5)若R是自反传递关系,则 R*=R。证.只证(3)（采用逻辑法）(3)对任何元素a，b A，有 aR*b (a=b)(k)(aRkb)(这里k

44、1)58离散数学 (a=b)(x1)(x2)(xk-1)(aRx1 x1Rx2 xk-1Rb)aSb(x1)(x2)(xk-1)(aSx1 x1Sx2 xk-1Sb)(S是自反的且RS)aSbaSb (S是传递的 且 xpp)aSb (幂等性：ppp )所以 R*S 。59离散数学 5.等价关系等价关系 1等价关系和等价类等价关系和等价类定义定义1.等价关系(equivalence relation)设二元关系R AA。这里A是非空的集合。R是A上的等价关系R是自反的、对称的、传递的。显然(R)=(R)=A(因为等价关系是自反的)；例例1.同乡关系是等价关系。例例2.平面几何中的三角形间的相似

45、关系是等价关系。例例3.平面几何中的三角形间的全等关系是等价关系。60离散数学例例4.平面几何中的直线间的平行关系是等价关系。例例5.设N是自然数集，m是一正整数，R=(a,b):aN bN a b(mod m)由等价关系的定义知R是N上等价关系；我们称R是N上的模m同余关系。例例6.6.非空集合A上的幺关系、全关系都是等价关系。例例7.7.非空集合A上的空关系不是等价关系(因为空关系不自反)。例例8.8.设二元关系R AA,这里 A=a,b,c,R=(a,a),(b,b),(c,c),(b,c),(c,b)则R是A上的等价关系。其关系图如下 61离散数学 等价关系的实质是将集合A中的元素进行

46、分类。定义定义2.2.等价类(块)(equivalence classes(block)设R是非空集合A上的等价关系。对任何元素aA，由a生成的(或者说是由a诱导出的)关于R的等价类定义为b:bAbRa记为aR.(显然有aR A)。同时称a为等价类aR的代表元。bca62离散数学定义定义3.3.设R是非空集合A上的等价关系。我们定义集合 R=aR:aA (注意：应去掉重复的类！)为集合A关于等价关系R的商集。记为A/R。称A/R中元素的个数为R的秩。例例9 9.设N是自然数集，m是一个正整数。R是N上的模m同余关系，即 R=(a,b):a N b N a b(mod m)。对于任何自然数a，b

47、 N，aRb a b(mod m)(kI)(a-b=km)；由等价关系的定义知R是N上的等价关系；对于任何自然数a N，以a为代表元的等价类 aR=am=b:bNb a(mod m)；自然数集N关于等价关系R的商集63离散数学N/R=R=0R,1R,2R,3R,m-1R ；或者记作 Nm=N/=0m,1m,2m,3m,m-1m；商集N/R共有m个等价类，故R的秩为m；特别地，取m=5，则有 N=0,1,2,3,45；又如3=3,8,13,5k+3,(这里：kN)。例例1010.例8中等价关系R的等价类为aR=a,bR=cR=b,c；其商集为 A/R=R=aR,bR=a,b,c；故其秩为2。64

48、离散数学定理定理1.设R是非空集合A上的等价关系。对任意的a,bA，有 (1)aaR (故aR)；(2)aRb(即(a,b)R)aR=bR；(3)(3.1)aR bR aR=bR (aRb，即(a,b)R)；(3.2)(a,b)R aR bR=；(4)两个等价类aR和bR，要么完全重合(即aR=bR)，要么不交(即aR bR=)；二者必居其一，也只居其一。证.（采用逻辑法）(1)对任何元素a，有 aA aRa (R是等价关系，故R自反)65离散数学 aaR aR ；(2)先证：aRbaR=bR 为证aR=bR，须证(a)aR bR 对任何元素x A，有 xaR xRa xRaaRb (已知条件

49、：aRb)xRb (R是等价关系，故R传递)xbR所以aR bR 66离散数学(b)bR aR 对任何元素x A，有 xbR xRb xRbaRb (已知条件：aRb)xRbbRa (R是等价关系，故R对称)xRa (R是等价关系，故R传递)xaR 所以bR aR综合(a)和(b)，即得 bR=aR；次证：aR=bR aRb aR (本定理的(1)(x0A)(x0aR)67离散数学 (x0A)(x0aR x0bR)(已知条件：aR=bR)(x0A)(x0Rax0Rb)(x0A)(aRx0 x0Rb)(R是等价关系，故R对称)aRb (R是等价关系，故R传递 且 xpp)(3)(3.1)aRbR

50、 (x0A)(x0aR bR)(x0A)(x0aR x0bR)(x0A)(x0Rax0Rb)(x0A)(aRx0 x0Rb)(R是等价关系，故R对称)aRb (即(a,b)R)(R是等价关系，故R传递 且 xpp)68离散数学 aR=bR (本定理的(2)；(3.2)(整体采用反证法)若(a,b)R，则 aR bR=。否则若 aRbR aR=bR (本定理的(3.1)aRb (本定理的(2)(a,b)R 这就与已知条件：(a,b)R 矛盾；(4)对任何序偶(a,b)(a,b)AA (a,b)R(a,b)R (二分法，互斥)(aR=bR)(aR bR=)(本定理的(3.1)和(3.2)，互斥)。