离散数学第一章第2节

《离散数学第一章第2节》由会员分享，可在线阅读，更多相关《离散数学第一章第2节（124页珍藏版）》请在装配图网上搜索。

1、数理学院数理学院SCHOOL OF MATHEMATICS AND PHYSICS11.2 关关 系系(relations)1.2.1关系的基本概念及其性质关系的基本概念及其性质 1.2.2等价关系等价关系 1.2.3部分序关系部分序关系数理学院数理学院SCHOOL OF MATHEMATICS AND PHYSICS21.2.1 关系的基本概念及其性质关系的基本概念及其性质 一、关系的定义一、关系的定义二、关系的表示二、关系的表示三、关系作为集合的运算三、关系作为集合的运算四、几种特殊关系及特点四、几种特殊关系及特点五、闭包运算五、闭包运算数理学院数理学院SCHOOL OF MATHEMAT

2、ICS AND PHYSICS3数理学院数理学院SCHOOL OF MATHEMATICS AND PHYSICS4一、关系的定义一、关系的定义 定义定义 设设A1,A2,An是是n个集合，个集合，集合集合A1 A2 An的一个子集的一个子集 F 称为称为A1,A2,An上的一个上的一个n元关系元关系。特别地，集合特别地，集合A B中的一个子集中的一个子集R，称为集合，称为集合A与与B上的上的一个一个二元关系二元关系(binary relationbinary relation)，简称为关系。，简称为关系。对于对于x A，y B，R是是A与与B上的一个二元关系，上的一个二元关系，若若(x,y)

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

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

5、和和C上的三元关系。上的三元关系。数理学院数理学院SCHOOL OF MATHEMATICS AND PHYSICS7R=(a,),(a,),(b,),(b,),(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分；分；学

6、生学生c所选所选 课程的成绩是课程的成绩是4分；分；学生学生f所选所选 课程的成绩是课程的成绩是2分。分。数理学院数理学院SCHOOL OF MATHEMATICS AND PHYSICS8例例 N上的小于关系上的小于关系R：R=(x,y)|x数学归纳法数学归纳法 证明：假设证明：假设m是任意自然数，对是任意自然数，对k归纳：归纳：当当k=0时，时，Ri+0p+m=Ri+m；当当k=1时，时，Ri+1p+m=Ri+j-i+m=Rj+m=Ri+m；假设假设k时成立，即：时成立，即：Ri+kp+m=Ri+m ，则则k+1的时候，有：的时候，有：Ri+(k+1)p+m=Ri+kp+p+m=Ri+kp

7、+ji+m=Rj+kp+m=Ri+kp+m=Ri+m。数理学院数理学院SCHOOL OF MATHEMATICS AND PHYSICS32证明证明(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)根据(1)数理学院数理学院SCHOOL OF MATHEMATICS AND PHYSICS33综合思考题综合思考题l 设设A表示工人的集合表示工人的集合,B表示工作的集合表示工作的集合.设设R1 表示表示A到到

8、B的二元关系的二元关系:R1=(a,b)a A,b B,a分配去做工作分配去做工作b.设设R2表示表示A到到A的二元关系的二元关系:R2=(a1,a2)a1,a2 A,a1和和a2不能友好相处不能友好相处.请你用请你用R1和和R2表示关系表示关系 R,使得使得xRy表示表示 x,y分配去做分配去做同样工作且能友好相处同样工作且能友好相处.v因为因为R1是是A到到B的二元关系的二元关系,故故R1-1表示表示B到到A的二元关的二元关系系,则则R1 R1-1表示从表示从A到到A的二元关系的二元关系,即由分配做同一即由分配做同一样工作的两个人构成的序偶的全体样工作的两个人构成的序偶的全体.因此因此R=

9、R1 R1-1-R2数理学院数理学院SCHOOL OF MATHEMATICS AND PHYSICS34四、几种特殊关系及特点四、几种特殊关系及特点1 1、自反、自反关系关系(reflexive)集合集合A 上的关系上的关系R称为是自反称为是自反的的(反身的反身的)，如果对，如果对每一个每一个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)（）？非空集合上的空关系？非空集合上的空关系（）、全域关系全域关系EA（）、相等关系相等关系IA（）？大于关系、父子关系

10、（？大于关系、父子关系（）数理学院数理学院SCHOOL OF MATHEMATICS AND PHYSICS35u 自反性特点：自反性特点：l R是自反的是自反的IA R R-1是自反的是自反的；l R有自反性，当且仅当有自反性，当且仅当R的关系图中每一点均有到自身的关系图中每一点均有到自身的弧。的弧。l 若若R的关系矩阵的主对角线元素都为的关系矩阵的主对角线元素都为1，则，则R具有自反性。具有自反性。数理学院数理学院SCHOOL OF MATHEMATICS AND PHYSICS362 2、反自反反自反关系关系(irreflexive)集合集合A上的关系上的关系R称为反自反的，如果对任称为

11、反自反的，如果对任意的意的x A，xRx均不成立均不成立。或者说对任意。或者说对任意的的x A，都有，都有xRx。v例：例：A=a,b,c,A上的关系上的关系？R1=(a,b),(b,b),(b,c)（）？R2=(a,b),(b,c),(a,c)（）？空关系？空关系（）、全域关系、全域关系EA（）、相等关系）、相等关系IA（）？小于关系（？小于关系（）数理学院数理学院SCHOOL OF MATHEMATICS AND PHYSICS37u 反自反性特点：反自反性特点：l R是反自反的是反自反的 IAR=；l R有反自反性，当且仅当有反自反性，当且仅当R的关系图中每一点均的关系图中每一点均没有到

12、自身的弧。没有到自身的弧。l 若若R的关系矩阵的主对角线元素都为的关系矩阵的主对角线元素都为0，则，则R具具有反自反性；有反自反性；数理学院数理学院SCHOOL OF MATHEMATICS AND PHYSICS38讨论：讨论：l 是否存在既具有自反性，又具有反自反性的关系？是否存在既具有自反性，又具有反自反性的关系？l 是否存在既不具有自反性，又不具有反自反性的关是否存在既不具有自反性，又不具有反自反性的关系？系？数理学院数理学院SCHOOL OF MATHEMATICS AND PHYSICS39讨论：讨论：l 是否存在既具有自反性，又具有反自反性的关系？是否存在既具有自反性，又具有反自

13、反性的关系？空集上的空关系空集上的空关系l 是否存在既不具有自反性，又不具有反自反性的关是否存在既不具有自反性，又不具有反自反性的关系？系？A=a,b,c,R=(a,a),(b,c),(b,a)数理学院数理学院SCHOOL OF MATHEMATICS AND PHYSICS403 3、对称对称关系关系(symmetric)集合集合A上的关系上的关系R称为对称的，如果称为对称的，如果xRy，则则yRx。其中。其中x A，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)

14、,(c,a)（）?R3=(a,a)（）?空关系空关系 、全域关系、全域关系EA 、相等关系、相等关系IA（）?同学关系，朋友关系，打架关系，同桌关系（同学关系，朋友关系，打架关系，同桌关系（）?父子关系，小于关系（父子关系，小于关系（）数理学院数理学院SCHOOL OF MATHEMATICS AND PHYSICS41u 对称性特点：对称性特点：l R是对称的是对称的 R-1=R；l R有对称性，当且仅当有对称性，当且仅当R的关系图中不同的两点间的关系图中不同的两点间若有弧相连则必定是成对出现的。若有弧相连则必定是成对出现的。l 若若R的关系矩阵为对称矩阵，则的关系矩阵为对称矩阵，则R具有对

15、称性；具有对称性；数理学院数理学院SCHOOL OF MATHEMATICS AND PHYSICS424 4、反对称、反对称关系关系(antisymmetric)集合集合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,b),(c,b),(b,c),(c,a)（）?R3=(a,a)（）?空关系空关系（）、全域关系、全域关系EA（）、相等关系、相等关系IA（）?同学关系，

16、相似关系（同学关系，相似关系（）?小于等于关系，父子关系（小于等于关系，父子关系（）数理学院数理学院SCHOOL OF MATHEMATICS AND PHYSICS43u 反对称性特点：反对称性特点：l R是反对称的是反对称的 RR-1 IAl R有反对称性，当且仅当有反对称性，当且仅当R的关系图中，若任意两个的关系图中，若任意两个不同点之间的有向弧都不成对出现。不同点之间的有向弧都不成对出现。l 在在R的关系矩阵中，若以主对角线为对称的元素都的关系矩阵中，若以主对角线为对称的元素都不同时为不同时为1，则，则R具有反对称性。具有反对称性。数理学院数理学院SCHOOL OF MATHEMATI

17、CS AND PHYSICS44R是反对称的，当且仅当是反对称的，当且仅当RR-1 IA l 证明：若证明：若R是空关系，结论显然成立。是空关系，结论显然成立。若若R不是空关系，先证不是空关系，先证必要性必要性：若若 RR-1=，则有，则有RR-1=IA；否则否则，任取，任取(x,y)RR-1，则，则(x,y)R而且而且(x,y)R-1，即，即，(x,y)R，且，且(y,x)R,则由则由R是反对称的，知是反对称的，知x=y，故，故(x,y)IA。因此，因此，RR-1 IA 数理学院数理学院SCHOOL OF MATHEMATICS AND PHYSICS45R是反对称的，当且仅当是反对称的，当

18、且仅当RR-1 IAl 再证充分性：再证充分性：若若xRy，yRx，则（，则（x,y）R,（x,y）R-1，故，故（x,y）R R-1。再由再由RR-1 IA，知（知（x,y）IA，因此，因此，x=y。所以，所以，R是反对称的。是反对称的。数理学院数理学院SCHOOL OF MATHEMATICS AND PHYSICS46讨论：讨论：l 是否存在既具有是否存在既具有对称对称性，又具有性，又具有反对称反对称性的关系？性的关系？l 是否存在既不具有是否存在既不具有对称对称性，又不具有反性，又不具有反对称对称性的关性的关系？系？数理学院数理学院SCHOOL OF MATHEMATICS AND P

19、HYSICS47讨论：讨论：l 是否存在既具有是否存在既具有对称对称性，又具有性，又具有反对称反对称性的关系？性的关系？空关系空关系、相等关系、相等关系IA （IA的子集的子集）l 是否存在既不具有是否存在既不具有对称对称性，又不具有反性，又不具有反对称对称性的关性的关系？系？A=a,b,c,R=(a,a),(a,b),(b,a),(b,c)数理学院数理学院SCHOOL OF MATHEMATICS AND PHYSICS485、传递关系传递关系(transitive)集合集合A上的关系上的关系R称为是传递的，如果称为是传递的，如果xRy，yRz，则则xRz。其中其中x A，y A，z A。v

20、例：例：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)（）数的大于关系、小于关系（数的大于关系、小于关系（）朋友关系，父子关系（朋友关系，父子关系（）空关系空关系、全域关系、全域关系EA、相等关系、相等关系IA（）数理学院数理学院SCHOOL OF MATHEMATICS AND PHYSICS49u 传递性特点：传递性特点：l R具有传递性的具有传递性的 R2 R。l R有传递性，当且仅当对于有传递性，当且仅当对于R的关系图中的任意三的关系图中的任意三点点a,b,

21、c，不存在这样的情形：有，不存在这样的情形：有a到到b的有向弧，的有向弧，b到到c的有向弧，但无的有向弧，但无a到到c的有向弧。的有向弧。l 如果如果M(R)2中某元素中某元素sij=1，那么，那么M(R)相应位置元素相应位置元素rij也一定为也一定为1，则，则R具有传递性。具有传递性。数理学院数理学院SCHOOL OF MATHEMATICS AND PHYSICS50定理定理1.2.4 v集合集合A上的关系上的关系R具有传递性的充要条件是具有传递性的充要条件是R2 R。v证明：必要性。证明：必要性。若若R具有传递性，任取具有传递性，任取(x,y)R2，于是存在，于是存在z A，使得，使得x

22、Rz，zRy，因为，因为R是传递是传递的，所以有的，所以有xRy，即，即(x,y)R,故故R2 R。充分性。充分性。如果如果xRy，yRz，则，则xR2z。因为因为R2 R，故，故xRz。所以。所以R具有传递性。具有传递性。数理学院数理学院SCHOOL OF MATHEMATICS AND PHYSICS51思考思考l A上关系上关系R是传递的是传递的当且仅当当且仅当对所有对所有n N+，都有，都有Rn R。提示：充分性易证；提示：充分性易证；采用采用数学归纳法数学归纳法证明必要性，即当证明必要性，即当R是传递的时，对是传递的时，对n N+进行归纳，证明进行归纳，证明Rn R。数理学院数理学院

23、SCHOOL OF MATHEMATICS AND PHYSICS52v关系的性质总结关系的性质总结自反的自反的反自反的反自反的对称的对称的反对称的反对称的传递的传递的定义定义任取任取 a A有有(a,a)R任取任取 a A有有(a,a)R若若(a,b)R,则则(b,a)R若若(a,b)R,(b,a)R,则则 a=b若若(a,b)R且且(b,c)R,则则(a,c)R 集合集合IA RIAR=R-1=RRR-1 IAR2 R关系关系图图图中每个图中每个结点都有结点都有自回路自回路图中每个结图中每个结点都无自回点都无自回路路任意两个不任意两个不同结点间要同结点间要么没有弧么没有弧,要要么有一对方么

24、有一对方向相反的弧向相反的弧任意两个不任意两个不同结点间至同结点间至多有一条弧多有一条弧若若a到到b有弧有弧,b到到c有弧有弧,则则a到到 c有弧有弧关系关系矩阵矩阵主对角线主对角线上全为上全为1主对角线上主对角线上全为全为0对称矩阵对称矩阵以主对角线以主对角线为对称的元为对称的元素不同时为素不同时为1MR2中某元素为中某元素为1，MR中相应中相应位置元素也一位置元素也一定为定为1数理学院数理学院SCHOOL OF MATHEMATICS AND PHYSICS53五、闭包运算五、闭包运算 一般来说，一般来说，A上的关系不一定具有上面讨论过的某上的关系不一定具有上面讨论过的某些性质，所以想到在

25、给定的关系些性质，所以想到在给定的关系R的基础上，扩充的基础上，扩充一些序偶得一新关系一些序偶得一新关系R，使新关系具有所要求的性，使新关系具有所要求的性质，但又希望它不太大。因此，讨论最小的包含质，但又希望它不太大。因此，讨论最小的包含R的的R，使它具有所要求的性质，这就是关系的闭包，使它具有所要求的性质，这就是关系的闭包。数理学院数理学院SCHOOL OF MATHEMATICS AND PHYSICS54关系的闭包关系的闭包(closure)v设设A是是非空非空集合，集合，R是是A上的二元关系。称上的二元关系。称R 是是R的的自反闭包自反闭包 ,如果如果R 满足：满足：（1）R 是自反的

26、是自反的 ；（2）R R；（3）对）对A上任意关系上任意关系R，若若R R，且，且R 是是自反自反的的 ，必有，必有RR。(对称闭包，传递闭包对称闭包，传递闭包)(对称的，传递的对称的，传递的)(对称的，传递的对称的，传递的)数理学院数理学院SCHOOL OF MATHEMATICS AND PHYSICS55R 的自反闭包、对称闭包和传递闭包分别记为的自反闭包、对称闭包和传递闭包分别记为r(R)，s(R)，t(R)，也称也称r，s，t为为闭包运算闭包运算，它们作用于关它们作用于关系系R后，产生包含后，产生包含R的最小的自反、对称、传递的关的最小的自反、对称、传递的关系。系。如何计算？如何计算

27、？数理学院数理学院SCHOOL OF MATHEMATICS AND PHYSICS56定理定理1.2.5 v设设R是集合是集合A上的关系，那么，上的关系，那么，(1)r(R)=IAR；(2)s(R)=RR-1；(3)t(R)=(x,y)|x A,y A,且存在且存在n0，使得，使得xRny=R+1iiR数理学院数理学院SCHOOL OF MATHEMATICS AND PHYSICS57（1 1）证明）证明 r(R)=IAR因为因为IA IAR，所以，所以IAR具有自反性；具有自反性；显然，显然，R IAR 对对A上任意关系上任意关系R，若若R R，且，且R 是是自反的，往证自反的，往证IA

28、R R。因为因为R 是是自反的，所以自反的，所以IA R ，又，又R R，所以所以IAR R。数理学院数理学院SCHOOL OF MATHEMATICS AND PHYSICS58（2 2）证明）证明 s(R)=RR-1 往证往证RR-1是对称的，任取是对称的，任取(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 数理学院数理学院SCHOOL OF MATHEMATICS

29、AND PHYSICS59对对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，由，由R R 知，知，(y,x)R，因为因为R 是是对称的对称的，所以，所以(x,y)R 。因此，因此，RR-1 R。数理学院数理学院SCHOOL OF MATHEMATICS AND PHYSICS60（3 3）证明）证明 t(R)=1iiR对于任意对于任意x,y,z A，若，若(x,y)(x,y)，(y,

30、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数理学院数理学院SCHOOL OF MATHEMATICS AND PHYSICS61对对A上任意关系上任意关系R，若若R R，且，且R 是是传递的，往传递的，往证证 R。为此只要证对任意正整数为此只要证对任意正整数n，Rn R 。对对n采用归纳法，采用归纳法，n=1时，显然有时，显然有R1 R 。假设。假设n=k时时有有Rk

31、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。证毕。证毕。1iiR1iiR数理学院数理学院SCHOOL OF MATHEMATICS AND PHYSICS62l 例例.设设 A=a,b,c，R=(a,b),(b,c),(c,a)则则自反闭包自反闭包r(R)=IAR =(a,b),(b,c),(c,a),(a,a),(b,b),(c,c)对称闭包对称闭包s(R)=RR-1=(a,b),(b,

32、c),(c,a),(b,a),(c,b),(a,c)传递闭包传递闭包 t(R)=RR R=EA1iiR数理学院数理学院SCHOOL OF MATHEMATICS AND PHYSICS631.2.2 等价关系等价关系(equivalence relation)定义定义设设A是一个是一个非空非空集合，集合，R是是A上二元关系。如上二元关系。如果果R具有自反性，对称性，传递性，则称具有自反性，对称性，传递性，则称R是一个等是一个等价关系。价关系。通常，用通常，用“”表示表示等价关系。等价关系。例：整数的模例：整数的模n同余关系同余关系(x,y)|x,yZ，x,y除以除以n余余数相同数相同，几何图形

33、的面积相等关系，人群中的同姓几何图形的面积相等关系，人群中的同姓关系、关系、同龄关系等。同龄关系等。数理学院数理学院SCHOOL OF MATHEMATICS AND PHYSICS64等价类等价类(equivalence class)设设A是一个是一个非空非空集合，集合，R是是A上的上的等价关系等价关系。A的一个的一个非非空子集空子集M叫做关于叫做关于R的一个等价类，如果的一个等价类，如果1）若）若a M，b M，则，则a R b。2）若）若a M，b M，则，则a R b；或者；或者,若若a M，a R b，则，则b M。数理学院数理学院SCHOOL OF MATHEMATICS AND

34、PHYSICS65定理定理1.2.6 设设 是非空集合是非空集合A上的等价关系，于是等价类上的等价关系，于是等价类是存在的。是存在的。v证明证明:任取任取a A，令，令M x|x A并且并且x a，(1)显然，显然，M非空，非空，a M。(2)任取任取x1 M，x2 M，根据，根据M的定义，则有的定义，则有x1 a，x2 a，而而 具有对称性，传递性，所以具有对称性，传递性，所以x1 x2。(3)任取任取x1 M，则，则x1 a，任取，任取yA，若，若x1 y，而，而 具有具有对称性，传递性，所以对称性，传递性，所以y a，故，故y M。因此，因此，M是一个等价类。是一个等价类。v通常，用通常

35、，用aR表示包含元素表示包含元素a的等价类，则的等价类，则 aR=x|xA且且(x,a)R,a称为该称为该等价类的等价类的代表元代表元。数理学院数理学院SCHOOL OF MATHEMATICS AND PHYSICS66例：例：设集合设集合A=1,2,3,10，R是是模模3同余同余(除以除以3之后，余之后，余数相同数相同)关系关系=(x,y)|x,yA，x,y除以除以3余数相同余数相同，则，则3R=6R=9R=3,6,9,1R=4R=7R=10R=1,4,7,10,2R=5R=8R=2,5,8都是等价类。都是等价类。设设A是本教室中的所有人集合，是本教室中的所有人集合，在同姓关系下，则在同姓

36、关系下，则本本教室中教室中所有姓所有姓“张张”的人构成的集合是一个的人构成的集合是一个等价类，等价类，所有姓所有姓“王王”的人构成的集合是一个的人构成的集合是一个等价类等价类,。数理学院数理学院SCHOOL OF MATHEMATICS AND PHYSICS67定理定理1.2.7 v设设 是集合是集合A上的等价关系，上的等价关系，M1,M2,，是，是A中关于中关于 的的所有等价类。于是所有等价类。于是AM1 M2 并且并且MiMj=(i j)，亦即，集合亦即，集合A上的等价关系把上的等价关系把A分分成了互不相交的等价类。成了互不相交的等价类。数理学院数理学院SCHOOL OF MATHEMA

37、TICS AND PHYSICS68证明：证明：v任取任取Mi，Mj，i j。假设。假设MiMj ，则必存在，则必存在x MiMj，则任取，则任取a Mi，b Mj，都有，都有a x，b x，所，所以以a b,故故Mi Mj，矛盾。，矛盾。v显然有显然有M1 M2 A，故只需证明，故只需证明 A M1 M2 。任取任取a A，令令M x x A并且并且x a，由定理由定理1.2.6知，知，M是等价类，故有是等价类，故有k，使得，使得MMk，因为，因为a M，所以，所以，a M1M2Mk。故故AM1 M2 。数理学院数理学院SCHOOL OF MATHEMATICS AND PHYSICS69划

38、分划分(partition)称集合称集合A的的子集族子集族C为为A的划分，如果：的划分，如果：（1）若）若B C，则，则B；（2）；（3）对任意的）对任意的B，BC，若，若B B，则，则BB=。称称C中元素为划分的中元素为划分的单元单元，或，或划分块划分块。v规定规定，A=时只有划分时只有划分。ABCB数理学院数理学院SCHOOL OF MATHEMATICS AND PHYSICS70例：例：v设设A=1,2,3,4,5,6,7,8,9,10，vC1=1,2,3,4,5,6,7,8,9,10 示意图为：示意图为：1 2 34 567 8 9 10A数理学院数理学院SCHOOL OF MATH

39、EMATICS AND PHYSICS71例：lA=1,2,3,4,5,6,7,8,9,10，lC2=1,3,2,4,5,6,7,8,9,101 34 5 8 9 10267A数理学院数理学院SCHOOL OF MATHEMATICS AND PHYSICS72商集商集(quotient set)v设设R是非空集合是非空集合A上的等价关系，以上的等价关系，以R的的所有不同等所有不同等价类为元素价类为元素作成的集合称为作成的集合称为A关于关于R的商集，简称的商集，简称A的的商集，记作商集，记作A/R。vA/R恰是集合的一个划分。恰是集合的一个划分。v设集合设集合A=1,2,3,10，R是模是模3

40、同余关系，则同余关系，则A/R 1R，2R，3R，这里，这里 1R=1,4,7,10,2R=2,5,8,3R=3,6,9 数理学院数理学院SCHOOL OF MATHEMATICS AND PHYSICS73例例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上的全体等价关系及其对应的商上的全体等价关系及其对应的商集。集。数理学院数理学院SCHOOL

41、 OF MATHEMATICS AND PHYSICS74解解 v(1)EA，IA，Rij是等价关系是等价关系(证明略证明略)。A/IA=a1,a2,an；A/EA=a1,a2,an；其中其中k1,k2,kn-2均不等于均不等于i或或j，共有共有C2n个这样的关系个这样的关系Rij。A为非空集合，为非空集合，因为无自反性，所以不是因为无自反性，所以不是A上的上的等价关系。等价关系。,/221nkkkjiijaaaaaRA数理学院数理学院SCHOOL OF MATHEMATICS AND PHYSICS75v(2)按按(1)中中n=3的情况，的情况，A=a,b,c上有上有5种不同的等价种不同的等

42、价关系：关系：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=a,c,b；R23=IA(b,c),(c,b)，A/R23=b,c,a；数理学院数理学院SCHOOL OF MATHEMATICS AND PHYSICS76等价关系等价关系=商集商集l 1.给定非空集合给定非空集合A，集合，集合A的一个等价关系，求该等的一个等价关系，求该等价关系对应的商集。价关系对应的商集。例如，设例如，设A=a,b,c，A的一个等价关系的一个等价关系IA，求，求

43、A/IA。显然：显然：IA=(a,a),(b,b),(c,c)。则：则：a IA=a，b IA=b，c IA=c 从而：从而：A/IA=a,b,c。关键：关键：求出该等价关系下集合求出该等价关系下集合A的每个元素所在的的每个元素所在的等价类。等价类。数理学院数理学院SCHOOL OF MATHEMATICS AND PHYSICS77商集商集=等价关系等价关系l 2.根据商集求等价关系。根据商集求等价关系。例如：例如：A=a,b,c，A的一个商集：的一个商集：A/R=a,b,c，则该商集对应的等价关系，则该商集对应的等价关系R为：为：R=(a,a),(b,b),(c,c),(b,c),(c,b

44、)=IA(b,c),(c,b)关键：关键：R=IA(),(),数理学院数理学院SCHOOL OF MATHEMATICS AND PHYSICS78定理定理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上的等价关系。上的等价关系。数理学院数理学院SCHOOL OF MATHEMATICS AND PHYSICS79(1)证明

45、：证明：A/R是是A的一个划分的一个划分设商集设商集A/R M1,M2,，则，则i(i=1,2,)是是A关于关于R的的等价类，根据等价类的定义知，等价类，根据等价类的定义知，i (i=1,2,);又又根据根据定理定理1.2.7知，知，AM1 M2，并，并且且MiMj=(i j)，所以，所以，A/R是是A的一个划分。的一个划分。数理学院数理学院SCHOOL OF MATHEMATICS AND PHYSICS80(2)证明：证明：RC为为A上的等价关系上的等价关系自反性；自反性；对任意的对任意的x A，有，有x和和x属于属于C的同一划分块，的同一划分块，所以所以(x,x)(x,x)RC，则，则R

46、C 具有自反性；具有自反性；对称性；对称性；对任意的对任意的x,y A，若，若(x,y)RC，即，即x,y属于属于C的同一划分块，亦即的同一划分块，亦即y,x 属于属于C的同一划分块，所以的同一划分块，所以(y,x)(y,x)RC，则，则RC 具有对称性；具有对称性；数理学院数理学院SCHOOL OF MATHEMATICS AND PHYSICS81传递性传递性；对任意的；对任意的x,y,z A，若若(x,y)RC，(y,z)RC，即，即x与与y属于同一划分块属于同一划分块X，y与与z属于同一划分块属于同一划分块Y，则，则y在在X与与Y这两个划分块的交这两个划分块的交集中，按照定义，任意不同

47、的划分块交集为空，从而集中，按照定义，任意不同的划分块交集为空，从而只能有：只能有：X=Y。即。即x与与z也属于同一划分块，所以也属于同一划分块，所以(x,z)RC，则，则RC 具有传递性；具有传递性；因此，因此，RC为为A上的等价关系。证毕。上的等价关系。证毕。数理学院数理学院SCHOOL OF MATHEMATICS AND PHYSICS82第二类第二类Stirling数数 v将将n个个不同的球不同的球放入放入r个个相同的盒相同的盒中去，并且要求无空中去，并且要求无空盒，有多少种不同的放法？这里要求盒，有多少种不同的放法？这里要求n r。v不同的放球方法数即为不同的放球方法数即为n元集合

48、元集合A的不同的划分数。的不同的划分数。v设设 表示将表示将n个不同的球放入个不同的球放入r个相同的盒中的方案个相同的盒中的方案数，称数，称 为第二类为第二类Stirling数。数。rnrn数理学院数理学院SCHOOL OF MATHEMATICS AND PHYSICS83第二类第二类Stirling数数的性质的性质00nv没有盒子，当然谈不到放法，所以没有盒子，当然谈不到放法，所以 v如果只有一个盒子，则所有如果只有一个盒子，则所有n个球只能放到该盒子里，个球只能放到该盒子里，放球的方案数为放球的方案数为1；.1,1,122,11,00)1(21nnCnnnnnnn数理学院数理学院SCHO

49、OL OF MATHEMATICS AND PHYSICS84l 如果有两个相同的盒子，先任取一个球如果有两个相同的盒子，先任取一个球ai，把它放，把它放到一个盒子里，对于剩下的到一个盒子里，对于剩下的n-1个球，每个球可以个球，每个球可以有两种选择：与有两种选择：与ai放在同一个盒子里或者不与放在同一个盒子里或者不与ai放放在同一个盒子里，根据乘法原理有在同一个盒子里，根据乘法原理有2n-1种方法。但种方法。但是其中有一种方法是错误的，即是其中有一种方法是错误的，即n-1个球都与个球都与ai放放在了同一个盒子里而另一个盒子为空。所以：在了同一个盒子里而另一个盒子为空。所以：1221nn数理学

50、院数理学院SCHOOL OF MATHEMATICS AND PHYSICS85l 当盒子数为当盒子数为n-1的时候，要把的时候，要把n个不同的球放到个不同的球放到n-1个个相同的盒子里，而且没有空盒，必然有一个盒子里放相同的盒子里，而且没有空盒，必然有一个盒子里放两个球。这两个球要从两个球。这两个球要从n个球中选取，有个球中选取，有Cn2种选择方种选择方法，所以：法，所以：当有当有n个相同的盒子的时候，个相同的盒子的时候，n个不同的球，没有空盒，个不同的球，没有空盒，只有一种放法。只有一种放法。.12nCnn数理学院数理学院SCHOOL OF MATHEMATICS AND PHYSICS8

51、6第二类第二类Stirling数数的性质的性质l(2)满足如下的递推公式：满足如下的递推公式：证明：把证明：把n个不同的球正好放到个不同的球正好放到r个相同的盒子里，没个相同的盒子里，没有空盒。我们先取一个球，设该球的编号为有空盒。我们先取一个球，设该球的编号为ai，然后，然后把所有的放法分成两类：把所有的放法分成两类：.111 rnrnrrn数理学院数理学院SCHOOL OF MATHEMATICS AND PHYSICS87 第一种，第一种，ai单放在一个盒子里，剩下的单放在一个盒子里，剩下的n-1个球放在个球放在剩下的剩下的r-1个盒子里，方法数为：个盒子里，方法数为：.111 rnrn

52、rrn 综上，根据加法原理，有：综上，根据加法原理，有：rn 1 第二种，第二种，ai不单放在一个盒子里。可以先把不单放在一个盒子里。可以先把n-1个球放在个球放在r个盒子里，有个盒子里，有 种方法，对于其中的任种方法，对于其中的任何一种方法，加入何一种方法，加入ai的方法有的方法有r种，由乘法原理，放种，由乘法原理，放球的方法数为：球的方法数为：rnr111rn数理学院数理学院SCHOOL OF MATHEMATICS AND PHYSICS88例例1.2.4 v集合集合A=a，b，c，d上有多少不同的等价关系？上有多少不同的等价关系？v解：不同的划分个数为解：不同的划分个数为:不同的等价关

53、系个数等于不同的划分个数，所以不同的等价关系个数等于不同的划分个数，所以不同的等价关系个数为不同的等价关系个数为1515。.151121443424142414C数理学院数理学院SCHOOL OF MATHEMATICS AND PHYSICS89定义定义1.2.14 加细加细v设设C和和C 都是集合都是集合A的划分，若的划分，若C的每个划分块都的每个划分块都包包含于含于C 的某个划分块中，则称的某个划分块中，则称C是是C 的加细。的加细。v示意图：示意图：CCA1A2A3A4B1B2数理学院数理学院SCHOOL OF MATHEMATICS AND PHYSICS90v例：设例：设A=1,2

54、,3,4，C1=1,2,3,4；C2=1,2,3,4；C3=1,2,3,4；C4=1,2,3,4；则则C4是是C1,C2,C3的加细；的加细；C3是是C1,C2的加细；的加细；C2是是C1的加细。的加细。数理学院数理学院SCHOOL OF MATHEMATICS AND PHYSICS91C是是C 的加细当且仅当的加细当且仅当RC RC v证明：证明：必要性必要性，取，取(x,y)Rc,则则x，y在在C的某一个划的某一个划分块中，因为分块中，因为C是是C的加细，的加细，C的每个划分块都包含于的每个划分块都包含于C的某个划分块中，从而的某个划分块中，从而x,y应该在应该在C的某一个划分块的某一个

55、划分块中，这样，就有中，这样，就有(x,y)Rc，从而有：，从而有：Rc Rc;数理学院数理学院SCHOOL OF MATHEMATICS AND PHYSICS92l 充分性充分性，任取任取C的一个划分块的一个划分块M，显然，显然M非空。非空。若若M中中只有一个元素只有一个元素x,则有则有(x,x)Rc，从而有，从而有(x,x)Rc，x出现在出现在C的某个划分块的某个划分块M中，则中，则M M；若若M中中元素多于两个元素多于两个，任取任取x,y M，则有，则有(x,y)Rc，从而，从而(x,y)Rc，也有，也有x,y都出现在都出现在C的某一的某一个划分块个划分块M中，则中，则M M。从而从而

56、C是是C的加细。的加细。数理学院数理学院SCHOOL OF MATHEMATICS AND PHYSICS93v例：例：v设设A=x|x是数理学院的本科生是数理学院的本科生，A上两个等价关系：上两个等价关系：同班，同年级。同班，同年级。vRc=(x,y)|x,yA而且而且x,y同班同班；Rc=(x,y)|x,yA而且而且x,y同年级同年级;则：则：C=070班的学生班的学生，0702班的学生班的学生，0801班的学生班的学生,0901班的学生班的学生,1001班的学生班的学生;C=大一的学生大一的学生,大二的学生大二的学生,大三的学生大三的学生,大四的学生大四的学生；有，有，C是是C的加细，的

57、加细，Rc是是Rc的子集。的子集。数理学院数理学院SCHOOL OF MATHEMATICS AND PHYSICS94例例1.2.5 v设设A=a，b，c，找出找出A的全部划分及对应的等价的全部划分及对应的等价关系，以及划分间的加细和等价关系间的包含关系。关系，以及划分间的加细和等价关系间的包含关系。v解解:由 第 二 类由 第 二 类 S t i r l i n g 数 易 知，数 易 知，A 上 共 有上 共 有 个划分。个划分。.5112133231313数理学院数理学院SCHOOL OF MATHEMATICS AND PHYSICS95v这些这些划分划分分别为：分别为：C1=a,b

58、,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的子集。的子集。数理学院数理学院SCHOOL OF MATHEMATICS AND PHYSICS961.2.3部分序关系部分序关系(partial ordering)设设R是集合是集合A上的一个关系。如果上的一个关系。如果R具有具有自反

59、性自反性，反对反对称性称性，传递性传递性，则称，则称R为一个部分序关系为一个部分序关系(半序关系、半序关系、偏序关系偏序关系)。集合。集合A在部分序关系在部分序关系R下做成一个下做成一个部分序集部分序集(半序集、偏序集半序集、偏序集)。记作记作(A，R)。v通常，将部分序关系通常，将部分序关系R写做写做“”，读做，读做“小于或等小于或等于于”。v 显然，一个部分序集的子集仍为部分序集。显然，一个部分序集的子集仍为部分序集。(A,R)=(B,R(BB),其中其中B A数理学院数理学院SCHOOL OF MATHEMATICS AND PHYSICS97例例 v设设A是整数集合，是整数集合，R是小

60、于等于是小于等于关系关系(或大于等于关系或大于等于关系)，则则(A,R)是一个部分序集是一个部分序集；v设设A是正整数集合，是正整数集合，R是整除关系，则是整除关系，则(A,R)是一个部是一个部分序集分序集；v设设A是一个集合族，是一个集合族，R是是“”关系。则关系。则(A,R)是一个部是一个部分序集。分序集。数理学院数理学院SCHOOL OF MATHEMATICS AND PHYSICS98设（设（A,R）是部分序集，则）是部分序集，则(B,R(BB)是部分是部分序集序集,其中其中B Al 证明：证明：1.R(BB)是自反的是自反的，任取任取xB，则，则(x,x)BB，由由xB，B A，知

61、，知xA因因R是是A上的自反关系，故上的自反关系，故(x,x)R因此，因此，(x,x)R(BB)，即，即R(BB)是自反的。是自反的。2.R(BB)是反对称的是反对称的，若若(x,y)R(BB)，(y,x)R(BB)，则则 (x,y)R而且而且(y,x)R，因为，因为R是反对称是反对称的，所以的，所以x=y。因此，因此，R(BB)是反对称的。是反对称的。数理学院数理学院SCHOOL OF MATHEMATICS AND PHYSICS993.R(BB)是传递的是传递的，若若(x,y)R(BB),(y,z)R(BB),则则(x,y)R,(y,z)R,由由R有传递性知，有传递性知，(x,z)R;另

62、外，另外，(x,y)BB，(y,z)BB，显然，显然BB是是B的全的全域关系域关系EB，则，则(x,z)BB。这样就有。这样就有：(x,z)R(BB)，即，即R(BB)是传递的。是传递的。数理学院数理学院SCHOOL OF MATHEMATICS AND PHYSICS100哈斯哈斯图图(Hasse diagram)v以平面上的点代表部分序集中的元素。以平面上的点代表部分序集中的元素。1）若若xy，且，且xy，则将，则将x画在画在y的下面。的下面。2）若若xy，xy，并且，并且没有没有不同于不同于x，y的的z，使得使得xzy(称称y盖住盖住x)，则在，则在x，y之间用直线连结。之间用直线连结。

63、数理学院数理学院SCHOOL OF MATHEMATICS AND PHYSICS101例例: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 数理学院数理学院SCHOOL OF MATHEMATICS AND PHYSICS102例例:v设设A 1,2,3,4,5,6,8,10,12,24，R是整除关系，则是整除关系，则(A,R)是一个部分序集。是一个部分序集。3152641210824数理学院数理学院SCHOOL OF MATHEMATICS AND PHYSICS10

64、3链链(chain)v设设(A,)是一个部分序集，对任意是一个部分序集，对任意x,y A，如果，如果xy，或或yx，称，称x与与y可比可比(comparable)；否则，称；否则，称x与与y不可不可比比。v一个部分序集的子集，其中任意两个元素都可比，称一个部分序集的子集，其中任意两个元素都可比，称该子集为一条该子集为一条链链(chain)。数理学院数理学院SCHOOL OF MATHEMATICS AND PHYSICS104例例:v设设A 1,2,3,4,5,6,8,10,12,24，R是整除关系，则是整除关系，则(A,R)是一个部分序集。是一个部分序集。3152641210824数理学院数

65、理学院SCHOOL OF MATHEMATICS AND PHYSICS105全序集全序集(totally ordered set)v一个部分序集一个部分序集(A,)说是一个全序集，如果说是一个全序集，如果(A,)本身本身是一条链。是一条链。v结论结论:若（若（A,R）是全序集，则）是全序集，则(B,R(BB)是全序集是全序集,其中其中B A数理学院数理学院SCHOOL OF MATHEMATICS AND PHYSICS106例例:v设设A 1,2,4,8,16,32,64，R是整除关系，则是整除关系，则(A,R)是是一个全序集。一个全序集。1248321664数理学院数理学院SCHOOL

66、OF MATHEMATICS AND PHYSICS107例例:v设设A整数集合整数集合，R是是“小于等于小于等于”关系，则关系，则(A,R)是一个全序集。是一个全序集。-2-10213数理学院数理学院SCHOOL OF MATHEMATICS AND PHYSICS108拟序关系拟序关系v设设R是集合是集合A上的一个关系。如果上的一个关系。如果R具有具有反自反性，传反自反性，传递性递性，则称，则称R为一个拟序关系。记为为一个拟序关系。记为，读做，读做“小小于于”。v注意，拟序关系的定义中隐含了其具有注意，拟序关系的定义中隐含了其具有反对称性反对称性。v例：数间的小于（例：数间的小于（“”）关系；集合间的真包含关系；集合间的真包含（“”）关系。）关系。数理学院数理学院SCHOOL OF MATHEMATICS AND PHYSICS109拟序关系是反对称的拟序关系是反对称的l证明：若证明：若R=，则，则R是反自反的、传递的，是反自反的、传递的，而且是反对称的；而且是反对称的；若若R不是空集，任取不是空集，任取(x,y)R，即即xRy,断断言言xy，否则与，否则与R是反自反的矛盾，往证一