《离散数学》课件：1-2-关系(简)

1、第二节第二节 关关 系系(relations)的基本概念及其性质的基本概念及其性质 1.2.2等价关系等价关系 1.2.3部分序关系部分序关系1.2.1 关系的基本概念及其性质关系的基本概念及其性质定义定义1.2.1 设设A1, ,A2, , ,An是是n个集合，个集合， 集合集合A1 A2 An的一个子集的一个子集F称为称为A1, ,A2, , ,An上的一个上的一个n元关系。特别地，集合元关系。特别地，集合A B中的一中的一个子集个子集R，称为集合，称为集合A与与B上的一个二元关系上的一个二元关系( (binary relationbinary relation) )，简称为关系。，简称为

2、关系。对于对于x A，y B，若，若(x, ,y) R则称则称x，y有关系有关系R，记为，记为xRy；若；若(x, ,y) R，则称，则称x，y没有关系没有关系R，记为，记为xRy。若若B=A，则，则R称为称为A上的二元关系。上的二元关系。 关系的特点关系的特点1.A A上的任一子集都是上的任一子集都是A上的一个关系；上的一个关系；2.若若A=n，则，则A上的关系有上的关系有 个。个。3.A上的三个特殊关系，即空关系上的三个特殊关系，即空关系 ；全域关系全域关系EA=A A；相等关系相等关系IA=(x,x) x A。4. 5.有序偶有序偶(a,b)=(c,d)的充要条件是的充要条件是a=c，b

3、=d。22nRAARERA例例设设A=a,b,c,d,e,f为学生集合，为学生集合，B= , , , 为选修课程集合，为选修课程集合，C=2,3,4,5为学习成绩为学习成绩集合，学生与课程之间存在着一种关系即集合，学生与课程之间存在着一种关系即“选修关系选修关系”；学生、课程和成绩之间也；学生、课程和成绩之间也存在着一种叫做存在着一种叫做“学习成绩关系学习成绩关系”。设用。设用R表示选修关系，表示选修关系，S表示学习成绩关系，那表示学习成绩关系，那么么R为为A与与B上的二元关系，上的二元关系，S为为A，B和和C上的三元关系。上的三元关系。 R=(a, ),(a, ),(b, ),(b, ),(

4、c, ),(c, ),(e, ),(f, )表示学生表示学生a选修课程选修课程 ， ；学生；学生b选修课程选修课程 ， ；学生；学生c选修课程选修课程 ， ；学生；学生e 选修课选修课程程 ；学生；学生f选修课程选修课程 ；而学生；而学生d没有选修没有选修任何课程。任何课程。S=(a, ,5), (a, ,5), (b, , 3), (c, ,4), (f, ,2)表示学生表示学生a所选的两门课程成绩都是所选的两门课程成绩都是5分；分；学生学生b所选所选 课程的成绩是课程的成绩是3分；学生分；学生c所选所选 课程的成绩是课程的成绩是4分；学生分；学生f所选所选 课程的成绩课程的成绩是是2分。分

5、。 关系是集合，因此集合的方法对关系都关系是集合，因此集合的方法对关系都是有效的。因而有子关系，关系的并、交、是有效的。因而有子关系，关系的并、交、差、余等运算。差、余等运算。v例：例：R，S是集合是集合A上的两个关系，若上的两个关系，若R S，则称，则称R为为S的子关系；的子关系；对任意对任意x，y A，有，有 x(RS)y当且仅当当且仅当xRy或者或者xSy x(R S)y当且仅当当且仅当xRy并且并且xSy x(R-S)y当且仅当当且仅当xRy并且并且xSy x y当且仅当当且仅当xR yR定义定义1.2.2 逆关系逆关系(inverse relation)设设R是集合是集合A上的一个关

6、系。上的一个关系。令令R-1 =(y, x) x A, y A, 并且有并且有xRy，则称关系，则称关系R-1为关系为关系R的逆。的逆。例如，小于关系的逆关系是大于关系，大于关例如，小于关系的逆关系是大于关系，大于关系的逆关系是小于关系，相等关系的逆关系仍系的逆关系是小于关系，相等关系的逆关系仍是相等关系。是相等关系。 例：例：R=(a,b),(b,c),(a,c),(b,d),则则R-1 = (b,a),(c,b),(c,a),(d,b)定义定义1.2.3 自反自反关系关系(reflexive)v集合集合A 上的关系上的关系R称为是自反的称为是自反的(反身的反身的)，如果对如果对每一个每一个

7、x A，都有，都有xRx。 v例：例：A=a, b, c, A 上的关系上的关系R1=(a,b),(b,b),(b,c) R2=(a,a),(a,b),(b,b),(b,c),(c,c)vR是自反的是自反的当且仅当当且仅当IA R，R是自反的是自反的当且仅当当且仅当R-1是自反的是自反的 。定义定义1.2.4 反自反反自反关系关系(irreflexive)v集合集合A上的关系上的关系R称为反自反的，如果对称为反自反的，如果对任意的任意的x A，xRx均不成立。或者说对任均不成立。或者说对任意的意的x A，都有，都有xRx。v例：例：A=a, b, c, A上的关系上的关系R1=(a,b),(b

8、,b),(b,c) R2=(a,b),(b,c),(a,c)v显然，显然，R是反自反的当且仅当是反自反的当且仅当 IAR= 。 讨论：讨论：是否存在既具有自反性，又具有反自反是否存在既具有自反性，又具有反自反性的关系？性的关系？是否存在既不具有自反性，又不具有反是否存在既不具有自反性，又不具有反自反性的关系？自反性的关系？空关系空关系 、全域关系、全域关系EA、相等关系、相等关系IA是否是否具有自反性，或反自反性？具有自反性，或反自反性？定义定义1.2.4 对称对称关系关系(symmetric)v集合集合A上的关系上的关系R称为对称的，如果称为对称的，如果xRy，则则yRx。其中。其中x A，

9、y A。 v例：例：A=a, b, c, A上的关系上的关系R1=(a,a),(a,b),(b,a),(b,c) R2=(a,a),(b,b),(c,b),(b,c),(a,c),(c,a)vR是对称的是对称的当且仅当当且仅当R-1=R 。定义定义1.2.4反对称反对称关系关系(antisymmetric)v集合集合A上的关系上的关系R称为是反对称的，如果称为是反对称的，如果xRy，yRx，则必有，则必有x=y ；或者说，如果；或者说，如果xRy且且x y ，则必有则必有yRx。v例：例：A=a, b, c, A上的关系上的关系R1=(a,a),(a,b),(b,c) R2=(a,a),(b,

10、b),(c,b),(b,c),(c,a)vR是反对称的是反对称的当且仅当当且仅当RR-1 IA 。讨论：讨论：是否存在既具有是否存在既具有对称对称性，又具有性，又具有反对称反对称性的关系？性的关系？是否存在既不具有是否存在既不具有对称对称性，又不具有反性，又不具有反对称对称性的关系？性的关系？空关系空关系 、全域关系、全域关系EA、相等关系、相等关系IA是否是否具有具有对称对称性，或反性，或反对称对称性？性？定义定义1.2.4 传递传递关系关系(transitive)v集合集合A上的关系上的关系R称为是传递的，如果称为是传递的，如果xRy，yRz，则，则xRz。 其中其中x A，y A，z A

11、。 v例：例：A=a, b, c, A上的关系上的关系R1=(a,a),(a,b),(b,c),(a,c) ， R2=(a,b),(a,c), R3=(a,a),(c,b),(b,c),(c,a)数的相等关系、大于关系、小于关系都数的相等关系、大于关系、小于关系都具有传递性。具有传递性。定义定义1.2.4 关系的乘积关系的乘积(composite)v设设R，S是集合是集合A上的两个关系，令上的两个关系，令RS=(x, y)x A, y A且存在一个且存在一个z A使得使得xRz，zSy。称关系。称关系RS为关系为关系R和和S的乘积的乘积或合成或合成(composite) 。 v例：兄弟关系和父

12、子关系的乘积是叔侄例：兄弟关系和父子关系的乘积是叔侄关系，而姐妹关系和母子关系的乘积是姨关系，而姐妹关系和母子关系的乘积是姨与外甥关系。与外甥关系。 例：例：vA=a, b, c, d, A上的关系上的关系 R和和S ，R=(a, a),(b,a),(c,d)，S= (a,c),(a,d),(b,c),(c,b)，则则RS = (a,c),(a,d),(b,c),(b,d)SR = (a,d), (b,d),(c,a)v显然，显然，RS SR，关系的乘法不满足交，关系的乘法不满足交换率。换率。关系的乘法满足结合率关系的乘法满足结合率v设设R，S和和T是集合是集合A上的三个关系，证明：上的三个关

13、系，证明： (RS)T= R(ST)。v分析：因为关系的乘积仍是集合，要证分析：因为关系的乘积仍是集合，要证明集合相等，就要证明集合互为包含，我明集合相等，就要证明集合互为包含，我们首先证明们首先证明(RS)T R(ST)，再证明，再证明R(ST) ( RS)T 。证明证明(RS)T R(ST)v任取任取(x, y) (RS)T，即，即x(RS)Ty，由关，由关系乘积的定义知，存在系乘积的定义知，存在z A使得使得x(RS)z，zTy，同样对，同样对x(RS)z，必存在，必存在zA使得使得xRz ，z Sz。故由。故由z Sz 和和zTy知知z (ST)y，再有再有xRz 得得xR(ST)y，

14、即，即(x, y) R(ST), 从而证得了从而证得了(RS)T R(ST) 证明证明R(ST) (RS)T v任取任取(x, y) R(ST), 即即xR(ST)y，由关，由关系乘积的定义知，存在系乘积的定义知，存在z A使得使得xRz，z(ST)y，同样对，同样对z(ST)y，必存在，必存在zA使得使得zSz ，z Ty 。故由。故由xRz和和zSz 知知x(RS)z ，再有再有z Ty，得，得x(RS)Ty ，即，即(x,y) (RS)T，从而证得了从而证得了R(ST) (RS)T。v因此，因此， (RS)T=R(ST)得证。得证。v对对A上任意的关系上任意的关系R，有，有RIA= IA

15、 R= Rv由于关系的乘法运算满足结合律，因此由于关系的乘法运算满足结合律，因此我们可以用我们可以用“幂幂”表示集合表示集合A上同一个关上同一个关系的乘积，即系的乘积，即 规定，规定，R0=IA。nnRRRR综合思考题设A表示工人的集合,B表示工作的集合. R1 表示A到B的二元关系,R1=(a,b)aA,bB, a分配去做工作b.设R2表示A到A的二元关系,R2=(a1,a2)a1,a2A,a1和a2不能友好相处.请你用R1和R2表示关系 R,使得xRy表示 x,y分配去做同样工作且能友好相处.v因为因为R1是是A到B的二元关系,故R1-1表示B到A的二元关系, 则R1R1-1表示从A到A的

16、二元关系,即由分配做同一样工作的两个人构成的序偶的全体.因此R=R1R1-1-R2定理定理1.2.1 v设设R是是A上的关系，上的关系，m，n为任意的自然为任意的自然数，那么，数，那么，(1) RmRn=Rm+n；(2) (Rm)n=Rmn。 v证明：证明：(1)任给任给m，对，对n作归纳法。作归纳法。n=0时时，Rm R0=Rm IA= Rm = Rm+0。假设假设Rm Rn=Rm+n，那么，那么RmRn+1=Rm(RnR1)= (RmRn )R1= Rm+nR1= Rm+n+1= Rm+(n+1) 。 (2)任给任给m，对，对n作归纳法。作归纳法。n=0时时，(Rm)0=IA= R0 =

17、Rm 0。假设假设( (Rm)n=Rmn。那么那么( (Rm)n+1= ( (Rm)n Rm = Rmn Rm= Rmn+m= Rm(n+1) 。定理定理1.2.2 v设集合设集合A的元素数为的元素数为n，R是是A上二元关系，上二元关系，那么存在自然数那么存在自然数i，j(0 i j )使得使得Ri=Rj。v证明：证明：由关系的特点知道，若由关系的特点知道，若 A =n，则，则A上的关系有上的关系有 个，因此，在个，因此，在 R0，R1，R2，这，这 +1个关系中，至少有两个个关系中，至少有两个是相同的（鸽巢原理），即有是相同的（鸽巢原理），即有i, ,j(0 i j )使得使得Ri=Rj。

18、22n22n22n22n定理定理1.2.3 v设设R是集合是集合A上的关系，若存在自然数上的关系，若存在自然数i，j(i j)，使得，使得Ri=Rj，则有，则有 (1)Ri+k=Rj+k，k N；(2)Ri+kp+m=Ri+m，其中，其中k，m N，p=j-i。 v证明：证明： (1) Ri+k= Ri Rk =Rj Rk =Rj+k；证明证明(2)mimjmi)-(jimi)-2)(j-(kimi)-2)(j-(kjmi)-2)(j-(ki)- j (imi)-1)(j-(kimi)-1)(j-(kjmi)-1)(j-(ki)- j (imkpiRRRRRRRRRR根据(1)根据(1)根据(

19、1)定理定理1.2.4 v集合集合A上的关系上的关系R具有传递性的充要条件具有传递性的充要条件是是R2 R。v证明：证明：必要性必要性。若。若R具有传递性，任取具有传递性，任取(x,y) R2，于是存在，于是存在z A，使得，使得xRz，zRy，因为因为R是传递的，所以有是传递的，所以有xRy，即，即(x,y) R,故故R2 R。充分性充分性。如果。如果xRy，yRz，则，则xR2z。因为因为R2 R，故，故xRz。所以具有传递性的。所以具有传递性的。 v二元关系的表示方法二元关系的表示方法v1列举法列举法:列出关系列出关系R中的所有序偶中的所有序偶;v2关系矩阵关系矩阵;给定两个有限给定两个

20、有限 集合集合A=a1,a2,B=b1,b2,R为为A到到B的一个二元关系的一个二元关系,则则可以用下列关系矩阵可以用下列关系矩阵MR=rijm n来表示来表示R:v r11 r12 r1n v MR= r21 r22 r2nv ： ： ：v rm1 rm2 rmnv其中其中rij=1,若若(ai,bj) R;否则否则rij=0,若若(ai,bj) Rv关系的矩阵表示与矩阵的行列对应的集合关系的矩阵表示与矩阵的行列对应的集合A和和B上的元素顺序上的元素顺序是相关的是相关的,不同的排序会得到不同的关系矩阵不同的排序会得到不同的关系矩阵.v二元关系的表示方法二元关系的表示方法v3关系图关系图:给定

21、两个有限集合给定两个有限集合A=a1,a2, am,B=b1,b2,bn,R为为A到到B的一个二元关系的一个二元关系. 首先在平面上作首先在平面上作m个结点代表个结点代表a1,a2, am,然然后作另外后作另外n结点代表结点代表b1,b2,bn.如果如果aiRbj,则画则画一条从一条从ai到到 bj的有向弧的有向弧,这样的图称为这样的图称为R的关的关系图系图.v关系的性质总结关系的性质总结自反的自反的反自反的反自反的对称的对称的反对称的反对称的传递的传递的定义定义任取任取 a A有有(a,a) R任取任取 a A有有(a,a) R若若(a,b) R,则则(b,a) R若若(a,b) R,(b,

22、a) R, 则则 a=b若若(a,b) R且且(b,c) R, 则则(a,c) R 集合集合IA RIAR= R-1=RRR-1 IAR2 R关系关系图图图中每图中每个结点个结点都有自都有自回路回路图中每个图中每个结点都无结点都无自回路自回路任意两个任意两个结点间要结点间要么没有弧么没有弧,要么有一要么有一对方向相对方向相反的弧反的弧任意两结任意两结点间至多点间至多有一条弧有一条弧若若a到到b有有弧弧,b到到c有弧有弧,则则a到到 c有弧有弧关系关系矩阵矩阵主对角主对角线上全线上全为为1主对角线主对角线上全为上全为0对称矩阵对称矩阵反对称矩反对称矩阵阵_定义定义1.2.9 关系的闭包关系的闭包

23、(closure)v设设A是非空集合，是非空集合，R是是A上的二元关系。上的二元关系。称称R 是是R的自反闭包的自反闭包(对称闭包，传递闭对称闭包，传递闭包包)，如果，如果R 满足：满足：（1）R 是自反的是自反的(对称的，传递的对称的，传递的)；（2）R R ；（3）对）对A上任意关系上任意关系R ， 若若R R ，且，且R 是是自反的自反的( (对称的，传递的对称的，传递的) )，必有，必有RR 。 R 的自反闭包、对称闭包和传递闭包的自反闭包、对称闭包和传递闭包分别记为分别记为r(R)，s(R)，t(R) ，也称也称r，s，t为闭包运算为闭包运算，它们作用于关系它们作用于关系R后，产生包

24、含后，产生包含R的最小的自反、对称、的最小的自反、对称、传递的关系。传递的关系。 定理定理1.2.5 v设设R是集合是集合A上的关系，那么，上的关系，那么，(1) r(R)=IAR；(2) s(R)=RR-1；(3) t(R)= 1iiR（1 1）证明）证明 r(R)=IAR因为因为IA IAR，所以，所以IAR具有自反性；具有自反性；显然，显然，R IAR 对对A上任意关系上任意关系R ， 若若R R ，且，且R 是是自反的，往证自反的，往证IAR R 。因为。因为R 是是自反自反的，所以的，所以IA R ，又，又R R ，所以所以IAR R 。 （2 2）证明）证明 s(R)=RR-1 任

25、取任取(x,y) RR-1 ，则，则(x,y) R或或(x,y) R-1 ，若，若(x,y) R，则有，则有(y,x) R-1，所以所以(y,x) RR-1；若；若(x,y) R-1 ，则有，则有(y,x) R，所以，所以(y,x) RR-1 ， RR-1具有具有对称性；对称性； 显然显然，R RR-1 对对A上任意关系上任意关系R ， 若若R R ，且，且R 是是对称的，往证对称的，往证RR-1 R 。 任取任取(x,y) RR-1 ，则，则(x,y) R或或(x,y) R-1 ，若若(x,y) R，因为，因为R R ，则则(x,y) R ；若若(x,y) R-1 ，则有，则有(y,x) R

26、，则，则(y,x) R ，因为因为R 是是对称的，所以对称的，所以(x,y) R ， 因此，因此，RR-1 R 。 （3 3）证明）证明 t(R)=1iiR对于任意对于任意x,y,z A，若，若(x,y)(x,y) ， (y,z)(y,z) , 则存在自然数则存在自然数j, k，使得，使得(x,y)(x,y) Rj，(y,z)(y,z) Rk ，故，故(x,z)(x,z) Rj Rk = Rj+k，从而从而(x，z) ，所以，所以， 具有具有传递性；传递性；显然，显然，R 1iiR1iiR1iiR1iiR1iiR对对A上任意关系上任意关系R ， 若若R R ，且，且R 是是传递的，往证传递的，

27、往证 R 。为此只要证对任为此只要证对任意正整数意正整数n，Rn R 。对。对n采用归纳法，采用归纳法，n=1时，显然有时，显然有R1 R 。假设。假设n=k时有时有Rk R ，任取，任取(x, y) Rk+1，那么有，那么有z使使(x, ,z) Rk，(z,y) R。根据归纳假设及题设，。根据归纳假设及题设，有有(x, ,z) R ，(z, ,y) R 。又。又R 是传递的，是传递的，故故(x,y) R ，所以，所以Rk+1 R ；因此，因此， R 。证毕。证毕。 1iiR1iiRv设设R是有穷集合是有穷集合A上的关系，上的关系，|A|=n，则则 t(R)=n1iiR推论推论1.2.2等价关

28、系等价关系(equivalence relation) 定义定义1.2.10设设A是一个是一个非空非空集合，集合，R是是A上二元关系。如果上二元关系。如果R具有自反性，对称性，具有自反性，对称性，传递性，则称传递性，则称R是一个等价关系。是一个等价关系。 通常，通常，用用“ ”表示表示等价关系。等价关系。 例：整数的同余关系，例：整数的同余关系，几何图形的面积几何图形的面积相等关系，人群中的同姓关系、相等关系，人群中的同姓关系、同龄关同龄关系等。系等。定义定义1.2.11 等价类等价类(equivalence class)v设设A是一个是一个非空非空集合，集合，R是是A上的等价关上的等价关系。

29、系。A的一个的一个非空子集非空子集M叫做叫做A关于关于R的一的一个等价类，如果个等价类，如果1）若）若a M，b M，则，则a R b。2）若）若a M，b M，则，则a R b；或者；或者, 若若a M，a R b，则，则b M。v通常，用通常，用aR表示包含元素表示包含元素a的等价类，的等价类，则则 aR=x|(x,a) R ,a称为该称为该等价类等价类代表元代表元。例：例：设集合设集合A=1,2,3,10，R是模是模3同余关系，同余关系，则则3R=6R=9R=3,6,9, 1R= 4R= 7R= 10R=1,4,7,10 , 2R= 5R= 8R= 2, 5, 8都是等价类。都是等价类。

30、设设A是本教室中的所有人集合，是本教室中的所有人集合，在同姓关在同姓关系下，则系下，则本教室中本教室中所有姓所有姓“张张”的人构成的人构成的集合是一个的集合是一个等价类等价类,所有姓所有姓“王王”的人构的人构成的集合是一个成的集合是一个等价类等价类, 。定理定理1.2.6 v设设 是集合是集合A上的等价关系，于是等价类是存上的等价关系，于是等价类是存在的。在的。 v证明证明: (1)任取任取a A，令，令M x|x A并且并且x a ，显然，显然，M非空。非空。(2)任取任取x1 M，x2 M，根据，根据M的定义，则有的定义，则有x1 a，x2 a，而，而 具有对称性，传递性，所以具有对称性，

31、传递性，所以x1 x2。 (3)任取任取x1 M，若，若x1 y，则，则x1 a，而，而 具有对称具有对称性，传递性，所以性，传递性，所以y a，故，故y M。因此，因此，M是一个等价类。是一个等价类。 定理定理1.2.7 v设设 是集合是集合A上的等价关系上的等价关系，M1, M2 , ，是是A中关于中关于 的的所有等价类。于是所有等价类。于是AM1 M2 并且并且MiMj= (i j)，亦即，集合亦即，集合A上的等上的等价关系把价关系把A分成了互不相交的等价类分成了互不相交的等价类。 证明：证明： v任取任取Mi，Mj，i j。假设。假设MiMj ，则，则必存在必存在x MiMj，则任取，

32、则任取a Mi，b Mj，都有都有a x，b x，所以，所以a b, 故故Mi Mj，矛盾。，矛盾。v任取任取a A， 令令M x x A并且并且x a ，由由定理定理1.2.6知，知，M是等价类，故有是等价类，故有k，使得，使得MMk，因为，因为a M，所以，所以，a M1M2Mk。显然有。显然有M1 M2 A。故故AM1 M2 。 定义定义1.2.12 划分划分(partition)v称集合称集合A的子集族的子集族C为为A的划分，如果：的划分，如果：（1）若）若B C，则，则B；（2） ；（3）对任意的）对任意的B，BC，若，若B B ，则，则BB = 。称称C中元素为划分的单元，或划分块

33、。中元素为划分的单元，或划分块。v规定规定，A= 时只有划分时只有划分 ，ABCB例：例：v设设A=1,2,3,4,5,6,7,8,9,10，vC1=1,2,3,4,5,6,7,8,9,10vC2=1,3,2,4,5,6,7,8,9,10vC3=1,4,7,10,2,5,8,3,6,9定义定义1.2.13 商集商集(quotient set)v设设R是非空集合是非空集合A上的等价关系，以上的等价关系，以R的的所有不同等价类为元素作成的集合称为所有不同等价类为元素作成的集合称为A的商集，简称的商集，简称A的商集，记作的商集，记作A/R。 vA/R恰是集合的一个划分。恰是集合的一个划分。v设集合设

34、集合A=1,2,3,10，R是模是模3同余关同余关系，则系，则A/R 1R，2R ，3R，这里，这里 1R=1,4,7,10, 2R= 2, 5, 8, 3R=3,6,9 例例1.2.3 v设设A=a1,a2, , an，n 1。 (1)验证验证EA，IA，Rij=IA(ai，aj)，(aj，ai)都是都是A上的等价关系，并求它们对应的上的等价关系，并求它们对应的商集，其中商集，其中ai，aj A，且，且i j。 是是A上的等上的等价关系吗？价关系吗？ (2)A=a,b,c，试求出，试求出A上的全体等价关系上的全体等价关系及其对应的商集。及其对应的商集。解解 v(1)EA，IA，Rij是等价关

35、系是等价关系(证明略证明略)。A/IA=a1,a2,an；A/EA=a1,a2,an；A/Rij=ai,aj,ak1,ak2,akn-2，其中，其中k1,k2,kn-2均不等于均不等于i或或j，共有，共有C2n个。个。 因为无自反性，所以不是因为无自反性，所以不是A上的等价关系。上的等价关系。 v(2)按按(1)中中n=3的情况，的情况，A=a,b,c上有上有5种种不同的等价关系：不同的等价关系：EA，其商集为，其商集为A/EA=a,b,c；IA，其商集为，其商集为A/IA=a,b,c；R12=IA(a,b),(b,a)，A/R12=a,b,c；R13=IA(a,c),(c,a)，A/R13=

36、a,c,b；R23=IA(b,c),(c,b)，A/R23=b,c,a； 定理定理1.2.8 v设设A为一个非空集合。为一个非空集合。(1)设设R为为A上的任意一个等价关系，上的任意一个等价关系，则对应则对应R的商集的商集A/R为为A的一个划分。的一个划分。(2)设设C为为A的任一个划分，令的任一个划分，令RC=(x, ,y)|x, ,y A并且并且x, y属于属于C的同一划的同一划分块分块，则，则RC为为A上的等价关系。上的等价关系。 (1)证明：证明：A/R是是A的一个划分的一个划分设商集设商集A/R M1, M2 , ，则，则i (i=1,2, )是是A关于关于R的的等价类，根据等价等价

37、类，根据等价类的定义知，类的定义知，i (i=1,2,3, );又根据又根据定定理理1.2.7知，知，AM1 M2 ，并，并且且MiMj= (i j) ，所以，所以，A/R是是A的一个划的一个划分。分。(2)证明：证明：RC为为A上的等价关系上的等价关系自反性；自反性；对任意的对任意的x A，有，有x和和x属于属于C的同一划分块，所以的同一划分块，所以(x,x)(x,x) RC，则，则RC 具具有自反性；有自反性；对称性；对称性；对任意对任意的的x,y A，若，若(x, y) RC，即即x,y属于属于C的同一划分块，亦即的同一划分块，亦即y, x 属于属于C的同一划分块，所以的同一划分块，所以

38、(y,x)(y,x) RC，则，则RC 具有对称性；具有对称性；(2)证明：证明：RC为为A上的等价关系上的等价关系传递性传递性；对任意的；对任意的x, y, z A，若若(x, y) RC， (y, z) RC，即，即x与与y属于同一属于同一划分块，划分块，y与与z属于同一划分块，则属于同一划分块，则x与与z也也属于同一划分块，所以属于同一划分块，所以(x,z)(x,z) RC，则，则RC 具有传递性；具有传递性；因此，因此， RC为为A上的等价关系。证毕。上的等价关系。证毕。第二类第二类Stirling数数 v将将n个不同的球放入个不同的球放入r个相同的盒中去，并且要个相同的盒中去，并且要

39、求无空盒，有多少种不同的放法？这里要求求无空盒，有多少种不同的放法？这里要求n r。v不同的放球方法数即为不同的放球方法数即为n元集合元集合A的不同的划的不同的划分数，分数， v设设 表示将表示将n个不同的球放入个不同的球放入r个相同的盒中个相同的盒中的方案数，称的方案数，称 为第二类为第二类Stirling数数 。rnrn第二类第二类Stirling数数的性质的性质1,1, 122, 11, 0021nnCnnnnnnnv(1) 111rnrnrrnv(2)满足如下的递推公式满足如下的递推公式: : 例例1.2.4 v集合集合A=a，b，c，d上有多少不同的等上有多少不同的等价关系？价关系？

40、v解：不同的划分个数为解：不同的划分个数为: :不同的等价关系个数等于不同的划分个数，不同的等价关系个数等于不同的划分个数，所以不同的等价关系个数为所以不同的等价关系个数为1515。151121443424142414C定义定义1.2.14 加细加细v设设C和和C 都是集合都是集合A的划分，若的划分，若C的每个的每个划分块都含于划分块都含于C 的某个划分块中，则称的某个划分块中，则称C是是C 的加细。的加细。v例：设例：设A=1,2,3,4,5,6,7,8,9,10，vC1=1,2,3,4,5,6,7,8,9,10vC2=1,3,2,4,5,6,7,8,9,10vC3=1,4,7,10,2,5

41、,8,3,6,9C是是C 的加细当且仅当的加细当且仅当RC RC v例：例：v设设A=x|x是吉大计算机学院的是吉大计算机学院的07级本科级本科生生，vC=0701班的学生班的学生，0502班的学生班的学生，0703班的学生班的学生, vC =大一的学生大一的学生, 大二的学生大二的学生,大三的学生大三的学生, 大四的学生大四的学生 vC对应的等价关系对应的等价关系RC是同班关系，是同班关系，vC 对应的等价关系对应的等价关系RC 是同年级关系。是同年级关系。例例1.2.5 v设设A=a，b，c，找出，找出A的全部划分及对的全部划分及对应的等价关系，以及划分间的加细和关系应的等价关系，以及划分

42、间的加细和关系中的包含关系。中的包含关系。v解解: 由第二类由第二类Stirling数易知，数易知，A上共有上共有 个划分。个划分。5112133231313v这些划分分别为：这些划分分别为：C1=a,b,c，C2=a,b,c，C3=b,a,c，C4=c,a,b，C5=a,b,c。 v它们对应的等价关系分别为它们对应的等价关系分别为:RC1=EA，RC2=IA(b, c), (c, b)，RC3= IA(a, c), (c, a)，RC4= IA(a, b), (b, a)，RC5=IA。vC2， C3， C4，C5都是都是C1的加细，的加细，RC2，RC3，RC4，RC5都是都是RC1的子集

43、。的子集。 1.2.2部分序关系部分序关系(partial ordering) v定义定义1.2.15 设设R是集合是集合A上的一个关系。如上的一个关系。如果果R具有自反性，反对称性，传递性，则具有自反性，反对称性，传递性，则称称R为一个部分序关系为一个部分序关系(半序关系、偏序关半序关系、偏序关系系)。集合。集合A在部分序关系在部分序关系R下做成一个部下做成一个部分序集分序集(半序集、偏序集半序集、偏序集)。记作记作(A，R) 。v通常，将部分序关系通常，将部分序关系R写做写做“”，读做，读做“小于或等于小于或等于”。 v 显然，一个部分序集的子集仍为部分序集。显然，一个部分序集的子集仍为部

44、分序集。 例例 v设设A是整数集合，是整数集合， R是小于等于是小于等于关系关系(或大或大于等于关系于等于关系)。v设设A是自然数集合，是自然数集合，R是整除关系。是整除关系。v设设A是一个集合族，是一个集合族，R是是“ ”关系。则关系。则(A,R)是一个部分序集；是一个部分序集；哈斯哈斯图图 (Hasse diagram)v以平面上的点代表部分序集中的元素。以平面上的点代表部分序集中的元素。1）若若xy，且，且xy，则将，则将x画在画在y的下面。的下面。2）若若xy，xy，并且没有不同于，并且没有不同于x，y的的z，使得，使得xzy(称称y盖住盖住x)，则在，则在x，y之间用直线连结。之间用

45、直线连结。 例例:v设设Aa , b , a,b , a,b, c , a,b, c,d , a,b,c,e， 则则(A, ) 是一是一个部分序集。个部分序集。 a b a,b a,b,c a,b,c,d a,b,c,e 例例:v设设A 1,2,3, 4,5,6,8,10,12,24 ，R是整除关是整除关系，则系，则(A, R) 是一个部分序是一个部分序集。集。3152641210824定义定义 链链(chain)v设设(A, )是一个部分序集，对任意是一个部分序集，对任意x, y A，如果如果xy，或，或yx，称，称x与与y可比可比(comparable) ；否则，称；否则，称x与与y不可比

46、。不可比。v一个部分序集的子集，其中任意两个元素一个部分序集的子集，其中任意两个元素都可比，称该子集为一条链都可比，称该子集为一条链(chain)。例例:v设设A 1,2,3, 4,5,6,8,10,12,24 ，R是整除关是整除关系，则系，则(A, R) 是一个部分序是一个部分序集。集。3152641210824定义定义1.2.16 全序集全序集( (totally ordered set) )v一个部分序集一个部分序集(A, )说是一个全序集，说是一个全序集，如果如果(A, )本身是一条链。本身是一条链。v显然，全序集的子集仍为全序集。显然，全序集的子集仍为全序集。例例:v设设A 1,2,

47、4, 8,16,32,64 ，R是整除关系，是整除关系，则则(A, R) 是一是一个全序集。个全序集。1248321664例例:v设设A整数集合整数集合，R是是“小于等小于等于于”关系，则关系，则(A, R) 是一个是一个全序集。全序集。-2-10213定义定义1.2.17拟序关系拟序关系v设设R是集合是集合A上的一个关系。如果上的一个关系。如果R具具有反自反性，传递性，则称有反自反性，传递性，则称R为一个为一个拟序关系。记为，读做拟序关系。记为，读做“小于小于”。 v例：数间的小于（例：数间的小于（“”）关系；集关系；集合间的真包含（合间的真包含（“ ”）关系。）关系。定义定义1.2.18v

48、设设(A, )是一个部分序集是一个部分序集(poset)，(1)如果如果A中有一个元素中有一个元素a，对于所有，对于所有的的x A，都有，都有xa(ax)，则称，则称a为集合为集合A的最大的最大(最小最小)元。元。（2）A中元素中元素a说是一个极大说是一个极大( (极小极小) )元，元，如果除如果除a之外，之外，A中没有元素中没有元素x，使得，使得ax(xa)。 定义定义1.2.18(3) 对于对于A中的子集中的子集M，A中中元素元素a称为称为子集子集M的一个上界的一个上界(下界下界)，如果对，如果对M中中任意元素任意元素m，都有，都有ma(am)。(4) 对于对于A中的子集中的子集M，A中中

49、元素元素a称为称为M的一个最小上界的一个最小上界(或称上确界或称上确界)，如果，如果a是是M的一个上界，并且对的一个上界，并且对M的任意一个的任意一个上界上界x，都有，都有ax。定义定义1.2.18(5) 对于对于A中的子集中的子集M，A中中元素元素a称为称为M的一个的一个最大下界最大下界( (或称下确界或称下确界) ) ，如，如果果a是是M的一个的一个下下界，并且对界，并且对M的任意的任意一个一个下下界界x，都有，都有xa 。例例: a b a,b a,b,c a,b,c,d a,b,c,e 极大元极大元极小元极小元例例: a b a,b a,b,c a,b,c,d a,b,c,e a,b,c,d,e 例题v设设A=1,2,3,12, 是是A上的整除关系上的整除关系,(A, )和哈斯图如下和哈斯图如下,求求B=2,4,6,C=4,6,9,D=1,2,5,10的特殊元素的特殊元素.810421269573111极小极小元元极大极大元元最小最小元元最大最大元元上界上界下界下界最小最小上界上界最大最大下界下界