西安交大离散课件第2章.ppt

《西安交大离散课件第2章.ppt》由会员分享，可在线阅读，更多相关《西安交大离散课件第2章.ppt（82页珍藏版）》请在金锄头文库上搜索。

1、 第二章第二章 关系关系 (relation) 1 . 集合的叉积集合的叉积n元组元组 2 .关系关系 3 .关系的关系的表示表示关系的性质关系的性质 4 .关系的运算关系的运算 5. 等价关系等价关系 6. 半序关系半序关系1 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-t

2、uple）；即，叉积是元组的集合； 每个n元组(a1, a2, , an)的第i个位置上的元素ai称为该n元组的第i个分量（坐标或投影）；元组各分量的顺序不能改变；2 n 称为该叉积及其元组的维数；两个元组相等它们的维数相同且对应的分量相等。即(a1, a2, , an)= (b1, b2, , bm) n=m(iN)(1i n)(ai = bi)；注：笛卡尔(1596-1650 )，法国数学家， 1637年发表方法论之一几何学，首次提出坐标及变量概念。这里是其概念的推广。3 定义定义2. 二个集合A，B的(二维或二重)叉积定义为 AB =(a, b): a A bB ；其元素二元组(a, b

3、)通常称为序偶或偶对(ordered pair) ；二元组(a, b)的第一分量上的元素a称为前者；第二分量上的元素b称为后者； 二重叉积的A B第一集合A称为前集；第二集合B称为后集。一般地说，关于叉积和元组 有： (1) (a, b) (b, a)； (2) AB B A ； (3)二元组不是集合，因为二元组中的分量计较顺4 序,而集合中的元素是不讲顺序的。但是 为了将所有的概念都统一于集合概念， 可采用克亚托斯基(Kazimierz Kurafowski)在1921年给出的定义(a, b)=a,a, b将二元组定义为比其元素高二层的集合； (4) 也可用二元组来递归的定义n元组如下：(a

4、,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)An5 (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 。6 证. )：（采用逻辑法）对任何的元素a,b aAbB (a,b)AB (

5、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) ； (叉积对并) (4)(AB)C = (AC)(BC) 。 (叉积对交)7 证.只证(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)

6、= (AB)(AC) 。8 2 .关系关系一一.关系的基本概念关系的基本概念定义定义1 . 设A,B是两个非空的集合，二重叉集AB 的任何一个子集R都称为是从集合A到集合B的一种二元关系(binary relation) 。即 RAB ；当 (a,b)R 时，称a与b有关系R ，记为 aRb ； 当 (a,b)R 时，称a与b没有关系R ，记为 或 ； 当A=B时，即RAA，则称R是A上的一个二元关系。例例1 . 设A是西安交通大学全体同学组成的集合。9 例例2 . 设A是某一大家庭。 例例3 . 设N是自然数集合。 例例4 . 设是整数集合。 例例5 . 设A是某一大型FORTRAN程序中诸

7、程序块的集合。例例6 . 设A = 风，马，牛，10 1全关系(full relation)： R=AB称为全关系； 2空关系(empty relation)： R= 称为空关系；空关系和全关系都是平凡关系； 3幺关系或单位关系(identical relation)： R= (a, a): aA AA称为A上的幺关系； 4关系的交，并，余运算：叉积是一种（新型的）集合，关系是叉积的子集，因此，关系也是一种集合，有关集合论的一切概念、论述、运算也都适合于关系； 5关系的扩充(expansion)：若R1 R2 ，则称关系R2 是关系R1的一个扩充； 6 n元关系： n元关系R是n 维叉积的一个

8、子集；即 R A1A2 An 11定义定义3.前域(domain) 后域(codomain) 设A,B是两个非空集合，R AB是一个从A到B的关系。则关系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)。 A (R)B (R)abR12 定理定理1. 设R1,R2 AB是两个关系。若 R1 R2 ，则 (1)保序性： (R1) (R2) ； (2)保序性： (R1) (R2) ；证.只证(1) （采用逻辑法）对任何元

9、素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) 。二二.关系的一些关联性质关系的一些关联性质13定理定理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

10、 R1 R2， R2 R1 R2 ，依定理1，有 (R1) (R1R2)， (R2) (R1R2)故根据第一章2定理2的(3 ) ，就可得 (R1) (R2) (R1 R2) 。 14 次证： (R1 R2) (R1) (R2) (采用元素法)对任何元素a A ， 若a (R1 R2)， 则存在 bB ，使得a R1 R2 b因此(a,b)R1 R2 ，从而有(a,b)R1或者(a,b)R2于是 a (R)或者a (R2 )故此 a (R1) (R2) 所以 (R1 R2) (R1) (R2) 。15 (3) 先证： (R1 R2) (R1) (R2) (采用包含法)由于 R1R2 R1 ，

11、R1R2 R2 ，依定理1，有 (R1 R2) (R1) ， (R1 R2) (R2) 根据第一章2定理2的(3) ，就可得 (R1 R2) (R1) (R2) 。例例9 .设 A=1,2,3 R1 =(1,1),(2,2) ， R2 =(1,2),(2,1) 。 16 w元素元素a A和集合和集合A1 A在关系在关系R AB下的关联集下的关联集 (1)a的的R-关联集关联集(R-relative set of a)： R(a)=b : b B aRb B ； (2) A1的的R-关联集关联集(R-relative set of A1)： R(A1)=b : b B ( a A1)(aRb)

12、B 。定理定理.设设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) 。 例例.设设A=a,b,c,d， A1 = c,d ， R=(a,a),(a,b),(b,c),(c,a),(d,c),(c,b)。17 3 .关系的关系的表示表示关系的性质关系的性质 一一.关系表示法关系表示法 1关系的矩阵表示法 设关系RAB ， 这里A,B是两个非空的有限集合， A= a1,a2,a3,am ， B= b1,b2,b3,bn 。

13、 则 用一个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时18 例例1 .设A= a1,a2,a3,a4 ，B=b1,b2,b3,RAB ， R = (a1, b2),(a1, b3),(a2, b3),(a3, b1),(a4, b2)。 例例2 .设A= a1,a2,a3 ，SAA ， S= (a1, a1),(a2, a2),(a3, a3),(a1, a3),(a3, a1) ,(a2, a3),(a3

14、, a2) 19 2关系的图形表示法 设关系RAB ， 这里A,B是两个非空的有限集合， A= a1,a2,a3,am ， B= b1,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相连；20 用两个圆圈分别将表示两

15、个集合A和B中元素的结点圈起来。 所有有向弧的始端结点构成 (R)；所有有向弧的终端结点构成 (R)。 若A=B，这时令VR =A，规定只画表示一个集合元素的结点；表示元素间关系的有向弧也只在此一个集合的结点间画出 。例例3 .设关系 RAB，A= a1,a2,a3,a4 ，B=b1,b2,b3 R = (a1, b2),(a1, b3),(a2, b3),(a3, b1),(a4, b2)例例4 .设关系SAA ，A= a1,a2,a3 ， S= (a1, a1),(a2, a2),(a3, a3),(a1, a3),(a3, a1) ,(a2, a3),(a3, a2)注： 图中各结点所带

16、的小圆圈称为自反圈；一对结点间的来回边称为双向弧；否则，一对结点间只有一条边，则此边称为单向弧。 21 二二 .关系的性质关系的性质 设二元关系RXX(或者说RX2)，这里X是一集合。则R称为是X上的1自反关系(reflexive relation)：当且仅当R满足 自反性：(xX)(xRx) ； 反自反关系(irreflexive relation)：当且仅当R满足反自反性：(xX)( )或(xX)(xRx)；注： 自反性和反自反性是关系的两个极端性质；因此，自反关系和反自反关系是两种极端关系；从关系矩阵来看：自反关系关系矩阵的对角线上元素全是1；反自反关系关系矩阵的对角线上元素全是0； 从

17、关系图来看：自反关系关系图的各结点上全都有自反圈；反自反关系关系图的各结点上全都没有自反圈。 22 2对称关系(symmetric relation)：当且仅当R满足 对称性：(xX)(yX)(xRy yRx) ；3反对称关系(antisymmetric relation)：当且仅当R满足反对称性：(xX)(yX)(xRyyRxx = y) ；注：对称性和反对称性是关系的两个极端性质；因此，对称关系和反对称关系是两种极端关系；从关系矩阵来看：对称关系的关系矩阵是对称矩阵。即xij = xji(1i,j n)； 反对称关系的关系矩阵满足如下性质 xij = 1 xji = 0 (1i,j n)

18、； 从关系图来看：对称关系关系图的结点间若有弧则都是双向弧；反对称关系关系图的结点间若有弧则都是单向弧； 23 4传递关系(transitive relation)：当且仅当R满足 传递性：(xX)(yX)(zX)(xRy yRzxRz) ； 反传递关系(antisymmetric relation)：当且仅当R满足反传递性：(xX)(yX)(zX)(xRy yRz ) ；注：传递性和反传递性是关系的两个极端性质；因此，传递关系和反传递关系是两种极端关系； 概念反传递性和反传递关系一般不甚用，所以不加讨论；24 例例5. .设设 X=a,b,c,d。 R1=(a,b),(a,a),(b,b),

19、(c,d),(c,c),(d,d) R2 =(a,a),(b,b),(c,c),(d,d) R3=(a,b),(a,c),(a,d),(c,d)例例6. .设设X=a,b,c， R1=(a,b),(b,a) ， R2=(a,a),(b,b) R3=(a,b),(b,a),(b,c)例例7. .设设X=a,b,c, , R1=(a,a),(a,b) ,(a,c) ,(c,b) ,(c,c) R2=(a,a),(a,b) ,(a,c) ,(b,a) ,(c,b)例例8. 设设X=a,b,c,d 。 R1=(a,b),(b,c),(a,c),(c,d),(a,d),(b,d) R2=(a,b),(b

20、,c),(a,c),(c,d),(a,d) 25 例例9. 设X是平面上直线的集合。平行关系 R=(x,y) : xX yX xy 例例10. 设X是平面上三角形的集合。相似关系 R=(x, y) : xX yX xy 例例11. 相等关系是自反的、对称的、反对称的、传递的。 全关系X2是自反的、对称的、传递的。 幺关系I 是自反的、对称的、反对称的、传递的。 空关系是反自反的、对称的、反对称的、传递的。 26 4 .关系的运算关系的运算1关系的逆运算关系的逆运算定义定义1.逆运算(converse operation)设A，B是两个非空的集合。 称一元运算 : 2A B 2 B A 对任何二

21、元关系RAB，使得 = (b,a) : bBaAaRbBA为关系的逆运算；称 是R的逆关系(converse of relation)。w显然，对任何(b,a) BA，b a aRb 。 例例1.设A=a,b,c ，B=1,2。 R=(a,1),(a,2),(b,2),(c,1)27 定理定理1.逆运算基本定理设两个关系R AB，S AB，这里 A,B是两个非空的集合。则有 (1) =R ； 反身律 (2) RS ； 保序性 R=S = ； (3) RS= ； 逆对并的分配律 (4) RS= ； 逆对交的分配律 (5) XY=YX ； (6) = ； (7) (R)=( ) ； (8) RS=

22、 。 逆对差的分配律28 证.只证(1)，(4)，(7) （采用逻辑法） (1)对任何(x,y)AB ，有 (x,y) (y,x) (x,y)R 所以 =R 。 (4)对任何(x,y)BA ，有 (x,y)RS (y,x)RS (y,x)R(y,x) S (x,y) (x,y) (x,y) 所以 RS = 。29 (7)对任何(x,y)BA ，有 (x,y)(R) (y,x)R (y,x)R (x,y) (x,y)( ) 所以 (R)= ( ) 。30 2关系的合成运算关系的合成运算定义定义2.合成运算(composition operation)设A，B是两个非空的集合。 称二元运算 o :

23、 2A B 2B C 2 AC对任何两个二元关系R AB , S BC ，使得 RoS =(a,c) : aAcC(bB)(aRbbSc)AC为关系的合成运算；称RoS是R与S的合成关系。w显然，对任何(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)。31 例例3.3.设A是老年男子的集合，B是中年男子的集合，C是青少年男子的集合。 R是由A到B的父子关系， R

24、AB S 是由B到C的父子关系， SBC 。b1b2Ba1a2a3Ac1c2c3c4CRSRoS32 定理定理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 o (S1S2) = (R o S1) (R o S2) ； 合成运算对并的左分配律 (S1S

25、2) o T = (S1 o T) (S2 o T)； 合成运算对并的右分配律 (6) R o (S1S2) (R o S1)(R o S2)； 合成运算对交的左分配不等式 (S1 S2) o T (S1 o T)(S2 o T)； 合成运算对交的右分配不等式(7) (R o S) = S o R 。 鞋袜律33 证.只证(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

26、)(bB)(aRb (bSccTd) (量词交换：xyA(x,y)yxA(x,y) ) (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；34 (5)对任何元素aA,cC ，有 a R o (S1S2)c (bB)(aRb b(S1S2)c) (bB)(aRb (bS1cbS2c) (bB)(aRbbS1c)(aRbbS2c) (对的分配律：p(q

27、r)(p q ) (p r ) ) (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) 。 w 但是合成运算不满足交换律。即，一般 R o SS o R35 例例4.设A=a,b,c,d,e 。 R=(a,b),(c,d),(b,b)，S=(b,e),(c,a),(a,c),(d,b) 3关系矩阵的合成运算关系矩阵的合成运算 设R AB ， SBC 是两个二元关系，其合成关系为R

28、 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)注：这里关系矩阵的合成运算与线性代数中的一般矩阵的乘法运算颇为相似。所不同的是：乘法现在换成布尔乘()；加法现在换成布尔加()。值得注意的是：这里的布尔加1 1=1（不进位），而非1 1=0（进位）。36 对任何的对任何的i ，j (1 i m,

29、1 j n) ，有有 uij =1 aiR o Scj ( b B)(aiRb bScj ) (aiRb1 b1Scj ) (aiRb2 b2Scj ) (aiRbl blScj ) (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 = (t

30、ij)mn 所以所以MR o S = MR o MS。证.（采用逻辑法）37 例例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 MS。38 4关系的闭包运算（宏运算）关系的闭包运算（宏运算）定义定义3.关系的合成幂(nth power) 设二元关系R AA，nN 。这里A 是一个非空的集合， N 是自然数集。 规定： (1) R0 =I（这里I=IA=(a,a) : aA是A上的幺关系）； (2) R

31、1 =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 。 39 证. （采用数学归纳法） 只证(1)的一个等式： RmoRn = Rm+n ； 归纳变量选取n（让m固定） n=0时， RmoR0 = RmoI (定义3的(1)：R0 =I) = Rm n=1时， RmoR1 = RmoR (定义3的(

32、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) 结论成立； 根据数学归纳法，即证明了该结论。40 例例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，R o 。 注： 由定理2的(1)有： o R = R o = ，这说明空集是合成

33、运算的零元。 一般地 a Rnb (c1)(c2) (cn-1)(aRc1 c1Rc2 cn-1Rb) ； 特别地a Rb (c) (aRc cR b) 。ac1c2bcn-1cn-2RnRRRRRabcRRR41 定义定义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 。注：传递闭包有时也记为t( R)；自反传

34、递闭包有时也记为rt( R)； a Rb (kN)(k 1)(aRkb) ； a R b (kN)(aRkb) (a=b)(kN)(k 1)(aRkb)(a=b)(aRb) 。42 定理定理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 ；这时 a Rb (kN)(1k n)(aRkb) ； (5)若R是传递关系

35、,则 R = R 。证.只证(2)(采用逻辑法) (2)对任何元素a，b，c A ，有 aRbbRc (k)(aRkb)(l)(aRlb) (这里k 1, l 1) 43 (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 y1Ry2 yl-1Rc) (量词前移：xA(x)px(A(x)p) )(x1)(x2) (xk-1)( y1)( y2) ( yl-1)(aRx1 x1Rx2 xk-1R

36、b bRy1 y1Ry2 yl-1Rc) (量词前移：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)(aRnb) (这里， 令：n=k+l 1+1 1 ) aRb 所以，R是传递的。 44 定理定理5.自反传递闭包基本定理 设二元关系R AA，R 。则 (1)若 mN，则 Rm R* ；特别地 I R* ， R R* ；(2) R*是

37、自反传递关系：即，对任何元素 aA ， aR*a ； 对任何元素 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 。45 证.只证(3)（采用逻辑法） (3)对任何元素a，b A ，有 aR*b (a=b)(k)(aRkb) (这里k 1) (a=b)(x1)(x2) (xk-1)(aRx1 x1Rx

38、2 xk-1Rb) aSb(x1)(x2) (xk-1)(aSx1 x1Sx2 xk-1Sb) (S是自反的且RS) aSbaSb (S是传递的 且 xpp ) aSb (幂等性：ppp ) 所以 R*S 。46 5. 等价关系等价关系1等价关系和等价类等价关系和等价类定义定义1.等价关系(equivalence relation) 设二元关系R AA。这里A是非空的集合。R是A上的等价关系R是自反的、对称的、传递的。例例1.同乡关系。例例2 .平面几何中的三角形间的相似关系。例例3 .平面几何中的三角形间的全等关系。例例4 .平面几何中的直线间的平行关系。例例5 .设N是自然数集，m是一正整

39、数， R是N上的模m同余关系R=(a,b) :aN bN a b (mod m) 。例例6.6.非空集合A上的幺关系、全关系。例例7.7.非空集合A上的空关系。47 例例8.8.设二元关系R AA,这里 A=a,b,c , R=(a,a), (b,b), (c,c), (b,c),(c,b)。其关系图如下等价关系的实质是将集合A中的元素进行分类。 bca48 定义定义2.2.等价类(块)(equivalence classes(block) 设R是非空集合A上的等价关系。对任何元素aA，由a生成的(或者说是由a诱导出的)关于R的等价类定义为b :bAbRa记为aR. (显然有aR A) 。同时

40、称a为等价类aR的代表元。定义定义3.3. 设R是非空集合A上的等价关系。 定义集合 R = aR : aA (注意：应去掉重复的类！) 为集合A关于等价关系R的商集。记为A/R。称A/R中元素的个数为R的秩。例例9.设N是自然数集，m是一个正整数。R是N上的模m同余关系，即 R=(a,b) : a N b N a b (mod m)。 49 定理定理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

41、)R aR bR = ； (4)两个等价类aR和bR ，要么完全重合(即aR = bR )，要么不交(即aR bR = )；二者必居其一，也只居其一。证.（采用逻辑法） (1)对任何元素a，有 aA aRa (R是等价关系，故R自反) aaR aR ；50 (2) 先证：aRbaR = bR 为证aR = bR ，须证(a) aR bR 对任何元素x A ，有 xaR xRa xRaaRb (已知条件： aRb) xRb (R传递) xbR 所以aR bR (b)证bR aR 任何元素x A ，有 xbR xRb xRbaRb (已知条件： aRb) xRbbRa (R对称 ) xRa (R传

42、递) xaR 所以bR aR 综合(a)和 (b)，即得 bR = aR ；51 次证： aR = bR aRb aR (本定理的(1) (x0A)(x0aR ) (x0A)(x0aR x0bR ) (已知条件：aR = bR ) (x0A)(x0Rax0Rb ) (x0A)(aRx0x0Rb ) (R是等价关系，故R对称) aRb (R是等价关系，故R传递 且 xpp )52 (3)(3.1) aRbR (x0A)(x0aR bR) (x0A)(x0aR x0bR ) (x0A)(x0Rax0Rb ) (x0A)(aRx0x0Rb ) (R是等价关系，故R对称) aRb (即 (a,b)R)

43、 (R是等价关系，故R传递 且 xpp ) aR = bR (本定理的(2) (3.2) (整体采用反证法) 若(a,b)R ，则 aR bR = 。否则若 aRbR aR = bR (本定理的(3.1) aRb (本定理的(2) (a,b)R 这就与已知条件：(a,b)R 矛盾；53 (4)对任何序偶(a,b) (a,b)AA (a,b)R(a,b)R (二分法，互斥) (aR = bR)(aR bR = ) (本定理的(2)和(3.2)，互斥) 。54 定义定义4.4. 设R和S是非空集合A上的两个等价关系。若RS ，则 称R细于S ，或S粗于R 。定理定理2.2.设R和S是非空集合A上的

44、两个等价关系。则 RS(aA)(aR aS) 。证.（采用逻辑法） 先证：RS (aA)(aR aS) 对任何元素对任何元素a A ，有，有 对任何元素xA，有 x aR xRa xSa (已知条件：RS) xaS 所以aR aS 所以(aA)(aR aS) ； 55 次证：(aA)(aR aS)RS 对任何序偶(a,b)AA (a,b)R aRb bRa (R是等价关系，故R对称) baR baS (已知：(aA)(aR aS) ) bSa aSb (S是等价关系，故S对称) (a,b)S 所以R S 。 56 定理定理3.3.设R和S是非空集合A上的两个等价关系。则 R=S(aA)(aR

45、= aS) 。证.(采用逻辑法) R=S RSSR (aA)(aR aS)(aA)(aS aR) (定理2) (aA)(aR aSaS aR) (量词对的分配律：x(A(x)xB(x) x(A(x)B(x) ) (aA)(aR = aS) 。注：由定理2知，若两个等价关系相等，则每个元素所对应的等价类也相同；若两个等价关系的等价类集合相等，则两个等价关系相同。 由定理3知，等价关系与等价类集合一一对应。即相同的等价关系对应着相同的等价类集合，不同的等价关系对应着不同的等价类集合。57 2划分与等价关系划分与等价关系定义定义5.5.覆盖、划分(covering partition) 设A是一非空

46、集合。则A的 (1)覆盖是一集合之集 =A : A，满足条件： A ； (2)划分是一集合之集 =A : A，满足条件：(a) A = ； (b)12A1A2 = ； 其中A称为划分的划分块(block of partition)。注：由划分和覆盖的定义可知，A上的划分一定是A上的覆盖；反之则未必。58 定理定理4 。设R是非空集合A上的等价关系。则R的等价类之集R = aR : aA 是A上的一个划分；等价类就是划分块。定理定理5. 设 =A : A 是非空集合A上的一个划分。 借助来定义A上的二元关系 R AA ，使得 R =(a,b) : ( )(aA bA )则R是A上的等价关系。 称

47、为是由划分产生的(或者说是诱导出的)A上的等价关系。证. (1)自反性： 对任何元素a，有 a A a (划分的条件(a)；A=) ()(aA ) ()(aA a A ) (幂等律：p pp ) (a,a)R aR a 所以R是自反的；59 (2)对称性： 对任何元素a,bA ，有 aR b (a,b)R ()(aA bA ) ()(bA aA ) (交换律：pqqp ) (b,a)R bR a 所以R是对称的；60 (3)传递性：对任何元素a,b,cA ，有 aR bbR c (a,b)R (b,c)R (1)(aA1bA 1)(2)(bA2cA2) ()(aA bA bA cA ) (由划

48、分的条件(b)的逆否，有 A1A2b 1=2= ) ()(aA bA cA ) (幂等律：pp p ) ()(aA cA ) (合取分析式：pqp ) (a,c)R aR c 所以R是传递的； 所以R是等价的。注：定理5表明:由集合A上的划分可产生A上的一个等价关系；划分块就是等价类。61 w问题：1.由A上的一个等价关系R出发，由等价类可以得到一个划分R= X/R，由该划分出发，又可产生一个新的等价关系R1，这个过程是否要进行下去？R与R1有什么关系？2.由A上的一个划分出发可产生一个等价关系R ，由该关系又可产生新的划分1，与1有什么关系？62 定理定理6。设R是非空集合上的等价关系， 是

49、A上的一个划分。那么 R= R R = 。证. (采用逻辑法) 先证： R= R R = 对任何元素aA ，有 对任何元素xA ，有 xaR xRa xRa (已知条件： R= R ) xaR 所以aR=aR 所以 (aA)(aR=aR ) 所以 R =aR : aA =aR : aA = ； 63 次证： R = R= R 对任何序偶(a,b)AA (a,b)R aRb bRa (R是等价关系，故R对称) baR baR (已知条件：R = (aA)(aR=aR ) ) bR a aR b (R是等价关系，故R对称) (a,b)R 所以 R= R 。 注：由定理4,5,6可知：由等价关系可以

50、产生一个划分，由划分 可以产生一个等价关系； 划分与等价关系是一一对应的。即每个划分对应一个等价关 系，且每个等价关系对应一个划分。64 6. 半序关系半序关系定义定义1.1.半序关系(partial order relation) 设二元关系R AA。这里A是非空的集合。R是A上的半序关系R是自反的、反对称的、传递的。w通常，半序关系R记为 ，称系统(A,)为半序集(poset)。例例1.1.自然数集N、整数集I、有理数集Q 、实数集R上的小于等于关系 。例例2.集合X的幂集2x上的包含关系。例例3.3. N、整数集I、有理数集Q 、实数集R上的小于关系 。注：二元关系R AA(A) 是A上

51、的拟序关系(quasi order) R是反自反的、传递的。拟序一般记作，称系统(A,)为拟序集； 拟序与半序的关系是：对任何元素a,bA ab ab ab ；65 例例4.集合X的幂集2x上的真包含关系。定义定义2.可比较性(comparability) 设(A, )是一半序集，a与b是A中的一对元素。 称a与b是可比较的 abba 。注： 否则，若abba ，则称a与b是不可比较的； 半序关系实际上是在集合A上建立了一种比较关系；例例5. .对小于等于关系 ，任何二数a,b是可比较的吗？例例6. .对于 ，任何二集合A,B都是可比较的吗？定义定义3.全序关系 线性序 链(total ord

52、er, linear order , chain) 设(A, )是一半序集。 是A上的全序关系 满足全可比较性： (aA)(bA)(abba) 。这时， 简称是全序或线性序；称(A, )是一全序集。66 注：注： 否则，若否则，若( a A)( b A)(a b b a)，一般一般 则则称称 是非是非线性序线性序(nonlinear order)(nonlinear order)； 非线性序在实际中有很重要的作用非线性序在实际中有很重要的作用；也是本课程的一个重要；也是本课程的一个重要研究对象。研究对象。 字典序字典序(lexicographic) 设设( , )是一全序集。其中：是一全序集。

53、其中： 是一有限集，称为字是一有限集，称为字母表母表(alphabet)，任一元素任一元素a称为字母称为字母(alpha)， 是是字母表中字母的自然顺序，显然字母表中字母的自然顺序，显然 是是一个一个全序。故此全序。故此, ,则则( *, * *)是一全序集是一全序集, , 称其为称其为字典序字典序。其中：其中： * = 2 3 n ( 称为空字称为空字)其任何元素其任何元素 w*称为一个字称为一个字(word)；必有必有k N,使得使得w k ，从而从而 w=(a(ai1i1,a,ai2i2,a,ai3i3, , , ,a aikik) )=a ai1i1a ai2 i2 a ai3 i3

54、a aikik这里这里a aijij (1 j k) 。 67 定义二元关系定义二元关系 * * * * ，使得；使得； 对于任何二字对于任何二字w1=a ai1i1a ai2i2a ai3i3a aimim和和w2=b bi1i1b bi2i2b bi3i3b bininw1 * * w2当且仅当当且仅当 下列三条之一成立：下列三条之一成立：(1)a ai1i1a ai2i2a ai3i3a aimim=b bi1i1b bi2i2b bi3i3b bin in ；(这时：这时：m=n, a aijij=b bijij ) (2)a ai1i1 b bi1 i1 且且a ai1i1 b bi

55、1 i1 ； (3)存在着某个存在着某个k N，1 k min(m,n)，使得使得a ai1i1a ai2i2a ai3i3a aik-1ik-1=b bi1i1b bi2i2b bi3i3b bik-1ik-1且且a aikik b bikik且且a aikik b bikik 。例例7.小于等于关系小于等于关系 ，包含关系包含关系 。例例8.(I , ) , (R, ) 都都是全序集。但是在是全序集。但是在(I , ) 中每个中每个整数，下一个比它大的或比它小的（即紧挨着它的）那整数，下一个比它大的或比它小的（即紧挨着它的）那个数都可确定；而在个数都可确定；而在(R, ) 中却不可能。中却

56、不可能。68 定义定义3.直接后继后继(direct successor, successor) 设(A, )是一半序集，a与b是A中的一对元素。 称b是a的直接后继aba b(tA)(a tt bt=at=b)直接后继简称后继； a的后继记作a+，即b= a+ ，这时称a是b的前驱或前趋(predecessor)。例例9. (Nm, ) , (N, ) ,(I , ) , (R, ) 都是全序集。 Nm=0,1,2,m-1。 (Nm, ) 中每个元素都有后继、前驱？ (N, )每个元素都有后继、前驱？ (R, )每个元素都有后继、前驱？69 w半序集的表示法半序集的表示法哈斯图哈斯图(Has

57、se) 半序集(A, )的Hasse图是一个图 G =(V ,E) 其中： V= A 是结点集； E=(a,b) : aAbAa bb= a+是边集。 在画法上, 规定： (1)结点a+必须画在结点a 的紧(斜)上方； (2)不画边的方向。注：与关系图相比， Hasse图 省略了自反性的边(圈)； 省略了(反对称性)方向； 省略了传递性的边；例例10. 设A =a,b,c, 2A上的包含关系 的Hasse图。 acb,ca,b,ca,ba,cb例1070 注；在非线性半序集中，直接后继一般不唯一； 其Hasse图呈现网格状；其实正是这点导致一门现代数学的重要学科格论的出现；而此例正好给人们形象

58、、直观的展现出布尔代数(用其三大特例之一集合代数来表现)的内部数学结构。 例例11. 设A = 2,3,4,6,7,8,12,36,60， R =(a,b):aAbAb |a，R是A上的整除关系。 例例12. 设A =2,3,6,12,24,36,R=(a,b):aAbAa | b R是A上的整除关系。注：虽然同为整除关系，但由于集合不同，其Hasse图就呈现出明显的不同；这说明两例中的半序集是不同的；所以，在论及半序关系时，重要的是一定要指明其是那个集合上的半序关系；半序集是一个整体，不能分而论之。 71 定义定义4.最大元最大元 最小元最小元( (greatest element,leas

59、t element) ) 设设(A, )是半序集，是半序集，B A ，x0 B 。则。则 称称 (1)x0是是B的最大元的最大元( x B)(x x0) ； (2)x0是是B的最小元的最小元( x B)(x0 x) 。 注：注： 最最大大( (小小) )元未必存元未必存在在；即使；即使B(甚或甚或A)是有限集合也是有限集合也未必；未必； B的的最最大大( (小小) )元若存元若存在，则在，则一定在一定在B中中；定义定义5.极极大元大元 极极小元小元( (maximum element,minimal element) )设设(A, )是半序集，是半序集，B A ， x0 B 。则。则 称称 (

60、1)x0是是B的一个极大元的一个极大元 ( x B)(x0 x x x0) ( x B)(x0 x) ； (2)x0是是B的一个极小元的一个极小元 ( x B)(x x0 x x0) ( x B)(x x0) 。 注：注： 极极大大( (小小) )元不一定存元不一定存在在；但在；但在B(或或A)是有限集合时是有限集合时一定存一定存在在； 极极大大( (小小) )元即使存元即使存在，一般也是不唯一的在，一般也是不唯一的； B的极的极大大( (小小) )元若存元若存在，则在，则一定在一定在B中中。 72 定理定理1. 设设(A, )是半序集，是半序集，B A。若。若B有最大有最大(小小)元，元，则

61、必是唯一的。则必是唯一的。证证.（采用逻辑法）只证最大元的唯一性（采用逻辑法）只证最大元的唯一性 x01是是B的最大元的最大元 x02是是B的最大元的最大元 ( x B)(x x01) ( x B)(x x02), x02 x01 x01 x02 (因因x01 , x02 B又都是又都是B的普通一元；根据的普通一元；根据普遍性特殊化：普遍性特殊化： xA(x) A(y)；以及以及合成律：合成律：(p q ) ( rs ) p r q s ) x01=x02 ( 有反对称性有反对称性) 所以，所以， B的最大元是唯一的。的最大元是唯一的。73 定义定义6.上界上界 下界下界( (upper bo

62、und,lower bound) ) 设设(A, )是半序集，是半序集，B A ， z0 A 。则。则 称称 (1)z0是是B的一个的一个上界上界( x B)(x z0) ； (2)z0是是B的一个的一个下界下界( x B)(z0 x) ；(3)若若B有有一个一个上界，则称上界，则称B上方有上方有界；界； 若若B有一个有一个下界，则称下界，则称B下下方有方有界；界； 若若B上、上、下下方都有方都有界，则称界，则称B有有界。界。注：注： 上上界界、下界、界下界、界一般不一定存一般不一定存在在； B(或或A)有限不有限不一定有一定有上上界界、下界、界；有下界、界；有上上界界、下界、界下界、界B(或

63、或A)也不一定有限；也不一定有限； 上上界界、下界、界下界、界即使存即使存在，一般也是不唯一的在，一般也是不唯一的； B的上的上界界、下界、界若下界、界若存存在，在，可以在可以在B中，也可以不在中，也可以不在B中中。例例13. (R, ) 是全序集。是全序集。取取B=(0,1)=x : x R 0 x 1 R，的上下界。，的上下界。 74 定义定义7.上确界、下确界上确界、下确界 ( (least upper bound,greatest lower bound) ) 设设(A, )是半序集，是半序集，B A ， z0 A 。则。则 称称 (1)z0是是B的的上确界上确界 ( x B)(x z

64、0) ( z A)( x B)(x z) z0 z) ； (2)z0是是B的的下确界下确界 ( x B)(z0 x) ( z A)( x B)(z x) z z0) ； (3)上确界即是上确界即是最小上界，记为最小上界，记为LUB(B)； 下确界即是下确界即是最大下界，记为最大下界，记为GLB(B)。注：注： 上上(下下)确界确界一般不一定存一般不一定存在在；即使；即使B(或或A)是有限集合也是有限集合也未必；未必； B的的上上(下下)确界确界若存若存在，在，可以在可以在B中，也可以不在中，也可以不在B中中；例例14.14.令：令：A= ：n N n 1 B= ：n N n 1 X=A B75

65、 定理定理2. 设设(A, )是半序集是半序集,B A。若。若B有有上上( (下下) )确界确界，则，则必是唯一的。必是唯一的。注：注： 最最大大( (小小) )元一定是元一定是极极大大( (小小) )元元； 极极大大( (小小) )元元不一定不一定是是最最大大( (小小) )元；元；极极大大( (小小) )元元存在不一定有存在不一定有最最大大( (小小) )元；元； 最最大大( (小小) )元一定是元一定是上上(下下)确界确界；(下下)确界确界不一定不一定是是最最大大( (小小) )元；元；上上(下下)确界确界存在不一定有存在不一定有最最大大( (小小) )元；元； 上上(下下)确界确界一定

66、是一定是上上(下下)界界； 上上(下下)界界不一定不一定是是上上(下下)确界确界； 上上(下下)界界存在不一定有存在不一定有上上(下下)确界确界； 讨论讨论B的上的上( (下下) )确界的前提是确界的前提是B的上的上( (下下) )界存在；界存在；例例15. 设设A=2,3,4,6,7,8,12,36,60, R=(a,b) : a A b A a | b。 76 半序集的全序化半序集的全序化(非线性序的线性化非线性序的线性化) 设设(A, )是一半序集，其中是一半序集，其中A=a1, a2, a3, , an。下下面的拓扑排序面的拓扑排序(分类分类)(A topological sort)算

67、法是将半序集算法是将半序集(A, )整整对对(或者说转化或者说转化)为一个全序集为一个全序集(A,)，并且满并且满足足 保序性：保序性： ( a A)( b A)(a b ab) (也称为也称为遗传性遗传性)。注：注： 拓扑学主要是研究变化中的不变量；拓扑学主要是研究变化中的不变量； 而这里，而这里，全序化是全序化是变化；变化；遗传性是遗传性是不变量。不变量。拓扑排序拓扑排序(分类分类)算法算法： No.1 k 1； (设置计数器设置计数器) No.2 在在A中任取中任取半序集半序集(A, )的的一个一个极小元极小元 aik ； No.3 若若 k=n ，则则算法停止；欲得之全序为：算法停止；

68、欲得之全序为： ai1 ai2 ai3 aik ain ； No.4 (否则否则k n) k k+1 ,A Aaik ；go to No.2 。77 注：注： 拓扑排序算法所得之全序不是唯一的（因为极小元不唯一）；拓扑排序算法所得之全序不是唯一的（因为极小元不唯一）； 例如，在例例如，在例14中的半序集就可被转化为如下的全序：中的半序集就可被转化为如下的全序： 7，3，2，6，4，12，8，60，36 。问题：问题： 有限有限半序集中一定有极小元吗？定义半序集中一定有极小元吗？定义5下的注已经回答；下的注已经回答； 半序集的子集和原序还构成半序集吗？回答参见习题半序集的子集和原序还构成半序集吗

69、？回答参见习题35。定义定义8.良序集良序集(well ordered set) 设设(A, )是半序集是半序集。则。则 称称 (A, )是良序集是良序集A的每个非空子集都有最小元的每个非空子集都有最小元 ( B A)( x0 B) ( x B)(x0 x)。这时这时 称称半序半序(关系关系) 是良序是良序(关系关系)。例例16. (N, )， (I , ) 。78 定理定理3. 设设(A, )是良序集。那么是良序集。那么(1) (A, )是是全全序集；序集；(即，良序集一定是即，良序集一定是全全序集序集) (2)对于任何元素对于任何元素a A，若，若a不是不是A的的最大元，则最大元，则a的的

70、直直接后继接后继a+一定存在；即一定存在；即( a A)( ( x A)(x a) ( b A)(b= a+ ) ) 。证证. (采用逻辑法采用逻辑法) (1) ( B A)( x0 B) ( x B)(x0 x) (因因 是良是良序序)( a,b A)( x0 a,b)( x a,b)(x0 x) (普遍性特殊化普遍性特殊化) ( a,b A)( x0 a,b)(x0 a x0 b) ( a A)( b A)(a a a b) (b a b b) ( a A)( b A)(a b b a) (合取分析式：合取分析式：p qp ) 所以所以 是全序关系；是全序关系；79 (2) ( B A)(

71、 x0 B) ( x B)(x0 x) (因因 是良是良序序) ( B A)( x0 A)(x0 B ( x A)(x B x0 x) (放大缩小法。注意：放大缩小法。注意： 量词的特征谓词量词的特征谓词x0 B作为合取项；作为合取项； 量词的特征谓词量词的特征谓词x B作为蕴含条件作为蕴含条件) ) ( B A)( b A)(b B ( t A)(t B b t) (约束变项换名：约束变项换名： xA(x) yA(y) (x0换名为换名为b)； xA(x) yA(y) (x换名为换名为t ) ) 80 ( B1=x : x a a x A) ( b A)(b B1 ( t A)(t B1b

72、t) (普遍性特殊化普遍性特殊化) ( a不是最大元不是最大元 (已知已知条件条件) ( x A)(x a) ( x A) (x a) (量词对偶律：量词对偶律：xA(x) x A(x) ) ( x A)(a a x a x) (因因 是全序是全序) ) B1 ) ( a A)( b A)(b a a b ( t A)(t a a t b t) ( b B1b a a b )81 ( a A)( b A)(b a a b ( t A)(t a a t t b b t t b) (附加律：附加律：pq p r q r) ( a A)( b A)(b a a b ( t A)(t a a t t b t= =b) ( 是良序，故是良序，故 是反对称的是反对称的) ( a A)( b A)(b a a b ( t A)(a t t b t =a t= =b) (相容相容(析取析取)排斥法：排斥法： r p q p r q ) ( a A)( b A)(b= a+ ) 82