离散数学第二章关系.ppt
108页
离散数学离散数学西安交通大学西安交通大学电子与信息工程学院电子与信息工程学院计算机软件所计算机软件所刘国荣刘国荣1 等价关系等价关系叉积叉积关系关系幺关系幺关系元组元组全关系全关系传递闭包传递闭包逆关系逆关系复合关系复合关系关系幂关系幂自反传递闭包自反传递闭包自反关系自反关系对称关系对称关系反对称关系反对称关系传递关系传递关系半序关系半序关系空关系空关系余关系余关系并关系并关系差关系差关系交关系交关系2 离散数学 第二章第二章 关系关系 (relation) §1 . 集合的叉积集合的叉积 n元组元组 §2 .关系关系 §3 .关系的关系的表示表示 关系的性质关系的性质 §4 .关系的运算关系的运算 §5. 等价关系等价关系 §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 离散数学即 (a1, a2, , an)= (b1, b2, , bm) n=m(iN)(1i n)(ai = bi)；注：笛卡尔(1596-1650 )，法国数学家， 1637年发表《方法论》之一《几何学》，首次提出坐标及变量概念这里是其概念的推广定义定义2. 二个集合A，B的(二维或二重)叉积定义为 A×B ={(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} 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={(白狗,张三),(白狗,李四),(黄狗,张三),(黄狗,李四)} 一般地说，关于叉积和元组我们有： (1) (a, b) (b, a)； (2) A×B B × A ； (3)二元组不是集合，因为二元组中的分量计较顺6 离散数学序,而集合中的元素是不讲顺序的。
但是我们为了将所有的概念都统一于集合概念，我们可采用克亚托斯基(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维叉积如下： A×B×C=(A×B)×C A1×A2× ×An-1×An= (A1×A2× ×An-1)×An7 离散数学 (6)利用(5)所给的定义，我们可以递归的定义集合的叉积幂如下： A2= A×A A3 = A2 ×A An = An-1 ×A (7)我们规定空集与任何集合A的叉积是空集 。
即 A× = = ×A 由于若偶对的第一分量或第二分量不存在就没有偶对存在，故规定它们的叉积集合为空集是合理的定理定理1.设A,B,C,D是四个非空的集合那么 A×B = C×D A = C B = D 8 离散数学[证].):显然 )：（采用逻辑法）对任何的元素a,b aAbB (a,b)A×B (a,b)C×D (条件：A×B = C×D ） aCbD 所以 A = C B = D 定理定理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) 9 离散数学 (叉积对并的)； (3)右分配律：(A∩B)×C = (A×C)∩(B×C) (叉积对交的)。
[证].只证(1)（采用逻辑法） 对任何的元素a,b (a,b)A×(B∪C) aAb B∪C aA(bBbC) (aAbB)(aAbC) (分配律：p(qr)(pq)(pr)) (a,b)A×B(a,b)A×C (a,b)(A×B)∪(A×C) 所以 A×(B∪C) = (A×B)∪(A×C) 10 离散数学 §2 .关系关系 一一.关系的基本概念关系的基本概念定义定义1 .二元关系(binary relation) 设A,B是两个非空的集合 二重叉集A×B 的任何一个子集R都称为是从集合A到集合B的一种二元关系即 RA×B ； 当 (a,b)R 时，称a与b有关系R ，记为 aRb ； 当 (a,b)R 时，称a与b没有关系R ，记为 或 ； 当A=B时，即RA×A，则称R是A上的一个二元关系例例1 . 设A是西安交通大学全体同学组成的集合。
11 离散数学 R={(a,b) : aAbAa与b是同乡}A×A 于是，R是西安交通大学同学之间的同乡关系例例2 . 设A是某一大家庭 R1 = {(a,b) : aAbAa是b的父亲或母亲}A×A R2 = {(a,b) : aAbAa是b的哥哥或姐姐}A×A R3 = {(a,b) : aAbAa是b的丈夫或妻子}A×A 于是， R1是父母与儿女之间的关系，即父母子女关系； R2是兄弟姐妹之间的关系，即兄弟姊妹关系； R3是夫妻之间的关系，即夫妻关系例例3 . 设N是自然数集合 12 离散数学 R= { (a,b) : aNbNa|b } N×N 则R就是自然数集合上的整除关系例例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上的一个二元关系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) , (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) : mNnNmn}NN S=整除关系={(m,n) : mNnNm|n}N N 则 R =大于等于关系()； RS=小于等于关系() ；15 离散数学 RS=不相等的整除关系()； R\S=小于又不整除关系( ∤)； S\R=相等关系(=) 5°关系的扩充(expansion)： 若R1 R2 ，则称关系R2 是关系R1的一个扩充； 6° n元关系： n元关系R是n 维叉积的一个子集；即 R A1A2 AnR1R216 定义定义3.前域(domain) 后域(codomain) 设A,B是两个非空集合，R 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)}。
则 (R) = {1,2,3}A ， (R) = {2,4,6}B 二二.关系的一些关联性质关系的一些关联性质离散数学A (R)B (R)abR17 离散数学定理定理1. 设R1,R2 A×B是两个关系若 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是A×B上的两个二元关系则 (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) (R1∪R2)， (R2) (R1∪R2) 故根据第一章§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)∪ (R2) (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) 其次，反方向的包含不成立且看下面的反例例例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 A×B下的关联集下的关联集 (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 A×B是一个二元关系， A1 ,A2 A 则 (1)保序性：A1 A2 R(A1) R(A2) ； (2)R(A1∪A2) = R(A1)∪R(A2) ； (3)R(A1∩A2) 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,c),(c,b)}那么 R(a)= {a,b}， R(b)= {c} ； 并且如果 A1 = {c,d} ，那么 R(A1)={a,b,c} 23 离散数学 §3 .关系的关系的表示 表示 关系的性质关系的性质 一一.关系表示法关系表示法 1°关系的矩阵表示法 设关系RA×B ， 这里A,B是两个非空的有限集合， A={ a1,a2,a3,…,am } ， B={ b1,b2,b3,…,bn } 则我们可用一个m×n阶0—1矩阵MR来表示关系R，我们称此矩阵MR为关系R的关系矩阵(relation matrix) MR=(xij)m×n ，其中 1 当（ai,bj) R时 xij = ( i=1,…,m ； j=1,…,n) 0 当（ai,bj) R时24 离散数学例例1 .设关系 RA×B ，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 .设关系 SA×A ，A={ a1,a2,a3} ， S={ (a1, a1),(a2, a2),(a3, a3),(a1, a3),(a3, a1) ,(a2, a3),(a3, a2)} 于是，我们得到S的关系矩阵MS为(上面右矩阵)b1b2b31a1a2a3a4001011010010a1a2a31a1a2a3１01０1１1１１25 离散数学 2°关系的图形表示法 设关系RA×B ， 这里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相连；26 离散数学 有时我们会用两个圆圈分别将表示两个集合A和B中元素的结点圈起来 所有有向弧的始端结点构成 (R)；所有有向弧的终端结点构成 (R) 若A=B，这时令VR =A，并规定只画表示一个集合元素的结点；表示元素间关系的有向弧也只在此一个集合的结点间画出 例例3 .设关系 RA×B，A={ a1,a2,a3,a4 }，B={b1,b2,b3} R ={ (a1, b2),(a1, b3),(a2, b3),(a3, b1),(a4, b2)} 于是，我们得到R的关系图GR为下面左图27 离散数学例例4 .设关系 SA×A ，A={ a1,a2,a3} ， S={ (a1, a1),(a2, a2),(a3, a3),(a1, a3),(a3, a1) ,(a2, a3),(a3, a2)} 于是，我们得到S的关系图GS为上面右图注： 图中各结点所带的小圆圈称为自反圈；一对结点间的来回边称为双向弧；否则，一对结点间只有一条边，则此边称为单向弧。
关系的表示法有三种:集合表示法,矩阵表示法,图形表示法a1a2a3a4b1b2b3RABGRa1a2a3GS28 离散数学 二二 .关系的性质关系的性质 设二元关系RX×X(或者说RX2)，这里X是一集合则R称为是X上的 1°自反关系(reflexive relation)：当且仅当R满足 自反性：(xX)(xRx) ； 显然，对于自反关系R， (R) = (R) = X 反自反关系(irreflexive relation)：当且仅当R满足 反自反性：(x X)( ) 或(x X)(xRx) ； 常见的自反关系有相等关系(=)，小于等于关系()，包含关系()等； 而不相等关系()，小于关系()，真包含关系()等都不是自反关系，它们都是反自反关系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上的幺关系； 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 离散数学注：对称性和反对称性是关系的两个极端性质；因此，对称关系和反对称关系是两种极端关系； 从关系矩阵来看：对称关系的关系矩阵是对称矩阵。
即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),(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 离散数学关系，同乡关系，后裔关系等； 而不相等关系()，父子关系，朋友关系，同学关系等都不是传递关系。
注：传递性和反传递性是关系的两个极端性质；因此，传递关系和反传递关系是两种极端关系； 概念反传递性和反传递关系一般不甚用，所以不加讨论；例例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 x∥y} 由平面几何的知识知:若x∥y且y∥z，则 x∥z 由传递关系的定义知R是X上的传递关系例例10. 设X是平面上三角形的集合相似关系 R={(x, y) : xX yX x∽y} 由平面几何的知识知:若x∽y 且y∽z ，则 x∽z 由传递关系的定义知R是X上的传递关系例例11. 相等关系是自反的、对称的、反对称的、传递关系。
全关系X2是自反的、对称的、传递的 幺关系I 是自反的、对称的、反对称的、传递的 35 离散数学 空关系是反自反的、对称的、反对称的、传递的36 离散数学 §4 .关系的运算关系的运算 1°°关系的逆运算关系的逆运算定义定义1.逆运算(converse operation) 设A，B是两个非空的集合我们称一元运算 : 2A× B 2 B ×A 对任何二元关系RA×B，使得 = {(b,a) : bBaAaRb}B×A为关系的逆运算；称 是R的逆关系(converse of relation) 显然，对任何(b,a) B×A，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 A×B，S A×B，这里 A,B是两个非空的集合。
则有 (1)反身律： =R ； (2)保序性：RS ； R=S = ； (3)分配律：RS= （逆对并的）； (4)分配律：RS= （逆对交的）； (5)X×Y=Y×X ； 38 离散数学 (6) = ； (7)交换律：(R)=( ) （逆与余的）； (8)分配律：R\S= \ （逆对差的）；[证].只证(1)，(4)，(7) （采用逻辑法） (1)对任何(a,b)A×B ，有 (a,b) (b,a) (a,b)R 所以 =R (4)对任何(a,b)B×A ，有 (a,b)RS (b,a)RS39 离散数学 (b,a)R(b,a) S (a,b) (a,b) (a,b) 所以 RS = 。
(7)对任何(a,b)B×A ，有 (a,b)(R) (b,a)R (b,a)R (a,b) (a,b)( ) 所以 (R)= ( ) 40 离散数学 2°°关系的合成运算关系的合成运算定义定义2.合成运算(composition operation) 设A，B是两个非空的集合我们称二元运算 o : 2A× B × 2B× C 2 A×C 对任何两个二元关系R A×B ， S B×C ，使得 RoS ={(a,c) : aAcC(bB)(aRbbSc)}A×C为关系的合成运算；称RoS是R与S的合成关系 显然，对任何(a,c)A×C，aRoSc(bB)(aRbbSc) 例例2 .设A={ a1,a2,a3} ，B={b1,b2} ，C={c1, c2, c3, c4} 关系 RA×B ， SB×C 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)} 其合成关系的关系图为例例3.3.设A是老年男子的集合，B是中年男子的集合，C是青少年男子的集合。
R是由A到B的父子关系， R A×B b1b2Ba1a2a3Ac1c2c3c4CRSRoS42 离散数学 S 是由B到C的父子关系， SB×C 则复合关系R o S是A到C的祖孙关系定理定理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； (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)；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)) (量词前移：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 (S1∪S2)c (bB)(aRb b(S1∪S2)c) (bB)(aRb (bS1cbS2c)) (bB)((aRbbS1c)(aRbbS2c)) (对的分配律：p(qr)(p 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 (S1∪S2) = (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 o SS o R 3°°关系矩阵的合成运算关系矩阵的合成运算 设R A×B ， SB×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) (1i m,1 j n)47 离散数学注：这里关系矩阵的合成运算与《线性代数》中的一般矩阵的乘法运算颇为相似。
所不同的是：乘法现在换成布尔乘()；加法现在换成布尔加()值得注意的是：这里的布尔加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 =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 离散数学 对任何的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)m×n = (tij)m×n 所以 MR o S = MR o MS 50 离散数学 4°°关系的闭包运算（宏运算）关系的闭包运算（宏运算）定义定义3.关系的合成幂(nth power) 设二元关系R A×A，nN 。
这里A 是一个非空的集合， N 是自然数集我们规定： (1) R0 =I （这里I=IA={(a,a) : aA}是A上的幺关系）； (2) R1 =R； (3) Rn+1 =RnoR (特别地：R2 =RoR )定理定理3.指数律 设二元关系R A×A，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 同理可证 归纳变量选取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 A×A,这里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 = ，这说明空集是合成运算的零元 一般地 a Rnb (c1)(c2) (cn-1)(aRc1 c1Rc2 cn-1Rb) ； 特别地 a R２b (c) (aRc cR b) 53 离散数学定义定义4.闭包运算(closure operation) 设二元关系R A×A 这里A 是一个非空的集合我们定义： (1)传递闭包(transitive closure)： R＋ = Rk =R∪ R２ ∪ R3 ∪ ∪ Rk ∪ ； (2)自反传递闭包(reflexive and transitive closure)： R = Rk =I∪R∪ R２ ∪ R3 ∪ ∪ Rk ∪ ac1c2bcn-1cn-2RnRRRRRabcR２RR54 离散数学注：传递闭包有时也记为t( R)；自反传递闭包有时也记为rt( R)；其实还有别的闭包； a R＋b (kN)(k 1)(aRkb) ； a R b (kN)(aRkb) (a=b)(kN)(k 1)(aRkb)(a=b)(aR＋b) 。
定理定理4.传递闭包基本定理 设二元关系R A×A，R 则 (1)若 mN，m 1 ，则 Rm R＋ ；特别地 R R＋ ； (2) R＋是传递关系：即，对任何元素 a，b，c A ， aR＋bbR＋caR＋c ； (3) R＋是包含R的最小传递关系：即，对任何二元关系SA×A，若RS且S也是传递关系，那么 R＋S ； (4)若|A|=n ，则 R＋ = Rk ；这时55 离散数学 a R＋b (kN)(1k n)(aRkb) ； (5)若R是传递关系, 则 R＋ = R [证].只证(2)(采用逻辑法) (2)对任何元素a，b，c A ，有 aR＋bbR＋c (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 y1Ry2 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 ) aR＋c 所以，R＋是传递的。
定理定理5.自反传递闭包基本定理 设二元关系R A×A，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的最小自反传递关系：即，对任何二元关系SA×A，若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 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 A×A这里A是非空的集合 R是A上的等价关系R是自反的、对称的、传递的 显然 (R) = (R) = A (因为等价关系是自反的)；例例1.同乡关系是等价关系例例2 .平面几何中的三角形间的相似关系是等价关系例例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 A×A,这里 A={a,b,c} , R={(a,a), (b,b), (c,c), (b,c),(c,b)}则R是A上的等价关系。
其关系图如下 61 离散数学 等价关系的实质是将集合A中的元素进行分类定义定义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 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 离散数学定理定理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 (已知条件： 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)(aRx0x0Rb ) (R是等价关系，故R对称) aRb (R是等价关系，故R传递 且 xpp ) (3)(3.1) aR∩bR≠ (x0A)(x0aR ∩bR) (x0A)(x0aR x0bR ) (x0A)(x0Rax0Rb ) (x0A)(aRx0x0Rb ) (R是等价关系，故R对称) aRb (即 (a,b)R) (R是等价关系，故R传递 且 xpp ) 68 离散数学 aR = bR (本定理的(2)) ； (3.2) (整体采用反证法) 若(a,b)R ，则 aR∩ bR = 。
否则若 aR∩bR≠ aR = bR (本定理的(3.1)) aRb (本定理的(2)) (a,b)R 这就与已知条件：(a,b)R 矛盾； (4)对任何序偶(a,b) (a,b)A×A (a,b)R(a,b)R (二分法，互斥) (aR = bR)(aR∩ bR = ) (本定理的(3.1)和(3.2)，互斥) 69 离散数学定义定义4.4. 设R和S是非空集合A上的两个等价关系若RS ，则我们称R细于S ，或S粗于R 例例1111. .设A是一非空集则 (1)A上最细的等价关系是幺关系；即 R细=IA ， A/R细={{a} : aA} ； (2)A上最粗的等价关系是全关系；即， R粗=A×A ，A/R粗={A} 。
定理定理2.2.设R和S是非空集合A上的两个等价关系则 RS(aA)(aR aS) [证].（采用逻辑法） 先证：RS (aA)(aR aS) 对任何元素aA ，有 70 离散数学 对任何元素xA ，有 x aR xRa xSa (已知条件：RS) xaS 所以 aR aS 所以(aA)(aR aS) ； 次证：(aA)(aR aS)RS 对任何序偶(a,b)A×A (a,b)R aRb bRa (R是等价关系，故R对称) baR 71 离散数学 baS (已知条件：(aA)(aR aS) ) bSa aSb (S是等价关系，故S对称) (a,b)S 所以 R S 。
定理定理3.3.设R和S是非空集合A上的两个等价关系则 R=S(aA)(aR = aS) [证].(采用逻辑法) R=S RSSR (aA)(aR aS)(aA)(aS aR) (定理2) (aA)(aR aSaS aR) (量词对的分配律：72 离散数学 x(A(x)xB(x) x(A(x)B(x)) ) (aA)(aR = aS) 注：由定理2知，若两个等价关系相等，则每个元素所对应的等价类也相同；若两个等价关系的等价类集合相等，则两个等价关系相同 由定理3知，等价关系与等价类集合一一对应即相同的等价关系对应着相同的等价类集合，不同的等价关系对应着不同的等价类集合 2°°划分与等价关系划分与等价关系定义定义5.5.覆盖 划分(covering partition) 设A是一非空集合。
则A的 (1)覆盖是一集合之集 ={A : A≠}，满足条件：73 离散数学 A ； (2)划分是一集合之集 ={A : A≠}，满足条件： (a) A = ； (b)1≠2A1∩A2 = ； 其中A称为划分的划分块(block of partition)注：由划分和覆盖的定义可知，A上的划分一定是A上的覆盖；反之则未必定理定理4 设R是非空集合A上的等价关系则R的等价类之集 R = { aR : aA }是A上的一个划分；等价类就是划分块[证].定理1的(1)不但直接给出等价类的非空性，而且74 离散数学由它可得等价类满足划分的条件(a) ；定理1的(4)直接给出等价类满足划分的条件(b)(详细叙述留给学者)注：定理4表明:由集合A上的等价关系R所产生的等价类之集构成集合A 上的一个划分定理定理5. 设 ={A : A≠ }是非空集合A上的一个划分我们借助来定义A上的二元关系 R A×A ，使得 R ={(a,b) : ( )(aA bA )}则R是A上的等价关系。
我们称为是由划分产生的(或者说是诱导出的)A上的等价关系[证].(采用逻辑法) (1)自反性： 对任何元素a，有75 离散数学 a A a (划分的条件(a)；A= ) ()(aA ) ()(aA aA ) (幂等律：p pp ) (a,a)R aR a 所以R是自反的； (2)对称性： 对任何元素a,bA ，有 aR b (a,b)R ()(aA bA ) ()(bA aA ) (交换律：pqqp )76 离散数学 (b,a)R bR a 所以R是对称的； (3)传递性： 对任何元素a,b,cA ，有 aR bbR c (a,b)R (b,c)R (1)(aA1bA 1)(2)(bA2cA2) ()(aA bA bA cA ) (由划分的条件(b)的逆否，有 A1∩A2{b} 1=2= ) ()(aA bA cA ) (幂等律：pp p )77 离散数学 ()(aA cA ) (合取分析式：pqp ) (a,c)R aR c 所以R是传递的； 所以R是等价的。
注：定理5表明:由集合A上的划分可产生A上的一个等价关系；划分块就是等价类定理定理6设R是非空集合Ａ上的等价关系， 是A上的一个划分那么 R= R R = 注： R是由划分所产生的A上的一个等价关系； R是由等价关系R所产生A上的一个的划分；78 离散数学[证]. (采用逻辑法) 先证： R= R R = 对任何元素aA ，有 对任何元素xA ，有 xaR xRa xRa (已知条件： R= R ) xaR 所以 aR=aR 所以 (aA)(aR=aR ) 所以 R ={aR : aA }={aR : aA }= ； 次证： R = R= R 对任何序偶(a,b)A×A (a,b)R79 离散数学 aRb bRa (R是等价关系，故R对称) baR baR (已知条件：R = (aA)(aR=aR ) ) bR a aR b (R是等价关系，故R对称) (a,b)R 所以 R= R 。
注：由定理4,5,6可知：由等价关系可以产生一个划分，由划分可以产生一个等价关系； 划分与等价关系是一一对应的即每个划分对应一个等价关系，且每个等价关系对应一个划分80 离散数学 §6. 半序关系半序关系定义定义1.1.半序关系(partial order relation) 设二元关系R A×A这里A是非空的集合R是A上的半序关系R是自反的、反对称的、传递的显然 (R) = (R) = A (因为半序关系是自反的)；通常，半序关系R记为≼ ，称系统(A, ≼)为半序集(poset)例例1.1.自然数集N、整数集I、有理数集Q 、实数集R上的小于等于关系‘ ’都分别是这些数集上的半序关系；因为，对任何数a,b,c a a ； a b b a a=b ； a b b c a c ；81 离散数学所以(N, ) ,(I , ) , (Q, ) , (R, ) 都是半序集例例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 ；故 是反自反关系注：一般我们定义：拟序(quasi order) 二元关系R A×A(A) 是A上的拟序关系R是反自反的、82 离散数学传递的拟序一般记作≺，称系统(A, ≺)为拟序集； 拟序与半序的关系是：对任何元素a,bA a ≺ b a ≼ b a b ； 因此，小于关系 是拟序； (N, ) ,(I , ) , (Q, ) , (R, ) 都是拟序集例例4.集合X的幂集2x上的真包含关系‘’不是其上的半序关系；因为， 不是自反关系，即对任何子集A,AA ；故是反自反关系注：因此，真包含关系是拟序； (2x, ) 是拟序集定义定义2.可比较性(comparability) 设(A, ≼)是一半序集，a与b是A中的一对元素我们称 a与b是可比较的 a ≼ b b ≼ a 83 离散数学注： 否则，若a ≼ bb ≼ a ，则称a与b是不可比较的； 半序关系≼实际上是在集合A上建立了一种比较关系；例例5. .对于小于等于关系‘ ’，任何二数a,b都是可比较的；即总有 a bb a 。
例例6. .对于包含关系‘’ ，任何二集合A,B不都是可比较的；即不总是有 A BB A 定义定义3.全序关系 线性序 链(total order, linear order , chain) 设(A, ≼)是一半序集 ≼是A上的全序关系 ≼满足全可比较性： (aA)(bA)(a ≼ b b ≼ a) 这时，我们简称是全序或线性序；称(A, ≼)是一全序集84 离散数学注： 否则，若(aA)(bA)(a ≼ b b ≼ a)，一般我们则称是非线性序(nonlinear order)； 非线性序在实际中有很重要的作用；也是本课程的一个重要研究对象字典序字典序(lexicographic) 设(, )是一全序集其中：是一有限集，称为字母表(alphabet)，任一元素a称为字母(alpha)， 是字母表中字母的自然顺序，则显然是一个全序故此,则(*, *)是一全序集,我们称其为字典序其中： * ={} 2 3 n (称为空字)其任何元素 w*称为一个字(word)；必有kN,使得 w k ，从而 w=(ai1,ai2,ai3, ,aik)=ai1ai2 ai3 aik这里aij (1 j k) 。
85 离散数学 我们定义二元关系* * × * ，使得； 对于任何二字w1=ai1ai2ai3aim和w2=bi1bi2bi3bin w1 * w2当且仅当 下列三条之一成立： (1)ai1ai2ai3aim=bi1bi2bi3bin ；(这时：m=n, aij=bij ) (2)ai1bi1 且ai1bi1 ； (3)存在着某个k N，1 k min(m,n)，使得 ai1ai2ai3aik-1=bi1bi2bi3bik-1且aikbik且aikbik 例例7.小于等于关系‘ ’是全序关系；包含关系‘’一般不是全序关系例例8.(I , ) , (R, ) 都是全序集但是在(I , ) 中每个整数，下一个比它大的或比它小的（即紧挨着它的）那个数都可确定；而在(R, ) 中却不可能86 离散数学定义定义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, )除尾元素m-1外，每个元素都有后继；除首元素0外，每个元素都有前驱； (N, )的每个元素都有后继；除首元素0外，每个元素都有前驱； (I, )的每个元素都有后继；每个元素都有前驱； (R, )的每个元素都没有后继；每个元素都没有前驱87 离散数学半序集的表示法半序集的表示法——哈斯图哈斯图(Hasse) 通常用Hasse图表示半序关系半序集(A, ≼)的Hasse图是一个图 G ≼ =(V ≼ ,E ≼) 其中： V ≼ = A 是结点集； E ≼ ={(a,b) : aAbAa ≼ bb= a+}是边集 在画法上,我们规定： (1)结点a+必须画在结点a 的紧(斜)上方； (2)不画边的方向注：与关系图相比， Hasse图 省略了自反性的边(圈)； 省略了(反对称性)方向； 省略了传递性的边；例例10. 设A ={a,b,c}, { }{a}{c}{b,c}{a,b,c}{a,b}{a,c}{b}例1088 离散数学 2A={,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}} 由于2A上的包含关系是自反的、反对称的、传递的，故包含关系是2A上的半序关系，(2A, ) 是半序集。
2A上的包含关系的Hasse图如上图所示注：从上例可以看出： 在非线性半序集中，直接后继一般不唯一； 其Hasse图呈现网格状；其实正是这点导致一门现代数学的重要学科——格论的出现；而此例正好给人们形象、直观的展现出布尔代数(用其三大特例之一——集合代数来表现)的内部数学结构 例例11. 设A = {2,3,4,6,7,8,12,36,60}， R ={(a,b):aAbAa | b}，即，R是A上的整除关系 由整除的性质知R是自反的、反对称的、传递的 由半序关系的定义知R是A上的半序关系 89 离散数学 R的Hasse图如下图左：例例12. 设A ={2,3,6,12,24,36},R={(a,b):aAbAa | b} R是A上的整除关系 由整除的性质知R是自反的、反对称的、传递的 由半序关系的定义知R是A上的半序关系 R的Hasse图如上图右：603687423612例11243632612例1290 离散数学注：从以上两例可以看出： 虽然同为整除关系，但由于集合不同，其Hasse图就呈现出明显的不同；这说明两例中的半序集是不同的；所以，在论及半序关系时，重要的是一定要指明其是那个集合上的半序关系；半序集是一个整体，不能分而论之。
定义定义4最大元 最小元(greatest element,least element) 设(A, ≼)是半序集，BA ，x0 B 则我们称 (1)x0是B的最大元(xB)(x ≼ x0) ； (2)x0是B的最小元(xB)(x0 ≼ x) 注：最大(小)元一般未必一定存在；即使B(甚或A)是有限集合也未必； B的最大(小)元若存在，则一定在B中；91 离散数学定理定理1. 设(A, ≼)是半序集,BA若B有最大(小)元，则必是唯一的[证].（采用逻辑法）只证最大元的唯一性 x01是B的最大元 x02是B的最大元 (xB)(x ≼ x01)(xB)(x ≼ x02), x02 ≼ x01x01 ≼ x02 (因x01 , x02B又都是B的普通一元；根据 普遍性特殊化：xA(x) A(y)；以及 合成律：(p q )( rs ) p r q s ) x01=x02 (≼是半序关系，故有反对称性) 所以， B的最大元是唯一的。
定义定义5.极大元 极小元 (maximum element,minimal element)92 离散数学 设(A, ≼)是半序集，BA ， x0 B 则我们称 (1)x0是B的一个极大元 (xB)(x0 ≼ xx x0) (xB)(x0 ≺ x) ； (2)x0是B的一个极小元 (xB)(x ≼ x0 x x0)(xB)(x ≺ x0) 注：极大(小)元一般不一定存在；但在B(或A)是有限集合时一定存在； 极大(小)元即使存在，一般也是不唯一的； B的极大(小)元若存在，则一定在B中 定义定义6.上界 下界(upper bound,lower bound) 设(A, ≼)是半序集，BA ， z0 A 则我们称 (1)z0是B的一个上界(xB)(x ≼ z0) ； 93 离散数学 (2)z0是B的一个下界(xB)(z0 ≼ x) ； (3)若B有一个上界，则称B上方有界； 若B有一个下界，则称B下方有界； 若B上、下方都有界，则称B有界。
注：上界、下界、界一般不一定存在； B(或A)有限不一定有上界、下界、界；有上界、下界、界B(或A)也不一定有限； 上界、下界、界即使存在，一般也是不唯一的； B的上界、下界、界若存在，可以在B中，也可以不在B中例例13. (R, ) 是全序集取B=(0,1)={x : xR0x1}R 于是， B有无穷个上界，无穷个下界；从而B是有界集 但是B却不是有限集，而是一个无限集94 离散数学定义定义7.上确界 下确界 (least upper bound,greatest lower bound) 设(A, ≼)是半序集，BA ， z0 A 则我们称 (1)z0是B的上确界 (xB)(x ≼ z0)(zA)((xB)(x ≼ z) z0 ≼ z) ； (2)z0是B的下确界 (xB)(z0 ≼ x)(zA)((xB)(z ≼ x) z ≼ z0) ； (3)上确界即是最小上界，记为LUB(B)； 下确界即是最大下界，记为GLB(B)。
注：上(下)确界一般不一定存在；即使B(甚或A)是有限集合也未必； B的上(下)确界若存在，可以在B中，也可以不在B中；95 离散数学例例1414.令：A={ ：nNn1} B={ ：nNn1} X=AB 则B中每个元素都是集合A的上界,但A无上确界,即LUB(A) 不存在； A中每个元素都是集合B的下界,但B无下确界,即GLB(B) 不存在定理定理2. 设(A, ≼)是半序集,BA若B有上(下)确界，则必是唯一的[证].仿定理1可证留给学者96 离散数学注：最大(小)元一定是极大(小)元； 极大(小)元不一定是最大(小)元； 极大(小)元存在不一定有最大(小)元； 最大(小)元一定是上(下)确界； 上(下)确界不一定是最大(小)元； 上(下)确界存在不一定有最大(小)元； 上(下)确界一定是上(下)界； 上(下)界不一定是上(下)确界； 上(下)界存在不一定有上(下)确界； 讨论B的上(下)确界的前提是B的上(下)界存在；例例15. 设A={2,3,4,6,7,8,12,36,60}, R={(a,b) : aAbAa | b}, R是A上的整除关系。
于是根据前面例11可知 ，R是A上的半序关系97 离散数学 其对应子集的各种性质的元素 列为下表： 集合最大元 最小元 极大元 极小元上界下界 上确界 下确界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,602122603687423612例14图例14表98 离散数学半序集的全序化半序集的全序化(非线性序的线性化非线性序的线性化) 设(A, )是一半序集，其中A={a1, a2, a3, , an}下面的拓扑排序(分类)(A topological sort)算法是将半序集(A,)整对(或者说转化)为一个全序集(A,≦)，并且满足 保序性： (aA)(bA)(ab a≦b) (也称为遗传性)注： 拓扑学主要是研究变化中的不变量； 而这里，全序化是变化；遗传性是不变量拓扑排序(分类)算法： No.1 k 1； (设置计数器) No.2 在A中任取半序集(A, )的一个极小元 aik ； No.3 若 k=n ，则算法停止；欲得之全序为： ai1 ≦ ai2 ≦ ai3 ≦ ≦ aik ≦ ≦ ain ； No.4 (否则kn) k k+1 ,A A\{aik} ；go to No.2 。
99 离散数学注： 拓扑排序算法所得之全序不是唯一的（因为极小元不唯一）； 例如，在例14中的半序集就可被转化为如下的全序： 7，3，2，6，4，12，8，60，36 问题： 有限半序集中一定有极小元吗？定义5下的注已经回答； 半序集的子集和原序还构成半序集吗？回答参见习题35定义定义8.良序集(well ordered set) 设(A, ≼)是半序集则我们称 (A, ≼)是良序集A的每个非空子集都有最小元 (B A)(x0B) (xB)(x0 ≼ x)这时我们称半序(关系) ≼是良序(关系)例例16. (N, )是良序集；而自然数集N上的小于等于关系100 离散数学 是良序关系 (I , ) 虽是全序集，但却不是良序集；从而整数集I上的小于等于关系 不是良序关系注：从上例我们可以得到 全序集未必一定是良序集；定理定理3. 设(A, ≼)是良序集那么 (1) (A, ≼)是全序集；(即，良序集一定是全序集) (2)对于任何元素aA，若a不是A的最大元，则a的直接后继a+一定存在；即 (aA)((xA)(x ≼a) (bA)(b= a+ ) ) 。
101 离散数学[证]. (采用构造法) (1)对于任二元素a,bA,构造一子集B={a,b}A,显然B是非空的，由(A, ≼)是良序集，知B有最小元 若a是B的最小元，那么有a ≼b； 若b是B的最小元，那么有b ≼a； 因此,总有a ≼bb ≼a 即(aA)(bA)(a ≼bb ≼a),全 可比较性成立，所以， ≼是全序，(A, ≼)是全序集2)对于任何元素aA,且a不是A的最大元，构造一子集 B={x:xaa ≼x}A,显然B是非空的(因为 a不是A的最大元 (已知条件) (xA)(x ≼a) (xA) (x ≼a) (量词对偶律:xA(x)xA(x)) (xA)(axa ≼x) (因是全序) B )102 离散数学 因此,由(A, ≼)是良序集，知B有最小元 设B的最小元为b，则我们可证a的直接后继a+ = b，总是存在 由于bB，故此ba，且a ≼b； 对于任何元素tA,若a ≼t且t ≼b,那么(二分法) 或者t=a； 或者ta,则加上a ≼t,可知tB,因此,由b是B的最小元,得到b ≼t,再加上假设t ≼b,由≼的反对称性,我们得到t=b; 因此,总有t=a 或者t=b。
所以， b是a的直接后继，即a+ = b 103 离散数学 [证]. (采用逻辑法) (1) (BA)(x0B) (xB)(x0 ≼ x) (因是良序) ({a,b}A)(x0{a,b})(x{a,b})(x0 ≼ x) (普遍性特殊化) ({a,b}A)(x0{a,b})(x0 ≼ ax0 ≼b) (aA)(bA)((a ≼aa ≼b)(b ≼ab ≼b)) (aA)(bA)(a ≼bb ≼a) (合取分析式：pqp ) 所以是全序关系； (2) (BA)(x0B) (xB)(x0 ≼x) (因是良序) (BA)(x0A)(x0B(xA)(xB x0 ≼x) (放大缩小法。
注意： 量词的特征谓词x0B作为合取项； 量词的特征谓词xB作为蕴含条件) (BA)(bA)(bB(tA)(tB b ≼t) 104 离散数学 (约束变项换名： xA(x)yA(y) (x0换名为b)； xA(x)yA(y) (x换名为t ) ) (B1={x : xa ax}A) (bA)(bB1(tA)(tB1b ≼t) (普遍性特殊化) ( a不是最大元 (已知条件) (xA)(x ≼a) (xA) (x ≼a) (量词对偶律：xA(x)xA(x) ) (xA)(axa ≼x) (因≼是全序) B1 ) (aA)(bA)(b aa ≼b(tA)(t a a ≼t b ≼t) ( bB1b aa ≼b )105 离散数学 (aA)(bA)(b a a ≼b (tA)(t a a ≼tt ≼b b ≼tt ≼b) (附加律：pq p r q r) (aA)(bA)(b aa ≼b (tA)(t aa ≼tt ≼b t=b) (≼是良序，故≼是反对称的) (aA)(bA)(b a a ≼b (tA)(a ≼tt ≼b t =at=b) (相容(析取)排斥法： r p q p r q ) (aA)(bA)(b= a+ ) 106 离散数学 作业作业 第二章第二章 P49 1.2)4) 3. 4 .1)3)5) 6. 7.1)改为 2) 9. 10.求R1, R3, R5, R7 11.1)3)5) 13. 15. 17.2)4) 18.2) 19.1)2)3) 20.1)2)3) 23.1)2) 25.2)4) 26.2)4) 28. 30.2)4) 31.3) 32. 34. 35. 36.1)3) 37.1)2)3) 107 离散数学w第二章 关系 到此已经结束！ 谢谢读者收看！ 作者：刘国荣 108 。
