离散数学 第二章 关系[2].ppt

1、1,离散数学,西安交通大学电子与信息工程学院计算机软件所刘国荣,2,3,离散数学,第二章关系(relation)1.集合的叉积n元组2.关系3.关系的表示关系的性质4.关系的运算5.等价关系6.半序关系,4,离散数学,1.集合的叉积n元组定义1.叉积，笛卡尔积(crossproduct,Cartesianproduct(1637)n个集合A1，A2，An的n维叉积定义为=A1A2An=(a1,a2,an):aiAi(1in)；n维叉积A1A2An的每个元素(a1,a2,an)都称为一个n元组（n-tuple）；即，叉积是元组的集合；每个n元组(a1,a2,an)的第i个位置上的元素ai称为该n

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

3、集；第二集合B称为后集。,6,离散数学,例1.A=a,b,c,B=0,1AB=(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=(白狗,张三),(白狗,李四),(黄狗,张三),(黄狗,李四)一般地说，关于叉积和元组我们有：(1)(a,b)(b,a)；(2)ABBA；(3)二元组不是集合，因为二元组中的分量计较顺,7,离散数学,序,而集合中的元素是不讲顺序的。但是我们为了将所有的概念都统一于集

4、合概念，我们可采用克亚托斯基(KazimierzKurafowski)在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维叉积如下：ABC=(AB)CA1A2An-1An=(A1A2An-1)An,8,离散数学,(6)利用(5)所给的定义，我们可以递归的定义集合的叉积幂如下：A2=AAA3=A2AAn=An-1A(7)我们规定空集与任何集合A的叉积是空集。即A=A由于若偶对的第一

5、分量或第二分量不存在就没有偶对存在，故规定它们的叉积集合为空集是合理的。定理1.设A,B,C,D是四个非空的集合。那么AB=CDA=CB=D。,9,离散数学,证.):显然。)：（采用逻辑法）对任何的元素a,baAbB(a,b)AB(a,b)CD(条件：AB=CD）aCbD所以A=CB=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)(方

6、法一:采用逻辑法)对任何的元素a,b(a,b)A(BC)aAbBCaA(bBbC)(aAbB)(aAbC)(分配律：p(qr)(pq)(pr)(a,b)AB(a,b)AC(a,b)(AB)(AC)所以A(BC)=(AB)(AC)。,11,离散数学,(方法二:采用元素法)先证：A(BC)(AB)(AC)对任何的元素a,b，若(a,b)A(BC)，则aA，(且)bBC，从而aA，bB或bC。分情况讨论如下：(a)若bB，于是由aA，则有(a,b)AB，从而有(a,b)AB或(a,b)AC，故此(a,b)(AB)(AC);(b)若bC，于是由aA，则有(a,b)AC，从而有(a,b)AB或(a,b)

7、AC，故此(a,b)(AB)(AC);综合(a)、(b)总有(a,b)(AB)(AC)。所以A(BC)(AB)(AC)。次证：(AB)(AC)A(BC)对任何的元素a,b，若(a,b)(AB)(AC)，则(a,b)AB或(a,b)AC。分情况讨论如下：,12,离散数学,(a)若(a,b)AB，则有aA，bB，从而有aA，bB或bC，于是aA，bBC，故此有(a,b)A(BC);(b)若(a,b)AC，则有aA，bC，从而有aA，bB或bC，于是aA，bBC，故此有(a,b)A(BC);综合(a)、(b)总有(a,b)A(BC)。所以A(BC)(AB)(AC)。最后，由这两方面，根据包含关系的反

8、对称性可得A(BC)=(AB)(AC)。,13,离散数学,2.关系一.关系的基本概念定义1.二元关系(binaryrelation)设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是西安交通大学全体同学组成的集合。,14,离散数学,R=(a,b):aAbAa与b是同乡AA于是，R是西安交通大学同学之间的同乡关系。例2.设A是某一大家庭。R1=(a,b):aAbAa是b的父亲或母亲AAR2

9、=(a,b):aAbAa是b的哥哥或姐姐AAR3=(a,b):aAbAa是b的丈夫或妻子AA于是，R1是父母与儿女之间的关系，即父母子女关系；R2是兄弟姐妹之间的关系，即兄弟姊妹关系；R3是夫妻之间的关系，即夫妻关系。例3.设N是自然数集合。,15,离散数学,R=(a,b):aNbNa|bNN则R就是自然数集合上的整除关系。例4.设是整数集合。R=(a,b):aIbI(kI)(a-b=km)II则R就是整数集合上的(模m)同余关系。例5.设A是某一大型FORTRAN程序中诸程序块的集合。R=(a,b):aAbAa调用(call)bAA则R就是程序块集合上的调用关系。例6.设A=风，马，牛，R=

10、(风,马)，(马,牛)AA则R是A上的一个二元关系。,16,离散数学,关于关系概念，我们还有如下的几个定义和说明：1全关系(fullrelation)：关系R=AB称为全关系；2空关系(emptyrelation)：关系R=称为空关系；空关系和全关系都是平凡关系；3幺关系或单位关系(identicalrelation)：关系R=(a,a):aAAA称为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)也不是；,17,离

11、散数学,4关系的交，并，余运算：叉积是一种（新型的）集合；关系是叉积的子集；因此，关系也是一种（新型的）集合；从而，有关集合论的一切概念、论述、运算也都适合于关系；尤其是集合的交，并，余，差运算也都适合于关系；因此，关系也有交，并，余，差运算；例8.设N是自然数集合。R=小于关系=(m,n):mNnNmnNNS=整除关系=(m,n):mNnNm|nNN则R=R=大于等于关系()；RS=小于等于关系()；,18,离散数学,RS=不相等的整除关系()；RS=小于又不整除关系()；SR=相等关系(=)。5关系的扩充(expansion)：若R1R2，则称关系R2是关系R1的一个扩充；6n元关系：n元

12、关系R是n维叉积的一个子集；即RA1A2An,例若R1=(a,b),(a,c),R2=(a,b),(a,c),(c,c),则R1R2,19,定义3.前域(domain)后域(codomain)设A,B是两个非空集合，RAB是一关系。则关系R的前域：(R)=a:aA(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。二.关系的一些关联性质,离散数学,20,离散数学,定理1.设R1,R2AB是两个关系。若R1R2，则(1)保序性：(R1)(R2)

13、；(2)保序性：(R1)(R2)；证.只证(1)（采用逻辑法）对任何元素aA，a(R1)aA(bB)(aR1b)aA(bB)(a,b)R1)aA(bB)(a,b)R2)(条件：R1R2)aA(bB)(aR2b)a(R2)所以(R1)(R2)。,21,定理2.设R1,R2是AB上的两个二元关系。则(1)(R1R2)=(R1)(R2)(2)(R1R2)=(R1)(R2)(3)(R1R2)(R1)(R2)(4)(R1R2)(R1)(R2)证.只证(1)，(3)(1)先证：(R1)(R2)(R1R2)(采用包含法)由于R1R1R2，R2R1R2，依定理1，有(R1)(R1R2)，(R2)(R1R2)故

14、根据第一章2定理2的(3)，就可得(R1)(R2)(R1R2)。次证：(R1R2)(R1)(R2)(采用元素,离散数学,22,离散数学,法)对任何元素aA，若a(R1R2)，则存在bB，使得aR1R2b因此(a,b)R1R2，从而有(a,b)R1或者(a,b)R2于是a(R)或者a(R2)故此a(R1)(R2),23,离散数学,所以(R1R2)(R1)(R2)。(3)先证：(R1R2)(R1)(R2)(采用包含法)由于R1R2R1，R1R2R2，依定理1，有(R1R2)(R1)，(R1R2)(R2)故根据第一章2定理2的(3)，就可得(R1R2)(R1)(R2)。其次，反方向的包含不成立。且看

15、下面的反例。例9.设R1=(1,1),(2,2)，R2=(1,2),(2,1)。则，由于R1R2=，故(R1R2)=但是，由于(R1)=1,2，(R2)=1,2故(R1)(R2)=1,2,24,离散数学,所以(R1)(R2)(R1R2)。,25,离散数学,3.关系的表示关系的性质一.关系表示法1关系的矩阵表示法设关系RAB，这里A,B是两个非空的有限集合，A=a1,a2,a3,am，B=b1,b2,b3,bn。则我们可用一个mn阶01矩阵MR来表示关系R，我们称此矩阵MR为关系R的关系矩阵(relationmatrix)。MR=(xij)mn，其中1当（ai,bj)R时xij=(i=1,m；j

16、=1,n)0当（ai,bj)R时,26,离散数学,例1.设关系RAB，A=a1,a2,a3,a4，B=b1,b2,b3R=(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为(上面右矩阵),27,离散数学,2关系的图形表示法设关系RAB，这里A,B是两个非空的有限集合，A=a1,a2,a3,am，B=b1,b2,b3,bn

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

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

19、三种:集合表示法,矩阵表示法,图形表示法。,30,离散数学,二.关系的性质设二元关系RXX(或者说RX2)，这里X是一集合。则R称为是X上的1自反关系(reflexiverelation)：当且仅当R满足自反性：(xX)(xRx)；显然，对于自反关系R，(R)=(R)=X。反自反关系(irreflexiverelation)：当且仅当R满足反自反性：(xX)()或(xX)(xRx)；常见的自反关系有相等关系(=)，小于等于关系()，包含关系()等；而不相等关系()，小于关系()，真包含关系()等都不是自反关系，它们都是反自反关系。,31,离散数学,注：自反性和反自反性是关系的两个极端性质；因此

20、，自反关系和反自反关系是两种极端关系；从关系矩阵来看：自反关系关系矩阵的对角线上元素全是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),32,离散数学,是X上的反自反关系。注：由此

21、例可知幺关系一定是自反关系，但自反关系不一定是幺关系。2对称关系(symmetricrelation)：当且仅当R满足对称性：(xX)(yX)(xRyyRx)；3反对称关系(antisymmetricrelation)：当且仅当R满足反对称性：(xX)(yX)(xRyyRxx=y)；常见的对称关系有相等关系(=)，不相等关系()，同余关系，朋友关系，同学关系，同乡关系等；而小于等于关系()，包含关系()，上下级关系，父子关系等都不是对称关系，它们都是反对称关系。,33,离散数学,注：对称性和反对称性是关系的两个极端性质；因此，对称关系和反对称关系是两种极端关系；从关系矩阵来看：对称关系的关系矩

22、阵是对称矩阵。即xij=xji(1i,jn)；反对称关系的关系矩阵满足如下性质xij=1xji=0(1i,jn)；从关系图来看：对称关系关系图的结点间若有弧则都是双向弧；反对称关系关系图的结点间若有弧则都是单向弧；例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。,34,离散数学,例7.设X=a,b,c。则关系R1=(a,a),(a,b),(a,c),(c,b),(c,c)是X上的反对称关系；而关系R2=(a,a),(a,b),(a,c

23、),(b,a),(c,b)不是X上的反对称关系；因(a,b)R2且(b,a)R2,但ab。4传递关系(transitiverelation)：当且仅当R满足传递性：(xX)(yX)(zX)(xRyyRzxRz)；反传递关系(antisymmetricrelation)：当且仅当R满足反传递性：(xX)(yX)(zX)(xRyyRz)；常见的传递关系有相等关系(=)，小于等于关系()，包含关系()，整除关系，同余关系，上下级,35,离散数学,关系，同乡关系，后裔关系等；而不相等关系()，父子关系，朋友关系，同学关系等都不是传递关系。注：传递性和反传递性是关系的两个极端性质；因此，传递关系和反传递

24、关系是两种极端关系；概念反传递性和反传递关系一般不甚用，所以不加讨论；例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。,36,离散数学,例9.设X是平面上直线的集合。平行关系R=(x,y):xXyXxy由平面几何的知识知:若xy且yz，则xz。由传递关系的定义知R是X上的传递关系。例10.设X是平面上三角形的集合。相似关系R=(x,y):xXyXxy由平面几何的知识知:若xy

25、且yz，则xz。由传递关系的定义知R是X上的传递关系。例11.相等关系是自反的、对称的、反对称的、传递关系。全关系X2是自反的、对称的、传递的。幺关系I是自反的、对称的、反对称的、传递的。,37,离散数学,空关系是反自反的、对称的、反对称的、传递的。,38,离散数学,4.关系的运算1关系的逆运算定义1.逆运算(converseoperation)设A，B是两个非空的集合。我们称一元运算:2AB2BA对任何二元关系RAB，使得=(b,a):bBaAaRbBA为关系的逆运算；称是R的逆关系(converseofrelation)。显然，对任何(b,a)BA，baaRb；并且。,39,离散数学,例1

26、.设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.逆运算基本定理设两个关系RAB，SAB，这里A,B是两个非空的集合。则有(1)反身律：=R；(2)保序性：RS；R=S=；(3)分配律：RS=（逆对并的）；(4)分配律：RS=（逆对交的）；(5)XY=YX；,40,离散数学,(6)=；(7)交换律：(R)=()（逆与余的）；(8)分配律：RS=（逆对差的）；证.只证(1)，(4)，(7)（采用逻辑法）(1)对任何(a,b)AB，有(a,b)(b,a)(a,b)R所以=R。(4)对任何(a,b

27、)BA，有(a,b)RS(b,a)RS,41,离散数学,(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)=()。,42,离散数学,2关系的合成运算定义2.合成运算(compositionoperation)设A，B是两个非空的集合。我们称二元运算o:2AB2BC2AC对任何两个二元关系RAB，SBC，使得RoS=(a,c):aAcC(bB)(aRbbSc)AC为关系的合成运算；称RoS是R与S的合成关系。显然，对任何(a,c)AC，aRoSc(bB)(aRbbSc)。例2.

28、设A=a1,a2,a3，B=b1,b2，C=c1,c2,c3,c4关系RAB，SBCR=(a1,b1),(a2,b2),(a3,b1)S=(b1,c4),(b2,c2),(b2,c3),43,离散数学,于是，我们得到R与S的合成关系为RoS=(a1,c4),(a2,c2),(a2,c3),(a3,c4)其合成关系的关系图为例3.设A是老年男子的集合，B是中年男子的集合，C是青少年男子的集合。R是由A到B的父子关系，RAB,44,离散数学,S是由B到C的父子关系，SBC则复合关系RoS是A到C的祖孙关系。定理2.合成运算基本定理设R,R1,R2AB，S,S1,S2BC，TCD，这里A,B,C,D

29、是四个非空的集合。则(1)Ro=oS=；(2)(RoS)(R)；(RoS)(S)；(3)保序性：R1R2S1S2R1oS1R2oS2；(4)结合律：Ro(SoT)=(RoS)oT；(5)左分配律：Ro(S1S2)=(RoS1)(RoS2)；(合成运算对并的)右分配律：(S1S2)oT=(S1oT)(S2oT)；(合成运算对并的)(6)左分配不等式：Ro(S1S2)(RoS1)(RoS2)；,45,离散数学,(合成运算对交的)右分配不等式：(S1S2)oT(S1oT)(S2oT)；(合成运算对交的)(7)鞋袜律：(RoS)=SoR。证.只证(4)，(5)（采用逻辑法）(4)对任何元素aA,dD，

30、有aRo(SoT)d(bB)(aRbb(SoT)d)(bB)(aRb(cC)(bSccTd)(bB)(cC)(aRb(bSccTd)(量词前移：pxA(x)x(pA(x)(cC)(bB)(aRb(bSccTd)(量词交换：xyA(x,y)yxA(x,y),46,离散数学,(cC)(bB)(aRbbSc)cTd)(的结合律：p(qr)(pq)r)(cC)(bB)(aRbbSc)cTd)(量词后移：x(pA(x)pxA(x)(cC)(a(RoS)ccTd)a(RoS)oTd所以Ro(SoT)=(RoS)oT；(5)对任何元素aA,cC，有aRo(S1S2)c(bB)(aRbb(S1S2)c)(bB

31、)(aRb(bS1cbS2c)(bB)(aRbbS1c)(aRbbS2c)(对的分配律：p(qr)(pq)(pr),47,离散数学,(bB)(aRbbS1c)(bB)(aRbbS2c)(量词对的分配律：x(A(x)B(x)xA(x)xB(x)a(RoS1)ca(RoS2)ca(RoS1)(RoS2)c所以Ro(S1S2)=(RoS1)(RoS2)。但是合成运算不满足交换律。即，一般RoSSoR例4.设A=a,b,c,d,e。则关系R=(a,b),(c,d),(b,b)，S=(b,e),(c,a),(a,c),(d,b)的合成关系为,48,离散数学,RoS=(a,e),(b,e),(c,b)，S

32、oR=(a,d),(c,b),(d,b)所以RoSSoR。3关系矩阵的合成运算设RAB，SBC是两个二元关系，其合成关系为RoS。这里A=a1,a2,am，B=b1,b2,bl，C=c1,c2,cn。并设它们的关系矩阵分别为MR=(xij)ml，MS=(yij)ln，MRoS=(uij)mn则我们有：MRoS=MRoMS其中：我们令MRoMS=(tij)mntij=(xikykj)(1im,1jn),49,离散数学,注：这里关系矩阵的合成运算与线性代数中的一般矩阵的乘法运算颇为相似。所不同的是：乘法现在换成布尔乘()；加法现在换成布尔加()。值得注意的是：这里的布尔加11=1（不进位），而非1

33、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)的合成关系RoS=(a,e),(b,e),(c,b)其关系矩阵分别为MR=MS=MRoS=,50,离散数学,现在我们计算MRoMS=其中：t25=(x2kyk5)=(x21y15)(x22y25)(x23y35)(x24y45)(x25y55)=(00)(11)(00)(00)(00)=01000=1这说明MRoS=MRoMS。这个等式的证明省略。,51,离散数学,5.等价关系1等价关系和等价类定义1.等价关系(equivalencerelation)

34、设二元关系RAA。这里A是非空的集合。R是A上的等价关系R是自反的、对称的、传递的。显然(R)=(R)=A(因为等价关系是自反的)；例1.同乡关系是等价关系。例2.平面几何中的三角形间的相似关系是等价关系。例3.平面几何中的三角形间的全等关系是等价关系。,52,离散数学,例4.平面几何中的直线间的平行关系是等价关系。例5.设N是自然数集，m是一正整数，R=(a,b):aNbNab(modm)由等价关系的定义知R是N上等价关系；我们称R是N上的模m同余关系。例6.非空集合A上的幺关系、全关系都是等价关系。例7.非空集合A上的空关系不是等价关系(因为空关系不自反)。例8.设二元关系RAA,这里A=

35、a,b,c,R=(a,a),(b,b),(c,c),(b,c),(c,b)则R是A上的等价关系。其关系图如下,53,离散数学,等价关系的实质是将集合A中的元素进行分类。定义2.等价类(块)(equivalenceclasses(block)设R是非空集合A上的等价关系。对任何元素aA，由a生成的(或者说是由a诱导出的)关于R的等价类定义为b:bAbRa记为aR.(显然有aRA)。同时称a为等价类aR的代表元。,54,离散数学,定义3.设R是非空集合A上的等价关系。我们定义集合R=aR:aA(注意：应去掉重复的类！)为集合A关于等价关系R的商集。记为A/R。称A/R中元素的个数为R的秩。例9.设

36、N是自然数集，m是一个正整数。R是N上的模m同余关系，即R=(a,b):aNbNab(modm)。对于任何自然数a，bN，aRbab(modm)(kI)(a-b=km)；由等价关系的定义知R是N上的等价关系；对于任何自然数aN，以a为代表元的等价类aR=am=b:bNba(modm)；自然数集N关于等价关系R的商集,55,离散数学,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)。例10.例8中等价关系R的等价

37、类为aR=a,bR=cR=b,c；其商集为A/R=R=aR,bR=a,b,c；故其秩为2。,56,离散数学,定理1.设R是非空集合A上的等价关系。对任意的a,bA，有(1)aaR(故aR)；(2)aRb(即(a,b)R)aR=bR；(3)(3.1)aRbRaR=bR(aRb，即(a,b)R)；(3.2)(a,b)RaRbR=；(4)两个等价类aR和bR，要么完全重合(即aR=bR)，要么不交(即aRbR=)；二者必居其一，也只居其一。证.（采用逻辑法）(1)对任何元素a，有aAaRa(R是等价关系，故R自反),57,离散数学,aaRaR；(2)先证：aRbaR=bR为证aR=bR，须证(a)a

38、RbR对任何元素xA，有xaRxRaxRaaRb(已知条件：aRb)xRb(R是等价关系，故R传递)xbR所以aRbR,58,离散数学,(b)bRaR对任何元素xA，有xbRxRbxRbaRb(已知条件：aRb)xRbbRa(R是等价关系，故R对称)xRa(R是等价关系，故R传递)xaR所以bRaR综合(a)和(b)，即得bR=aR；次证：aR=bRaRbaR(本定理的(1)(x0A)(x0aR),59,离散数学,(x0A)(x0aRx0bR)(已知条件：aR=bR)(x0A)(x0Rax0Rb)(x0A)(aRx0x0Rb)(R是等价关系，故R对称)aRb(R是等价关系，故R传递且xpp)(

39、3)(3.1)aRbR(x0A)(x0aRbR)(x0A)(x0aRx0bR)(x0A)(x0Rax0Rb)(x0A)(aRx0x0Rb)(R是等价关系，故R对称)aRb(即(a,b)R)(R是等价关系，故R传递且xpp),60,离散数学,aR=bR(本定理的(2)；(3.2)(整体采用反证法)若(a,b)R，则aRbR=。否则若aRbRaR=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)(aRbR=)(本定理的(3.1)和(3.2)，互斥)。,61,离散

40、数学,定义4.设R和S是非空集合A上的两个等价关系。若RS，则我们称R细于S，或S粗于R。例11.设A是一非空集。则(1)A上最细的等价关系是幺关系；即R细=IA，A/R细=a:aA；(2)A上最粗的等价关系是全关系；即，R粗=AA，A/R粗=A。定理2.设R和S是非空集合A上的两个等价关系。则RS(aA)(aRaS)。证.（采用逻辑法）先证：RS(aA)(aRaS)对任何元素aA，有,62,离散数学,对任何元素xA，有xaRxRaxSa(已知条件：RS)xaS所以aRaS所以(aA)(aRaS)；次证：(aA)(aRaS)RS对任何序偶(a,b)AA(a,b)RaRbbRa(R是等价关系，故

41、R对称)baR,63,离散数学,baS(已知条件：(aA)(aRaS)bSaaSb(S是等价关系，故S对称)(a,b)S所以RS。定理3.设R和S是非空集合A上的两个等价关系。则R=S(aA)(aR=aS)。证.(采用逻辑法)R=SRSSR(aA)(aRaS)(aA)(aSaR)(定理2)(aA)(aRaSaSaR)(量词对的分配律：,64,离散数学,xA(x)xB(x)x(A(x)B(x)(aA)(aR=aS)。注：由定理2知，若两个等价关系相等，则每个元素所对应的等价类也相同；若两个等价关系的等价类集合相等，则两个等价关系相同。由定理3知，等价关系与等价类集合一一对应。即相同的等价关系对应

42、着相同的等价类集合，不同的等价关系对应着不同的等价类集合。2划分与等价关系定义5.覆盖划分(coveringpartition)设A是一非空集合。则A的(1)覆盖是一集合之集=A:A，满足条件：,65,离散数学,A；(2)划分是一集合之集=A:A，满足条件：(a)A=；(b)12A1A2=；其中A称为划分的划分块(blockofpartition)。注：由划分和覆盖的定义可知，A上的划分一定是A上的覆盖；反之则未必。定理4。设R是非空集合A上的等价关系。则R的等价类之集R=aR:aA是A上的一个划分；等价类就是划分块。证.定理1的(1)不但直接给出等价类的非空性，而且,66,离散数学,由它可得

43、等价类满足划分的条件(a)；定理1的(4)直接给出等价类满足划分的条件(b)(详细叙述留给学者)。注：定理4表明:由集合A上的等价关系R所产生的等价类之集构成集合A上的一个划分。定理5.设=A:A是非空集合A上的一个划分。我们借助来定义A上的二元关系RAA，使得R=(a,b):()(aAbA)则R是A上的等价关系。我们称为是由划分产生的(或者说是诱导出的)A上的等价关系。证.(采用逻辑法)(1)自反性：对任何元素a，有,67,离散数学,aAa(划分的条件(a)；A=)()(aA)()(aAaA)(幂等律：ppp)(a,a)RaRa所以R是自反的；(2)对称性：对任何元素a,bA，有aRb(a,

44、b)R()(aAbA)()(bAaA)(交换律：pqqp),68,离散数学,(b,a)RbRa所以R是对称的；(3)传递性：对任何元素a,b,cA，有aRbbRc(a,b)R(b,c)R(1)(aA1bA1)(2)(bA2cA2)()(aAbAbAcA)(由划分的条件(b)的逆否，有A1A2b1=2=)()(aAbAcA)(幂等律：ppp),69,离散数学,()(aAcA)(合取分析式：pqp)(a,c)RaRc所以R是传递的；所以R是等价的。注：定理5表明:由集合A上的划分可产生A上的一个等价关系；划分块就是等价类。定理6。设R是非空集合上的等价关系，是A上的一个划分。那么R=RR=。注：R

45、是由划分所产生的A上的一个等价关系；R是由等价关系R所产生A上的一个的划分；,70,离散数学,证.(采用逻辑法)先证：R=RR=对任何元素aA，有对任何元素xA，有xaRxRaxRa(已知条件：R=R)xaR所以aR=aR所以(aA)(aR=aR)所以R=aR:aA=aR:aA=；次证：R=R=R对任何序偶(a,b)AA(a,b)R,71,离散数学,aRbbRa(R是等价关系，故R对称)baRbaR(已知条件：R=(aA)(aR=aR)bRaaRb(R是等价关系，故R对称)(a,b)R所以R=R。注：由定理4,5,6可知：由等价关系可以产生一个划分，由划分可以产生一个等价关系；划分与等价关系是

46、一一对应的。即每个划分对应一个等价关系，且每个等价关系对应一个划分。,72,离散数学,6.半序关系定义1.半序关系(partialorderrelation)设二元关系RAA。这里A是非空的集合。R是A上的半序关系R是自反的、反对称的、传递的。显然(R)=(R)=A(因为半序关系是自反的)；通常，半序关系R记为，称系统(A,)为半序集(poset)。例1.自然数集N、整数集I、有理数集Q、实数集R上的小于等于关系都分别是这些数集上的半序关系；因为，对任何数a,b,caa；abbaa=b；abbcac；,73,离散数学,所以(N,),(I,),(Q,),(R,)都是半序集。例2.集合X的幂集2x

47、上的包含关系是其上的半序关系；因为对任何子集A,B,CAA；ABBAA=B；ABBCAC；故(2x,)是半序集。例3.自然数集N、整数集I、有理数集Q、实数集R上的小于关系都不是这些数集上的半序关系；因为，不是自反关系，即对任何数a,aa；故是反自反关系。注：一般我们定义：拟序(quasiorder)二元关系RAA(A)是A上的拟序关系R是反自反的、,74,离散数学,传递的。拟序一般记作，称系统(A,)为拟序集；拟序与半序的关系是：对任何元素a,bAababab；因此，小于关系是拟序；(N,),(I,),(Q,),(R,)都是拟序集。例4.集合X的幂集2x上的真包含关系不是其上的半序关系；因为

48、，不是自反关系，即对任何子集A,AA；故是反自反关系注：因此，真包含关系是拟序；(2x,)是拟序集。定义2.可比较性(comparability)设(A,)是一半序集，a与b是A中的一对元素。我们称a与b是可比较的abba。,75,离散数学,注：否则，若abba，则称a与b是不可比较的；半序关系实际上是在集合A上建立了一种比较关系；例5.对于小于等于关系，任何二数a,b都是可比较的；即总有abba。例6.对于包含关系，任何二集合A,B不都是可比较的；即不总是有ABBA。定义3.全序关系线性序链(totalorder,linearorder,chain)设(A,)是一半序集。是A上的全序关系满足

49、全可比较性：(aA)(bA)(abba)。这时，我们简称是全序或线性序；称(A,)是一全序集。,76,离散数学,注：否则，若(aA)(bA)(abba)，一般我们则称是非线性序(nonlinearorder)；非线性序在实际中有很重要的作用；也是本课程的一个重要研究对象。例7.小于等于关系是全序关系；包含关系一般不是全序关系。例8.(I,),(R,)都是全序集。但是在(I,)中每个整数，下一个比它大的或比它小的（即紧挨着它的）那个数都可确定；而在(R,)中却不可能。,77,离散数学,定义3.直接后继后继(directsuccessor,successor)设(A,)是一半序集，a与b是A中的一

50、对元素。我们称b是a的直接后继abab(tA)(attbt=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,)的每个元素都没有后继；每个元素都没有前驱。,78,离散数学,半序集的表示法哈斯图(Hasse)通常用Hasse图表示半序关

51、系。半序集(A,)的Hasse图是一个图G=(V,E)其中：V=A是结点集；E=(a,b):aAbAabb=a+是边集。在画法上,我们规定：(1)结点a+必须画在结点a的紧(斜)上方；(2)不画边的方向。注：与关系图相比，Hasse图省略了自反性的边(圈)；省略了(反对称性)方向；省略了传递性的边；例10.设A=a,b,c,79,离散数学,2A=,a,b,c,a,b,a,c,b,c,a,b,c由于2A上的包含关系是自反的、反对称的、传递的，故包含关系是2A上的半序关系，(2A,)是半序集。2A上的包含关系的Hasse图如上图所示。注：从上例可以看出：在非线性半序集中，直接后继一般不唯一；其Ha

52、sse图呈现网格状；其实正是这点导致一门现代数学的重要学科格论的出现；而此例正好给人们形象、直观的展现出布尔代数(用其三大特例之一集合代数来表现)的内部数学结构。例11.设A=2,3,4,6,7,8,12,36,60，R=(a,b):aAbAa|b，即，R是A上的整除关系。由整除的性质知R是自反的、反对称的、传递的。由半序关系的定义知R是A上的半序关系。,80,离散数学,R的Hasse图如下图左：例12.设A=2,3,6,12,24,36,R=(a,b):aAbAa|bR是A上的整除关系。由整除的性质知R是自反的、反对称的、传递的。由半序关系的定义知R是A上的半序关系。R的Hasse图如上图右：,81,离散数学,注：从以上两例可以看出：虽然同为整除关系，但由于集合不同，其Hasse图就呈现出明显的不同；这说明两例中的半序集是不同的；所以，在论及半序关系时，重要的是一定要指