离散数学第2章关系.ppt

离散数学离散数学西安交通大学西安交通大学电子与信息工程学院电子与信息工程学院计算机系计算机系1离散数学 第二章第二章 关系关系 (relation) §1 . 集合的叉积集合的叉积　　n元组元组 §2 .关系关系 §3 .关系的关系的表示表示　　关系的性质关系的性质 §4 .关系的运算关系的运算 §5. 等价关系等价关系 §6. 半序关系半序关系2离散数学§1 . 集合的叉积集合的叉积　　n元组元组 定义定义1. 叉积，笛卡尔积 (cross product , Cartesian product(1637))　 n个集合A1， A2， ，An的 n 维叉积定义为 =A1 × A2 ×  × An ={(a1, a2, , an): ai Ai(1i  n)} ；　3离散数学u n 维叉积A1 × A2 ×  × An的每个元素(a1, a2, , an)都称为一个n元组（n-tuple）；即，叉积是元组的集合；u 每个n元组(a1, a2, , an)的第i个位置上的元素ai称为该n元组的第i个分量（坐标或投影）；元组各分量的顺序不能改变；un 称为该叉积及其元组的维数；u两个元组相等它们的维数相同且对应的分量相等。

即 (a1, a2, , an)= (b1, b2, , bm)  n=m  (iN)(1i  n)(ai = bi)；注：笛卡尔(1596-1650 )，法国数学家， 1637年发表《方法论》之一《几何学》，首次提出坐标及变量概念这里是其概念的推广4离散数学定义定义2.  二个集合A，B的(二维或二重)叉积定义为 A×B ={(a, b): a A bB} ；w其元素——二元组(a, b)通常称为序偶或偶对(ordered pair) ；w二元组(a, b)的第一分量上的元素a称为前者；第二分量上的元素b称为后者；w二重叉积的A B第一集合A称为前集；第二集合B称为后集5离散数学例例1 . A={ a,b,c }, B={0,1} A×B={(a,0), (a,1), (b,0), (b,1), (c,0), (c,1)} B×A={(0,a), (0,b), (0,c), (1,a), (1,b), (1,c)} 例例2 . A={张三,李四}，B={白狗,黄狗} A×B={(张三,白狗),(张三,黄狗),(李四,白狗),(李四,黄狗)} B×A={(白狗,张三),(白狗,李四),(黄狗,张三),(黄狗,李四)}6离散数学一般地说，关于叉积和元组我们有：(1) (a, b) (b, a)；(2) A×B  B × A ；(3) 二元组不是集合，因为二元组中的分量计较顺序, 而集合中的元素是不讲顺序的。

4) 我们也可用二元组来递归的定义n元组如下：　　　(a,b,c)=((a,b),c)    (a1, a2, , an-1 , an)= ((a1, a2, , an-1) , an)7离散数学(5) 这样，我们也就可用二重叉积来递归的定义n维叉积如下：　　 A×B×C=(A×B)×C　　    A1×A2× ×An-1×An= (A1×A2× ×An-1)×An8离散数学(6) 利用(5)所给的定义，我们可以递归的定义集合的叉积幂如下：　　　　　A2= A×A A3 = A2 ×A  An = An-1 ×A(7)我们规定空集与任何集合A的叉积是空集 即 A× =  = ×A　由于若偶对的第一分量或第二分量不存在就没有偶对存在，故规定它们的叉积集合为空集是合理的9离散数学定理定理1. 设A,B,C,D是四个非空的集合。

那么　　　　A×B = C×D  A = C  B = D 　[证]. 　 )：（采用逻辑法）对任何的元素a,b (a,b)A×B (a,b)C×D (条件： A = C  B = D ）所以　 A×B = C×D 10离散数学　 )：（采用逻辑法）对任何的元素a,b aAbB (a,b)A×B (a,b)C×D (条件：A×B = C×D ）  aCbD 所以　A = C  B = D 11离散数学定理定理2 . 设A,B,C是三个非空集合则 (1)左分配律：A×(B∪C) = (A×B)∪(A×C)　 (2)左分配律：A×(B∩C) = (A×B)∩(A×C) 　 (3)右分配律：(A∪B)×C = (A×C)∪(B×C) (4)右分配律：(A∩B)×C = (A×C)∩(B×C) 　12离散数学[证]. 只证(1)（采用逻辑法）　对任何的元素a,b　　(a,b)A×(B∪C)　aAb B∪C  aA(bBbC)  (aAbB)(aAbC) (分配律：p(qr)(pq)(pr))　 (a,b)A×B(a,b)A×C  (a,b)(A×B)∪(A×C) 所以 A×(B∪C) = (A×B)∪(A×C) 。

13离散数学 §2 .关系关系一一. 关系的基本概念关系的基本概念定义定义1 . 二元关系(binary relation) 设A, B是两个非空的集合w二重叉集A×B 的任何一个子集R都称为是从集合A到集合B的一种二元关系即 RA×B ；w当 (a,b)R 时，称a与b有关系R ，记为 aRb ；w当 (a,b)R 时，称a与b没有关系R ，记为 或　 ； w当A=B时，即RA×A，则称R是A上的一个二元关系14离散数学例例1 . 设A是西安交通大学全体同学组成的集合 R={(a,b) : aAbAa与b是同乡}A×A 于是，R是西安交通大学同学之间的同乡关系例例2 . 设N是自然数集合 R= { (a,b) : aNbNa|b } N×N 则R就是自然数集合上的整除关系15离散数学例例3 . 设A是某一大家庭 R1 = {(a,b) : aAbAa是b的父亲或母亲}A×A R2 = {(a,b) : aAbAa是b的哥哥或姐姐}A×A R3 = {(a,b) : aAbAa是b的丈夫或妻子}A×A 于是， R1是父母与儿女之间的关系，即父母子女关系； R2是兄弟姐妹之间的关系，即兄弟姊妹关系； R3是夫妻之间的关系，即夫妻关系。

16离散数学例例4 . 设Ｉ是整数集合 R= { (a,b) : aIbI(kI)(a-b =km)} II 则R就是整数集合上的(模m)同余关系例例5 . 设A是某一大型FORTRAN程序中诸程序块的集合 R= { (a,b) : aAbAa调用(call)b }AA 则R就是程序块集合上的调用关系例例6 . 设A = {风，马，牛}， R = { (风,马)，(马,牛) }AA 则R是A上的一个二元关系17离散数学 关于关系概念，我们还有如下的几个定义和说明： 1°全关系(full relation)： 关系R=AB称为全关系； 2°空关系(empty relation)： 关系R= 称为空关系；　空关系和全关系都是平凡关系；18离散数学 3°幺关系或单位关系(identical relation)： 关系R= {(a, a): aA} AA称为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) }也不是；19离散数学4°关系的交，并，补运算：w 叉积是一种（新型的）集合；关系是叉积的子集；因此，关系也是一种（新型的）集合；w 从而，有关集合论的一切概念、论述、运算也都适合于关系；w 尤其是集合的交，并，补，差运算也都适合于关系；因此，关系也有交，并，补，差运算；20离散数学例例8 . 设N是自然数集合。

R=小于关系={(m,n) : mNnNmn}NN S=整除关系={(m,n) : mNnNm|n}N N 则 R’ =大于等于关系()； RS=小于等于关系() ； 　 RS=不相等的整除关系()；　　　R\S=小于又不整除关系( ∤)；　　 S\R=相等关系(=) 21离散数学 5°关系的扩充(expansion)：若R1  R2 ，则称关系R2 是关系R1的一个扩充； 6° n元关系：　n元关系R是n 维叉积的一个子集；即　　 R A1A2 AnR1R222定义定义3. 前域(domain) 后域(codomain) 设A, B是两个非空集合，R A×B是一关系则关系R的w 前域：  (R) = { a : a A(bB)(aRb)}A ；w 后域：  (R) = { b : bB(aA)(aRb) }B 离散数学A (R)B (R)abR23例例9 . 设A={1,2,3,4} ，B={2,4,6,8,10} 。

R={(1,2),(2,4),(3,6)} 则　 (R) = {1,2,3}A ，  (R) = {2,4,6}B 离散数学24离散数学 二二. 关系的一些关联性质关系的一些关联性质定理定理1. 设R1,R2  A×B是两个关系若 R1  R2 ，则 (1)保序性： (R1)   (R2) ； (2)保序性：  (R1)   (R2) ；[证]. 只证(1) （采用逻辑法）对任何元素a A，　　　 a   (R1 ) 　 aA(bB)((a,b)R1) (前域的定义)　　 aA(bB)((a,b)R2) (条件：R1  R2 )  aA(bB)(a R2 b)　  a   (R2 ) 所以  (R1)   (R2) 25定理定理2 . 设R1, R2是A×B上的两个二元关系则 (1)  (R1 ∪ R2) =  (R1)∪ (R2) (2)  (R1 ∪ R2) =  (R1)∪ (R2) (3)  (R1 ∩ R2)  (R1)∩ (R2) (4)  (R1 ∩ R2)   (R1)∩ (R2) 离散数学26[证]. 只证(1)， (3) (1) 先证：  (R1)∪ (R2)   (R1 ∪ R2) (采用包含法)　由于　R1  R1 ∪ R2， R2  R1 ∪ R2 ，　依定理1，有  (R1)   (R1∪R2)，  (R2)   (R1∪R2)　故根据第一章§2定理2的(3 ) ，就可得　  (R1)∪ (R2)   (R1 ∪ R2) 。

离散数学27 离散数学 次证：  (R1 ∪ R2)   (R1)∪ (R2) (采用元素法)　 对任何元素a A 　， 若a   (R1∪ R2)，则存在 bB ，使得　 　 (a,b)R1 ∪ R2 ，　从而有　　(a,b)R1　或者　(a,b)R2　于是　 a   (R１)　或者　a   (R2 )　故此 　 a   (R1)∪ (R2) 　 所以　  (R1 ∪ R2)   (R1)∪ (R2) 28离散数学(3) 先证：  (R1 ∩ R2)   (R1)∩ (R2) (采用包含法)　由于　 R1∩R2  R1 ， R1∩R2  R2 ，　依定理1，有  (R1 ∩ R2)  (R1) ， (R1 ∩ R2)   (R2) 　 故 根据第一章§2定理2的(3) ，就可得　　 (R1 ∩ R2)   (R1)∩ (R2) 。

　 其次，反方向的包含不成立且看下面的反例29离散数学例例9 . 设 R1 ={(1,1),(2,2)} ， R2 ={(1,2),(2,1)} 由于　R1 ∩ R2 =  ，故　 (R1 ∩ R2) =  但是，由于 (R2) = {1,2 } ，  (R2) = {1,2}　 故　  (R1)∩ (R2) = {1,2 } 所以  (R1)∩ (R2)  (R1 ∩ R2) 30离散数学 §3 .关系的关系的表示　表示　关系的性质关系的性质一一. 关系表示法关系表示法 1°关系的矩阵表示法 设关系RA×B ， 这里A,B是两个非空的有限集合， A={ a1,a2,a3,…,am } ， B={ b1,b2,b3,…,bn } 则我们可用一个m×n阶0-1矩阵MR来表示关系R，我们称此矩阵MR为关系R的关系矩阵(relation matrix)31离散数学 MR=(xij)m×n ，其中 1 当（ai,bj)  R时 xij = 0 当（ai,bj)  R时 ( i=1,…,m ； j=1,…,n)32离散数学例例1 . 设关系　RA×B ， A={ a1,a2,a3,a4 } ， B={b1,b2,b3} R ={ (a1, b2),(a1, b3),(a2, b3),(a3, b1),(a4, b2)}。

于是，我们得到R的关系矩阵MR为　　 MR= ；b1b2b31a1a2a3a400101101001033离散数学例例2 . 设关系　SA×A ，A={ a1,a2,a3} ， S={ (a1, a1),(a2, a2),(a3, a3),(a1, a3),(a3, a1) , (a2, a3),(a3, a2)} 于是，我们得到S的关系矩阵MS为　　 MS= a1a2a31a1a2a3１１0101１１1１１１１34离散数学 2°关系的图形表示法 设关系RA×B ，这里A, B是两个非空的有限集合，A={ a1,a2,a3,,am }, B={ b1,b2,b3,,bn } 则我们可用一个有向图GR=(VR,ER)来表示关系R，我们称此有向图GR为关系R的关系图 (relation digraph) 35离散数学w VR =AB，ER =R； w　VR中的元素称为结点，用小圆点表示；表示A中元素的结点放在左边一块；表示B中元素的结点放在右边一块；w　ER中的元素称为边，用有向弧表示；若aRb(即(a,b)R)，则在表示a的结点和表示b的结点之间连一条有向弧。

有向弧的始端与结点a相连，有向弧的终端与结点b相连；36离散数学w 有时我们会用两个圆圈分别将表示两个集合A和B中元素的结点圈起来 w 所有有向弧的始端结点构成 (R)；所有有向弧的终端结点构成 (R)w 若A=B，这时令VR =A，并规定只画表示一个集合元素的结点；表示元素间关系的有向弧也只在此一个集合的结点间画出 37离散数学例例3 . 设关系 RA×B， A={ a1,a2,a3,a4 }，B={b1,b2,b3} R ={ (a1, b2),(a1, b3),(a2, b3),(a3, b1),(a4, b2)} 于是，我们得到R的关系图GR为下图a1a2a3a4b1b2b3RABGR38离散数学例例4 . 设关系　SA×A ，A={ a1,a2,a3} ， S = { (a1, a1),(a2, a2),(a3, a3),(a1, a3), (a3, a1) ,(a2, a3),(a3, a2)} 于是，我们得到S的关系图GS为下图注： 图中各结点所带的小圆圈称为自反圈；一对结点间的来回边称为双向弧；否则，一对结点间只有一条边，则此边称为单向弧。

关系的表示法有三种:集合表示法,矩阵表示法,图形表示法a1a2a3GS39离散数学二二 . 关系的性质关系的性质 设二元关系RX×X (或者说RX2)，这里X是一集合则R称为是X上的1°自反关系(reflexive relation)： 当且仅当R满足自反性：(xX)(xRx) ； 显然，对于自反关系R，  (R) =  (R) = X w 反自反关系(irreflexive relation)： 当且仅当R满足反自反性： (x  X)( ) 或(x X)(xRx) ；40离散数学w 常见的自反关系有相等关系(=)，小于等于关系()，包含关系()等； 而不相等关系()，小于关系()，真包含关系()等都不是自反关系，它们都是反自反关系注:自反性和反自反性是关系的两个极端性质；因此，自反关系和反自反关系是两种极端关系；从关系矩阵来看：自反关系关系矩阵的对角线上元素全是1；反自反关系关系矩阵的对角线上元素全是0；从关系图来看：自反关系关系图的各结点上全都有自反圈；反自反关系关系图的各结点上全都没有自反圈。

41离散数学例例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)}　是X上的反自反关系注：由此例可知幺关系一定是自反关系，但自反关系不一定是幺关系42离散数学2°对称关系(symmetric relation)： 当且仅当R满足对称性： (xX)(yX)(xRy  yRx) ；3°反对称关系(antisymmetric relation)： 当且仅当R满足反对称性： (xX)(yX)(xRy  yRx  x = y) ；43离散数学w 常见的对称关系有相等关系(=)，不相等关系()，同余关系，朋友关系，同学关系，同乡关系等； 而小于等于关系()，包含关系()，上下级关系，父子关系等都不是对称关系，它们都是反对称关系。

注: 对称性和反对称性是关系的两个极端性质；因此，对称关系和反对称关系是两种极端关系； 从关系矩阵来看：对称关系的关系矩阵是对称矩阵即xij = xji(1i,j  n)；反对称关系的关系矩阵满足如下性质 xij = 1  xji = 0 (1i,j  n) ；从关系图来看：对称关系关系图的结点间若有弧则都是双向弧；反对称关系关系图的结点间若有弧则都是单向弧.44离散数学例例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 .例例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 ,但ab45离散数学4°传递关系(transitive relation)： 当且仅当R满足传递性： (xX)(yX)(zX)(xRy  yRz  xRz) ；w 反传递关系(antisymmetric relation)： 当且仅当R满足反传递性：(xX)(yX)(zX)(xRy  yRz  ) ；46离散数学w 常见的传递关系有相等关系(=)，小于等于关系()，包含关系()，整除关系，同余关系，上下级关系，同乡关系，后裔关系等； 而不相等关系()，父子关系，朋友关系，同学关系等都不是传递关系。

注： 传递性和反传递性是关系的两个极端性质；因此，传递关系和反传递关系是两种极端关系； 概念反传递性和反传递关系一般不甚用，所以不加讨论47离散数学例例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 48离散数学例例9. 设X是平面上直线的集合平行关系 R={(x,y) : xX  yX  x∥y} 由平面几何的知识知: 若x∥y且y∥z，则 x∥z 由传递关系的定义知R是X上的传递关系例例10. 设X是平面上三角形的集合相似关系 R={(x, y) : xX  yX  x∽y} 由平面几何的知识知: 若x∽y 且y∽z ，则 x∽z 由传递关系的定义知R是X上的传递关系　　　　　　　　 49离散数学w 相等关系是自反的、对称的、反对称的、传递关系。

w 全关系X2是自反的、对称的、传递的w 幺关系I 是自反的、对称的、反对称的、传递的w 空关系是反自反的、对称的、反对称的、传递的50离散数学 §4 .关系的运算关系的运算1°°关系的逆运算关系的逆运算定义定义1. 逆运算(converse operation)　设A，B是两个非空的集合对任何二元关系RA×B，使得 = {(b,a) : bBaAaRb}  B×A为关系的逆运算；称 是R的逆关系(converse of relation) 　显然，对任何(b,a) B×A，b a  aRb ；并且　　　 RRR51离散数学例例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)} R52离散数学定理定理1. 逆运算基本定理 设两个关系R  A×B，S A×B，这里 A,B是两个非空的集合。

则有 (1) 反身律： 　=R ； (2) 保序性： RS   ； R=S  = ； (3) 分配律： RS=  　 ； (4) 分配律： RS= 　 ；RRSRSRSRS53离散数学 (5) X×Y=Y×X ； (6) = ； (7)交换律：(R)=( ) ； (8)分配律：R\S= \　；RR S54离散数学[证]. 只证(1)，(4)，(7) （采用逻辑法）(1) 对任何(a,b)A×B ，有　　　 (a,b) 　  (b,a)  (a,b)R 所以　　= R RRR55离散数学 (4) 对任何(a,b)B×A ，有 (a,b)RS  (b,a)RS  (b,a)R  (b,a) S  (a,b) (a,b)  (a,b)  所以 RS =  。

RRSSSR56离散数学(7) 对任何(a,b)B×A ，有 (a,b)(R)  (b,a)R  (b,a)R  (a,b)  (a,b)( ) 所以 (R)= ( ) RRR57离散数学2° ° 关系的合成运算关系的合成运算定义定义2. 合成运算(composition operation)　设A，B，C是三个非空的集合对任何两个二元关系R A×B ， S B×C ，使得 RoS ={(a,c) : aAcC(bB)(aRbbSc)}A×C为关系的合成运算；称RoS是R与S的合成关系　显然，对任何(a,c)A×C， a RoS c  (bB)(aRb  bSc) 58离散数学例例2 . 设A={ a1,a2,a3} ，B={b1,b2} ，C={c1, c2, c3, c4}，关系　RA×B ， SB×C R ={(a1, b1),(a2, b2),(a3, b1)} S ={(b1, c4),(b2, c2),(b2, c3)} 于是，我们得到R与S的合成关系为　　R o S ={(a1, c4),(a2, c2) ,(a2, c3),(a3, c4)} 其合成关系的关系图为59离散数学例例3.3.设A是老年男子的集合，B是中年男子的集合，C是青少年男子的集合。

R是由A到B的父子关系， R A×B S是由B到C的父子关系， SB×C 则复合关系R o S是A到C的祖孙关系b1b2Ba1a2a3Ac1c2c3c4CRSRoS60离散数学定理定理2. 合成运算基本定理 设R, R1, R2  A×B， S, S1, S2  B×C，T  C×D ，这里 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；61离散数学(5)左分配律：R o (S1∪S2) = (R o S1) ∪ (R o S2) ；　右分配律： (S1∪S2) o T = (S1 o T) ∪ (S2 o T)；(6)左分配不等式： R o (S1∩S2) (R o S1)∩(R o S2)； 右分配不等式： (S1∩ S2) o T (S1 o T)∩(S2 o T)；(7) (R o S) = o 。

SR62离散数学[证]. 书上P30页 63离散数学w 但是合成运算不满足交换律即，一般　　　　　 R o SS 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)} 的合成关系为 R o S= {(a,e),(b,e),(c,b)}， So R = {(a,d),(c,b),(d,b)} 所以 R o SS o R 　 64离散数学3°°关系矩阵的合成运算关系矩阵的合成运算　 设R A×B ， SB×C 是两个二元关系，其合成关系为R o S这里A={ a1,a2,,am} ，B={b1,b2 , , bl} ，C={c1, c2, ,cn} 并设它们的关系矩阵分别为 MR=(xij)m×l ， MS=(yij)l×n ， MR o S =(uij)m×n 则我们有：　  MR o S = MR o MS　 其中：我们令　 MR o MS = (tij)m×n 　　　tij = (xik  ykj) (1i  m,1  j  n)65离散数学注：这里关系矩阵的合成运算与《线性代数》中的一般矩阵的乘法运算颇为相似。

所不同的是：乘法现在换成布尔乘()；加法现在换成布尔加()值得注意的是：这里的布尔加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 =66离散数学　现在我们计算 　 MR o MS = = 其中： t25= (x2k  yk5) =(x21y15)(x22y25)(x23y35)(x24y45)(x25y55) =(0 0) (11) (0 0) (0 0) (0 0) =0  1  0 0  0 =1 这说明　MR o S = MR o MS　。

67离散数学4° ° 关系的复合幂与闭包关系的复合幂与闭包定义定义3. 关系的复合幂　 设A是非空集合R A×A ， k为一正整数 ，规定 (1) R0 = IA (2) R1 = R (3) Rm+1 = Rm o R称为关系R的复合幂　68离散数学定理定理3. 设A是非空集合，R A×A ， m与n为非负整数 ，则 (1) Rm o Rn = Rm+n (2) (Rm)n = Rmn　69离散数学[证]. (1) 固定 m，对 n 用数学归纳法当 n = 1 时， Rm o R1 = Rm+1 （定义）假设当 n = k 时， Rm o Rk = Rm+k 那么当 n = k+1 时， Rm o Rk+1 = Rm o Rk o R1 = Rm+k o R1 = Rm+k+1 = Rm+(k+1)由归纳法知，对任意 m、n 均有 Rm o Rn = Rm+n 　70离散数学[证]. (2) 固定 m，对 n 用数学归纳法当 n = 1 时， (Rm )1 = Rm = Rm*1 假设当 n = k 时，有 (Rm )k = Rmk 那么当 n = k+1 时， (Rm )k+1 = (Rm )k o Rm = Rmk o Rm = Rmk+m = Rm(k+1)由归纳法知，对任意m、n均有 (Rm )n = Rmn 　71离散数学复合幂的注意要点：复合幂的注意要点：(1) R0 = IA = I R1 o R0 = R0 o R1 = R1 = R(2) R2 = R o R 当(a,b)  R2 时，有一个媒介元素 t ，t  A，使得(a,t)  R 且(t,b)  R，即a,b有间接R关系。

当(a,b)  R3 时，有两个媒介元素 t1、t2 ，使得(a,t1)  R ，(t1,t2)  R， (t2,b)  R，即a,b有二阶间接R关系 当(a,b)  Rn 时，有n-1个媒介元素 ，a,b有n-1阶间接R关系　72离散数学 (3)复合幂的并 (a,b)  R ∪ R2 直接、间接关系 (a,b)  R ∪ R2 ∪ R3 直接、间接、二阶间接关系　 (a,b)  R ∪ R2 ∪ R3 ∪ ‥ ‥ ∪ Rn a,b之间有不超过n-1阶间接关系73离散数学 §5. 等价关系等价关系 1°°等价关系和等价类等价关系和等价类定义定义1.等价关系(equivalence relation) 设二元关系R A×A这里A是非空的集合　R是A上的等价关系R是自反的、对称的、传递的 显然　(R) = (R) = A 　(因为等价关系是自反的)；74离散数学例例1.同乡关系是等价关系。

例例2 .平面几何中的三角形间的相似关系是等价关系例例3 .平面几何中的三角形间的全等关系是等价关系例例4 .平面几何中的直线间的平行关系是等价关系75离散数学例例5 .设N是自然数集，m是一正整数，　R={(a,b) :aN  bN  a  b (mod m)}由等价关系的定义知R是N上等价关系；我们称R是N上的模m同余关系例例6.6.非空集合A上的幺关系、全关系都是等价关系例例7.7.非空集合A上的空关系不是等价关系(因为空关系不自反) 例例8.8.设二元关系R A×A,这里 A={a,b,c} , R={(a,a), (b,b), (c,c), (b,c),(c,b)}则R是A上的等价关系其关系图如下　　　 76离散数学 等价关系的实质是将集合A中的元素进行分类　　　　bca77离散数学定义定义2.2.等价类(块)(equivalence classes (block))　设R是非空集合A上的等价关系。

对任何元素aA，由a生成的(或者说是由a诱导出的)关于R的等价类定义为　　　　　　　{b :bAbRa}记为aR. (显然有aR  A) 同时称a为等价类aR的代表元　　　　78离散数学定义定义3.3. 设R是非空集合A上的等价关系我们定义集合  R = {aR : aA} (注意：应去掉重复的类！) 为集合A关于等价关系R的商集记为A/R称A/R中元素的个数为R的秩79离散数学例例9 9. .设N是自然数集，m是一个正整数R是N上的模m同余关系，即　　　 R={(a,b) : a N  b N  a  b (mod m)}　 对于任何自然数a，b N ，　　 aRb  a  b (mod m)(kI)(a-b=km) ；由等价关系的定义知R是N上的等价关系； 对于任何自然数a N ，以a为代表元的等价类　 aR = am ={b :bNb  a (mod m)}； 自然数集N关于等价关系R的商集　80离散数学　N/R=  R = {0R,1R,2R,3R,…,m-1R } ；或者记作　Nm = N/ =  = {0m,1m,2m,3m,…,m-1m}；商集N/R共有m个等价类，故R的秩为m；　特别地，取m =5，则有 N５ = {0５,1５,2５,3５,45}；　又如　3５ ={3,8,13, …,5k+3, …} 　(这里：kN) 。

　　81离散数学例例1010. .例8中等价关系R的等价类为　aR = {a}, bR = cR = {b,c} ；其商集为 A/R= R = {aR , bR }={{a},{b,c}}；故其秩为2例例8.8.设二元关系R A×A,这里 A={a,b,c} , R={(a,a), (b,b), (c,c), (b,c),(c,b)}则R是A上的等价关系　　　82离散数学定理定理1. 设R是非空集合A上的等价关系对任意的a,bA，有 (1)aaR 　(故aR ≠)　； (2)aRb (即 (a,b)R)  aR = bR 　； (3)(3.1) aR∩ bR≠  aR = bR ( aRb，即 (a,b)R) ； (3.2) (a,b)R  aR∩ bR =  ； (4)两个等价类aR和bR ，要么完全重合(即aR = bR )，要么不交(即aR∩ bR =  )；二者必居其一，也只居其一。

83离散数学[证].（采用逻辑法） (1)对任何元素a，有 aA aRa (R是等价关系，故R自反) 　 aaR aR ≠ ；84离散数学 (2) 先证：aRbaR = bR 　　为证aR = bR ，须证　　(a) aR bR 　对任何元素x A ，有 xaR  xRa xRaaRb (已知条件： aRb)　 xRb (R是等价关系，故R传递)　 xbR　所以　aR  bR 85离散数学　　(b) bR  aR 　对任何元素x A ，有 xbR  xRb xRbaRb (已知条件： aRb) xRbbRa (R是等价关系，故R对称)　 xRa (R是等价关系，故R传递)　  xaR　 所以　bR  aR　　综合(a)和 (b)，即得 bR = aR ；86离散数学 次证： aR = bR  aRb 　　 aR ≠ 　　　　　　 (本定理的(1)) (x0A)(x0aR ) (x0A)(x0aR  x0bR ) (已知条件：aR = bR ) (x0A)(x0Rax0Rb ) (x0A)(aRx0x0Rb ) (R是等价关系，故R对称) aRb (R是等价关系，故R传递) 87离散数学(3)(3.1) aR∩bR≠ (x0A)(x0aR ∩bR) (x0A)(x0aR  x0bR ) 　 (x0A)(x0Rax0Rb ) (x0A)(aRx0x0Rb ) (R是等价关系，故R对称) aRb (即 (a,b)R) (R是等价关系，故R传递 )  aR = bR (本定理的(2)) ； 　88离散数学 (3.2) (整体采用反证法) 若(a,b)R ，则 aR∩ bR =  。

否则若 aR∩bR≠  aR = bR (本定理的(3.1)) aRb (本定理的(2)) (a,b)R 这就与已知条件：(a,b)R 矛盾；89离散数学 (4)对任何序偶(a,b) (a,b)A×A (a,b)R(a,b)R (二分法，互斥) (aR = bR)(aR∩ bR = ) (本定理的(3.1)和(3.2)，互斥) 90离散数学定义定义4.4. 设R和S是非空集合A上的两个等价关系若RS ，则我们称R细于S ，或S粗于R 例例1111. .设A是一非空集则 (1)A上最细的等价关系是幺关系；即　　　 R细=IA ， A/R细={{a} : aA} ；　(2)A上最粗的等价关系是全关系；即， R粗=A×A ，A/R粗={A} 。

91离散数学定理定理2.2.设R和S是非空集合A上的两个等价关系则 RS(aA)(aR aS) [证].（采用逻辑法） 先证：RS (aA)(aR aS) 对任何元素aA ，有 　　 x aR  xRa  xSa (已知条件：RS)  xaS 所以　aR aS　 所以(aA)(aR aS) ； 92离散数学 次证：(aA)(aR aS)RS 对任何序偶(a,b)A×A　　　 (a,b)R aRb bRa (R是等价关系，故R对称) baR baS (已知条件：(aA)(aR aS) ) bSa aSb (S是等价关系，故S对称)　  (a,b)S　 所以　R S 。

93离散数学定理定理3.3.设R和S是非空集合A上的两个等价关系则　 R=S(aA)(aR = aS) [证].(采用逻辑法) R=S RSSR  (aA)(aR  aS)(aA)(aS  aR) (定理2)  (aA)(aR  aSaS  aR) (aA)(aR = aS) 94离散数学注： 由定理2知，若两个等价关系相等，则每个元素所对应的等价类也相同；若两个等价关系的等价类集合相等，则两个等价关系相同　 由定理3知，等价关系与等价类集合一一对应即相同的等价关系对应着相同的等价类集合，不同的等价关系对应着不同的等价类集合95离散数学 2°°划分与等价关系划分与等价关系定义定义5.5.覆盖 划分(covering partition) 设A是一非空集合。

则A的(1)覆盖是一集合之集 ={A : A≠}，满足条件：　 A  ；　(2)划分是一集合之集 ={A : A≠}，满足条件： (a) A = ； (b) 1≠2A1∩A2 =  ； 　其中A称为划分的划分块(block of partition)注：由划分和覆盖的定义可知，A上的划分一定是A上的覆盖；反之则未必96离散数学定理定理4 设R是非空集合A上的等价关系则R的等价类之集　　　　R = { aR : aA }是A上的一个划分；等价类就是划分块[证].定理1的(1)不但直接给出等价类的非空性，而且由它可得等价类满足划分的条件(a) ；定理1的(4)直接给出等价类满足划分的条件(b)(详细叙述留给学者)注：定理4表明:由集合A上的等价关系R所产生的等价类之集构成集合A 上的一个划分97离散数学定理定理5. 设 ={A : A≠ }是非空集合A上的一个划分我们借助来定义A上的二元关系 R  A×A ，使得 　　　　R ={(a,b) : ( )(aA   bA )}则R是A上的等价关系。

我们称为是由划分产生的(或者说是诱导出的)A上的等价关系98离散数学[证].(采用逻辑法) (1)自反性：　 对任何元素a，有　 a A a 　 　　 (划分的条件(a)；A=　　　)　 ()(aA  ) ()(aA   aA  ) (a,a)R aR a 所以R是自反的；99离散数学　(2)对称性： 对任何元素a,bA ，有 aR b (a,b)R 　 　　 　 ()(aA  bA  ) ()(bA   aA  ) 　(b,a)R  bR a 所以R是对称的；100离散数学 (3)传递性：　对任何元素a,b,cA ，有 aR bbR c (a,b)R (b,c)R 　 　　 　 (1)(aA1bA 1)(2)(bA2cA2) ()(aA   bA   bA   cA  ) ()(aA   bA   cA  ) ()(aA   cA  ) 　 (a,c)R  aR c 所以R是传递的； 所以R是等价的。

注：定理5表明:由集合A上的划分可产生A上的一个等价关系；划分块就是等价类101离散数学定理定理6设R是非空集合Ａ上的等价关系， 是A上的一个划分那么 R= R  R =  注： R是由划分所产生的A上的一个等价关系；　　 R是由等价关系R所产生A上的一个的划分；102离散数学[证]. (采用逻辑法) 先证： R= R  R =  对任何元素aA ，有 对任何元素xA ，有 　　　　 xaR 　　　  xRa  xRa (已知条件： R= R )  xaR 所以　aR=aR 所以 (aA)(aR=aR ) 　所以 R ={aR : aA }={aR : aA }=  ；103离散数学 次证： R =  R= R 　对任何序偶(a,b)A×A　　　 (a,b)R aRb bRa (R是等价关系，故R对称) baR baR (已知条件：R = (aA)(aR=aR ) ) bR a aR b (R是等价关系，故R对称)　 (a,b)R 　所以　 R= R 。

104离散数学注：由定理4,5,6可知：由等价关系可以产生一个划分，由划分可以产生一个等价关系；　　划分与等价关系是一一对应的即每个划分对应一个等价关系，且每个等价关系对应一个划分105离散数学 §6. 半序关系半序关系定义定义1.1.半序关系(partial order relation) 设二元关系R A×A这里A是非空的集合　R是A上的半序关系R是自反的、反对称的、传递的显然　(R) = (R) = A 　(因为半序关系是自反的)；通常，半序关系R记为 ，称系统(A,)为半序集(poset)106离散数学例例1.1.自然数集N、整数集I、有理数集Q 、实数集R上的小于等于关系‘  ’都分别是这些数集上的半序关系；因为，对任何数a,b,c a a ； a b  b a  a=b ； a b  b c  a c ；所以(N, ) ,(I , ) , (Q, ) , (R, ) 都是半序集107离散数学例例2.集合X的幂集2x上的包含关系‘’是其上的半序关系；因为对任何子集A,B,C A  A ； A  B  B  A  A=B ； A  B  B  C  A  C ；故(2x, ) 是半序集。

例例3.3. 自然数集N、整数集I、有理数集Q 、实数集R上的小于关系‘  ’都不是这些数集上的半序关系；因为， 不是自反关系，即对任何数a, a ≮a ；故 是反自反关系108离散数学注：一般我们定义：拟序(quasi order)　　二元关系R A×A(A) 是A上的拟序关系R是反自反的、传递的拟序一般记作，称系统(A,)为拟序集； 拟序与半序的关系是：对任何元素a,bA ababab ；　因此，小于关系 是拟序； (N,  ) ,(I ,  ) , (Q,  ) , (R,  ) 都是拟序集例例4.集合X的幂集2x上的真包含关系‘’不是其上的半序关系；因为， 不是自反关系，即对任何子集A,AA ；故是反自反关系注：因此，真包含关系是拟序； (2x, ) 是拟序集109离散数学定义定义2.可比较性(comparability) 设(A, )是一半序集，a与b是A中的一对元素我们称　　a与b是可比较的  abba 　注： 否则，若abba ，则称a与b是不可比较的；　　 半序关系实际上是在集合A上建立了一种比较关系；110离散数学例例5. .对于小于等于关系‘  ’，任何二数a,b都是可比较的；即总有　a  bb  a 　。

例例6. .对于包含关系‘’ ，任何二集合A,B不都是可比较的；即不总是有　A  BB  A 　111离散数学定义定义3.全序关系 线性序链(total order, linear order , chain) 设(A, )是一半序集 是A上的全序关系 满足全可比较性： 　 (aA)(bA)(abba) 　　这时，我们简称是全序或线性序；称(A, )是一全序集注： 否则，我们则称是非线性序(nonlinear order)；　　 非线性序在实际中有很重要的作用；也是本课程的一个重要研究对象112离散数学例例7.小于等于关系‘  ’是全序关系； 包含关系‘’一般不是全序关系例例8.(I , ) , (R, ) 都是全序集但是在(I , ) 中每个整数，下一个比它大的或比它小的（即紧挨着它的）那个数都可确定；而在(R, ) 中却不可能113离散数学定义定义3.直接后继　 后继(direct successor, successor) 设(A, )是一半序集，a与b是A中的一对元素。

我们称 b是a的直接后继 aba  b(tA)(a  tt bt=at=b)直接后继简称后继； a的后继记作a+，即b= a+ ，这时称a是b的前驱或前趋(predecessor)114离散数学例例9. (Nm, ) , (N, ) ,(I , ) , (R, ) 都是全序集这里 都是数的小于等于关系；而 Nm={0,1,2,,m-1}于是 (Nm, )除尾元素m-1外，每个元素都有后继；除首元素0外，每个元素都有前驱； (N, )的每个元素都有后继；除首元素0外，每个元素都有前驱； (I, )的每个元素都有后继；每个元素都有前驱； (R, )的每个元素都没有后继；每个元素都没有前驱115离散数学半序集的表示法半序集的表示法——哈斯图哈斯图(Hasse) 通常用Hasse图表示半序关系半序集(A, )的Hasse图是一个图 G =(V ,E) 其中： V= A 是结点集； E={(a,b) : aAbAa  bb= a+}是边集 在画法上,我们规定： (1)结点a+必须画在结点a 的紧(斜)上方； (2)不画边的方向。

注：与关系图相比， Hasse图 省略了自反性的边(圈)； 省略了(反对称性)方向； 省略了传递性的边；116离散数学例例10. 设A ={a,b,c}, 　2A={,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}} 由于2A上的包含关系是自反的、反对称的、传递的，故包含关系是2A上的半序关系，(2A, ) 是半序集 2A上的包含关系的Hasse图如右图所示 { }{a}{c}{b,c}{a,b,c}{a,b}{a,c}{b}例10117离散数学注：从上例可以看出： 在非线性半序集中，直接后继一般不唯一； 其Hasse图呈现网格状；其实正是这点导致一门现代数学的重要学科——格论的出现；而此例正好给人们形象、直观的展现出布尔代数(用其三大特例之一——集合代数来表现)的内部数学结构 118离散数学例例11. 设A = {2,3,4,6,7,8,12,36,60}，R ={(a,b):aAbAa | b}，即，R是A上的整除关系 由整除的性质知R是自反的、反对称的、传递的。

　由半序关系的定义知R是A上的半序关系 　R的Hasse图如右图：603687423612例11119离散数学例例12. 设A ={2,3,6,12,24,36}, R={(a,b):aAbAa | b} R是A上的整除关系 由整除的性质知R是自反的、反对称的、传递的由半序关系的定义知R是A上的半序关系 R的Hasse图如右图：243632612例12120离散数学注：从以上两例可以看出： 虽然同为整除关系，但由于集合不同，其Hasse图就呈现出明显的不同；这说明两例中的半序集是不同的；所以，在论及半序关系时，重要的是一定要指明其是那个集合上的半序关系；半序集是一个整体，不能分而论之121离散数学定义定义4 最大元 最小元 (greatest element, least element) 设(A, )是半序集，BA ，x0 B 则我们称 (1)x0是B的最大元(xB)(x x0) ； (2)x0是B的最小元(xB)(x0 x) 注：最大(小)元一般未必一定存在；即使B(甚或A)是有限集合也未必；  B的最大(小)元若存在，则一定在B中；122离散数学定理定理1. 设(A,)是半序集,BA。

若B有最大(小)元，则必是唯一的[证].（采用逻辑法）只证最大元的唯一性 x01是B的最大元  x02是B的最大元 (xB)(x x01)(xB)(xx02), x02 x01x01 x02 x01=x02 (是半序关系，故有反对称性) 所以， B的最大元是唯一的123离散数学定义定义5. 极大元 极小元 (maximum element, minimal element) 设(A,)是半序集，BA ， x0 B 则我们称 (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中。

124离散数学　定义定义6.上界 下界(upper bound,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(或A)也不一定有限； 上界、下界、界即使存在，一般也是不唯一的；  B的上界、下界、界若存在，可以在B中，也可以不在B中125离散数学例例13. (R, ) 是全序集取B=(0,1)={x : xR0x1}R 于是， B有无穷个上界，无穷个下界；从而B是有界集 但是B却不是有限集，而是一个无限集126离散数学定义定义7. 上确界 下确界 (least upper bound, greatest lower bound) 设(A,)是半序集，BA ， z0 A 。

则我们称 (1)z0是B的上确界(xB)(xz0)(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)127离散数学注：上(下)确界一般不一定存在；即使B(甚或A)是有限集合也未必；  B的上(下)确界若存在，可以在B中，也可以不在B中；例例1414.令：A={ ：nNn1} B={ ：nNn1} X=AB 则B中每个元素都是集合A的上界,但A无上确界,即LUB(A) 不存在； A中每个元素都是集合B的下界,但B无下确界,即GLB(B) 不存在128离散数学定理定理2. 设(A,)是半序集,BA若B有上(下)确界，则必是唯一的[证].仿定理1可证留给学者注：最大(小)元一定是极大(小)元； 极大(小)元不一定是最大(小)元； 极大(小)元存在不一定有最大(小)元； 最大(小)元一定是上(下)确界； 上(下)确界不一定是最大(小)元； 上(下)确界存在不一定有最大(小)元； 上(下)确界一定是上(下)界； 上(下)界不一定是上(下)确界； 上(下)界存在不一定有上(下)确界； 讨论B的上(下)确界的前提是B的上(下)界存在；129离散数学例例15. 设A={2,3,4,6,7,8,12,36,60}, R={(a,b) : aAbAa | b}, R是A上的整除关系。

根据前面例11可知 ，R是A上的半序关系取B1={7,8}, B2={8,12}, B3={2,3}, B4={2,4,12}则:集合最大元 最小元 极大元 极小元上界下界 上确界 下确界B1={8,12}无无8,128,12无2,4无4B2={2,3}无无2,32,36,12,36,60无6无B3 ={7,8} 无无7,87,8无无无无B4 ={2,4,12}12212212,36,602122130离散数学定义定义8. 良序集(well ordered set) 设(A, )是半序集则我们称 (A, )是良序集  A的每个非空子集都有最小元　  (B A)(x0B) (xB)(x0 x) 这时我们称半序(关系)是良序(关系)131离散数学例例16. (N, )是良序集；而自然数集N上的小于等于关系 是良序关系　(I , ) 虽是全序集，但却不是良序集；从而整数集I上的小于等于关系  不是良序关系注：从上例我们可以得到　　全序集未必一定是良序集；132离散数学定理定理3. 设(A,)是良序集那么　(1) (A,)是全序集；(即，良序集一定是全序集) (2)对于任何元素aA，若a不是A的最大元，则a的直接后继a+一定存在；即　(aA)((xA)(xa) (bA)(b= a+ ) ) 。

133离散数学[证]. (采用构造法) (1)对于任二元素a,bA,构造一子集B={a,b}A,显然B是非空的，由(A,)是良序集，知B有最小元 若a是B的最小元，那么有ab；　 若b是B的最小元，那么有ba； 因此,总有abba 即(aA)(bA)(abba), 全可比较性成立，所以， 是全序，(A,)是全序集134离散数学　(2)对于任何元素aA,且a不是A的最大元，构造一子集B={x:xaax}A,显然B是非空的(因为a不是A的最大元 (已知条件)  (xA)(xa) (xA) (xa) (xA)(axax) (因是全序) B　　因此,由(A,)是良序集，知B有最小元135离散数学　设B的最小元为b，则我们可证a的直接后继a+ = b，总是存在 由于bB，故此ba，且ab； 对于任何元素tA,若at且tb,那么(二分法) 　或者t=a；　　 或者ta,则加上at,可知tB,因此,由b是B的最小元,得到bt,再加上假设tb,由的反对称性,我们得到t=b; 因此,总有t=a 或者t=b。

所以， b是a的直接后继，即a+ = b 136离散数学重点要求重点要求 w掌握序偶和笛卡尔积的概念掌握序偶和笛卡尔积的概念w掌握二元关系的形式定义及其各种表示方法：序偶，掌握二元关系的形式定义及其各种表示方法：序偶，矩阵，关系图等；能正确使用集合表达式，关系距阵，矩阵，关系图等；能正确使用集合表达式，关系距阵，关系图等表示给定的关系，并要求能够从一种形式写关系图等表示给定的关系，并要求能够从一种形式写出另一种形式出另一种形式w掌握关系的运算，包括集合运算以及关系的复合和关掌握关系的运算，包括集合运算以及关系的复合和关系的逆运算系的逆运算w掌握二元关系的各种特殊性质：自反，反自反，对称，掌握二元关系的各种特殊性质：自反，反自反，对称，反对称，传递等，并理解这些性质如何反映在关系图反对称，传递等，并理解这些性质如何反映在关系图上，关系矩阵上等上，关系矩阵上等w掌握集合中二元关系的闭包的意义和其基本性质，能掌握集合中二元关系的闭包的意义和其基本性质，能求出有限集上的二元关系的闭包求出有限集上的二元关系的闭包137离散数学w掌握等价关系的概念，并掌握覆盖、划分、等价类、掌握等价关系的概念，并掌握覆盖、划分、等价类、商集的定义和基本性质，弄清楚等价关系与划分之间商集的定义和基本性质，弄清楚等价关系与划分之间的关系。

牢记等价关系的的关系牢记等价关系的分类分类作用w掌握半序、半序集、全序、良序等概念，以及半序集掌握半序、半序集、全序、良序等概念，以及半序集的可比较性、极大元、极小元、最大元、最小元、上的可比较性、极大元、极小元、最大元、最小元、上界、下界、最大下界、最小上界、直接后继等概念界、下界、最大下界、最小上界、直接后继等概念牢记半序关系的牢记半序关系的非线性非线性特性w能画出有限半序集的哈斯图能画出有限半序集的哈斯图, ,并根据图讨论半序集的并根据图讨论半序集的某些性质某些性质138离散数学w第二章　关系　到此已经结束！　139。