集合论-第三章2

1、2.3 2.3 例题例题例例1 1 设设R R为为X X上的二元关系，显然若上的二元关系，显然若R R ，则，则R R是反自是反自反的、对称和传递的；但若反的、对称和传递的；但若RR 且且R R是反自反的和对是反自反的和对称的，则称的，则R R不是传递的。不是传递的。此题可变形为：此题可变形为： 若若RR 且且R R是反自反的和传递的是反自反的和传递的, ,则则R R是反对称的。是反对称的。例例2 2 设设R R是是X X上的二元关系，证明：上的二元关系，证明：R R对称对称R RR R-1-1。说明说明: :例中的结果还可以减弱为例中的结果还可以减弱为X X上的二元关系上的二元关系R R是对

2、是对称当且仅当称当且仅当R R R R-1-1。第二章第二章 习题课（习题课（1 1）例例1 1 设设X X a,b,ca,b,c ，给出，给出X X上的一个二元关系，使其同上的一个二元关系，使其同时时不满足不满足自反性、反自反性、对称性、反对称和传递自反性、反自反性、对称性、反对称和传递性的二元关系，并画出性的二元关系，并画出R R的关系图。的关系图。例例2 2 设设A A是集合，是集合，R,SR,SX XX X且且R,SR,S都是传递的，则都是传递的，则 (1) RS(1) RS是否传递的？是否传递的？ (2) RS(2) RS是否是不传递的？是否是不传递的？ 不一定是传递的不一定是传递的

3、; ; 不一定不传递的（有可能传递）不一定不传递的（有可能传递） 例例3 3 设有集合设有集合X X，|X|=3,|X|=3,求求X X上具有上具有反自反且反对称性反自反且反对称性的的二元关系的数目，并写出计算过程。二元关系的数目，并写出计算过程。 若若|X|=n|X|=n，结果又如何？，结果又如何？ |X|=3,27; |X|=n, 3 |X|=3,27; |X|=n, 3(n(n2 2-n)/2-n)/2 例例4 4 设设X X是一个集合，是一个集合，|X|X|n n，求：，求： (1) X(1) X上的二元关系有多少？上的二元关系有多少？ (2) (2) X X上的自反的二元关系有多少？

4、上的自反的二元关系有多少？ (3) X(3) X上的反自反的二元关系有多少？上的反自反的二元关系有多少？ (1)2(1)2n2 n2 (2)(2)、(3)(3)自反与反自反一样多自反与反自反一样多2 2n2-nn2-n (4) (4) X X上的对称的二元关系有多少？上的对称的二元关系有多少？ (5) X(5) X上的反对称的二元关系有多少？上的反对称的二元关系有多少？ (4)(4) 2 2(n2+n)/2 (n2+n)/2 (5)(5) 3 3(n2-n)/2(n2-n)/22 2n n (6) X (6) X上上既是既是自反的自反的又是又是反自反的关系有多少？反自反的关系有多少？ (7)

5、X(7) X上既不是自反的也不是反自反的关系有多少？上既不是自反的也不是反自反的关系有多少？ (6)0 ,(7)(6)0 ,(7) |B|BC CCCC C|=|S|-|A|=|S|-|AB|=2|=2n2-nn2-n(2(2n n-2)-2) (8) X (8) X上自反的且对称的关系有多少？上自反的且对称的关系有多少？ 与与“反自反且对称关系有多少？反自反且对称关系有多少？”一样多一样多2 2(n2-n)/2(n2-n)/2 (9) X(9) X上自反的或对称的关系有多少？上自反的或对称的关系有多少？ |BC|=2|BC|=2n2-nn2-n+2+2(n2+n)/2(n2+n)/2-2-2

6、(n2-n)/2(n2-n)/2 (10)X (10)X上反自反的上反自反的且且反对称的关系有多少？反对称的关系有多少？ (11)X(11)X上上既是既是对称的对称的也是也是反对称的关系有多少？反对称的关系有多少？ (10) 3(10) 3(n2-n)/2(n2-n)/2 (11) R(11) RI IX X，2 2n n (12)X(12)X上既不是对称的也不是反对称的关系有多少？上既不是对称的也不是反对称的关系有多少？ |B|BC CCCC C|=|S|-|B|=|S|-|BC|=2|=2n2n2-2-2(n2+n)/2(n2+n)/2-3-3(n2-n)/2(n2-n)/22 2n n+

7、2+2n n例例5 5 设设 A=1,2,3A=1,2,3，R R是是A A的幂集的幂集2 2A A上的二元关系且上的二元关系且 R=(R=(a,b)|aa,b)|ab b ，则，则R R不满足下列哪些性质？不满足下列哪些性质？为什么？为什么？ aRbaRb a ab b (1) (1) 自反性自反性 (2) (2) 反自反性反自反性 (3) (3) 对称性对称性 (4) (4) 反对称性反对称性 (5) (5) 传递性传递性 不满足自反性、反自反性、反对称性、传递性不满足自反性、反自反性、反对称性、传递性 例例6 6 设设R R是复数集合是复数集合C C上的一个二元关系且满足上的一个二元关系

8、且满足xRyxRyx-yx-y= =a+bia+bi，a,ba,b为非负整数，试确定为非负整数，试确定R R的性质。的性质。若若a=b=0a=b=0时，时，R=I(R=I(恒等关系恒等关系) )，满足满足自反性、对称、反自反性、对称、反对称性、传递性对称性、传递性若若a a、b b不全为零不全为零0 0时，时，满足反满足反自反性、反对称性自反性、反对称性5 5 关系矩阵和关系图关系矩阵和关系图 前面介绍过的关系都是用集合表达式来定义的，前面介绍过的关系都是用集合表达式来定义的，对于有限集合上的关系还可以用关系矩阵和关系图的对于有限集合上的关系还可以用关系矩阵和关系图的方法给出，这两种方法形象、

9、直观，不仅对分析关系方法给出，这两种方法形象、直观，不仅对分析关系性质有很大的方便，而且也有利于用计算来处理有关性质有很大的方便，而且也有利于用计算来处理有关问题。问题。5.15.1关系矩阵关系矩阵定义定义1 1 设设A A、B B为有限集合为有限集合,A=a,A=a1 1,a,a2 2, ,a,an n, B=b B=b1 1,b,b2 2, , ,b bm m , ,则则 (1) (1) 若若R R是从是从A A到到B B的二元关系，则的二元关系，则n nm m矩阵矩阵M MR R=(=(r rijij) )n nm m称为称为A A到到B B的二元关系的二元关系R R的关系矩阵，简称的关

10、系矩阵，简称关系矩阵。其中关系矩阵。其中1 ( ,) 1,2, ;1,2,3,0 ( ,)ijijija bRrin jma bR当当(2) (2) 若若R R是是A A上的关系，则上的关系，则n nn n矩阵称为矩阵称为A A上的二元关系上的二元关系R R的关系矩阵，简称关系矩阵，其中：的关系矩阵，简称关系矩阵，其中：二、例题二、例题例例1 设设A=a1,a2,a3,a4，B=b1,b2,b3。A到到B的二元关系的二元关系R=(a1,b1),(a1,b3),(a2,b3),(a4,b2)，则，则R的关系矩阵为：的关系矩阵为：例例2 设设A=1,2,3,4,，集合，集合A上的大于关系上的大于关

11、系“”定义为：定义为： =(2,1),(3,1),(4,1),(3,2),(4,2),(4,3)，则关系则关系“”的关系矩阵为的关系矩阵为：101001000010RM0000100011001110M1 (,) ( ,1, 2,)0 (,)ijijijaaRri jnaaR当当三、关系矩阵包含关系的信息三、关系矩阵包含关系的信息 设设M MR R是关系是关系R R的关系矩阵，则的关系矩阵，则 (1) R(1) R是自反的是自反的M MR R的对称线上的元素全为的对称线上的元素全为1 1。 (2) R(2) R是反自反的是反自反的M MR R对称线上的元素全为对称线上的元素全为0 0。 (3)

12、 R(3) R是对称的是对称的MRMR是对称的。是对称的。 (4) R(4) R是反对称的是反对称的若若ijij, ,则则r rijij与与r rjiji不能同时为不能同时为1 1。 或或r rijij+r+rjiji1 (5) R (5) R是传递的是传递的若若r rijij1 1且且r rjkjk1 1，则，则r rikik1 1。 或或M MR RM MR RMMR R，即，即R RR RR R (6) R (6) R-1-1的关系矩阵为的关系矩阵为M MR RT T。5.25.2关系图关系图定义定义1 1 设设A A，B B为有限集合，为有限集合，A=aA=a1 1,a,a2 2, ,

13、a,an n, , B=bB=b1 1,b,b2 2, , ,b bm m,R,R是是A A到到B B的一个二元关系。的一个二元关系。 首先在平面上用首先在平面上用n n个小圆点代表个小圆点代表A A中的中的n n个元素，个元素，并在这些点的旁边标上并在这些点的旁边标上a a1 1,a,a2 2, ,a,an n ；然后用另外；然后用另外m m个个小圆点代表小圆点代表B B中的中的m m个元素，并在这些点旁边标上个元素，并在这些点旁边标上b b1 1,b,b2 2, , ,b bm m 。于是有：。于是有： 若若( (a ai i,b,bj j) )R R，则在顶点，则在顶点a ai i到作一

14、条带箭头的线到作一条带箭头的线指向顶点指向顶点b bj j ； 若若( (a ai i,b,bj j) ) R R ，则，则a ai i与与b bj j之间没有线联结。之间没有线联结。 用这种方法构造的图形称为用这种方法构造的图形称为A A到到B B的关系的关系R R的关系的关系图，简称关系图。图，简称关系图。 当当A AB B时时，A A上的关系上的关系R R的关系图画法类似。把的关系图画法类似。把A A中的中的每一个元素在平面上用点表示，并在这些点旁边标上每一个元素在平面上用点表示，并在这些点旁边标上元素的名字。元素的名字。 若若( (a ai i,b,bj j) )R R，则从代表，则从

15、代表a ai i的点的点画画一条带箭头的一条带箭头的线指向代表线指向代表a aj j的点。的点。 若若( (a ai i,a,ai i) )R R, ,则从顶点则从顶点a ai i也画一条指向自己的矢也画一条指向自己的矢线，称为环。线，称为环。 这样得到的图形称为这样得到的图形称为A A上的关系上的关系R R的关系图，简称的关系图，简称关系图。关系图。说明：说明：为了使图形直观，易于理解，通常把为了使图形直观，易于理解，通常把A A中元素中元素a a1 1,a,a2 2, ,a,an n画在左边，而把画在左边，而把B B中元素中元素b b1 1,b,b2 2, , ,b bm m画在画在右边。

16、右边。2.2.例例(1)(1)设设A=1,2,3,4,B=A=1,2,3,4,B=a,b,ca,b,c ，A A到到B B的二元关系的二元关系 R=(1,a),(2,a),(4,a),(3,b),(3,c)R=(1,a),(2,a),(4,a),(3,b),(3,c)，则，则R R的关系图的关系图如图如图1 1所示。所示。 (2) (2) 设设A=1,2,3,4A=1,2,3,4，则在，则在A A上的整除关系上的整除关系R=(1,1),(1,2),(1,3),(1,4),(2,2),(2,4),(3,3),(4,4)R=(1,1),(1,2),(1,3),(1,4),(2,2),(2,4),(

17、3,3),(4,4)，则则R R的关系图如图的关系图如图2 2所示。所示。 图图1 图图21234cba1234二、关系图包含关系的所有信息二、关系图包含关系的所有信息(1) R(1) R是自反的是自反的 R R的关系图的每个顶点都有一个环。的关系图的每个顶点都有一个环。(2) R(2) R是反自反的是反自反的 R R的关系图的每个顶点都没有环。的关系图的每个顶点都没有环。(3) R(3) R是对称的是对称的在在R R的关系图中，若两个不同的顶点的关系图中，若两个不同的顶点间有弧，则必有方向相反的两条弧（对称弧）。间有弧，则必有方向相反的两条弧（对称弧）。(4) R(4) R是反对称是反对称在

18、在R R的关系图中，若两个不同的顶点的关系图中，若两个不同的顶点之间有弧，则弧只有一条。之间有弧，则弧只有一条。(5) R(5) R是传递的是传递的在在R R的关系图中，任意从某点沿箭头的关系图中，任意从某点沿箭头所指的方向经过二步走到另一点，则从该点必能一步所指的方向经过二步走到另一点，则从该点必能一步走到另一点。走到另一点。5.3 5.3 闭包的运算闭包的运算 用矩阵方法计算闭包用矩阵方法计算闭包 一、布尔矩阵的运算一、布尔矩阵的运算 在关系矩阵在关系矩阵M MR R中，中，r rijij的值不是的值不是0 0就是就是1 1，这种矩阵，这种矩阵称为布尔矩阵。把关系用对应的称为布尔矩阵。把关

19、系用对应的布尔矩阵布尔矩阵表示，而布表示，而布尔矩阵是代数所研究的对象，因此便于进行尔矩阵是代数所研究的对象，因此便于进行代数处理代数处理。特别是矩阵间可以进行特别是矩阵间可以进行代数运算代数运算，这有利于计算机的，这有利于计算机的存储处理，下面介绍布尔矩阵间的若干运算。存储处理，下面介绍布尔矩阵间的若干运算。定义定义1 1 设设M MR R,M,MS S是两个是两个阶的布尔矩阵，则阶的布尔矩阵，则（1 1）把）把M MR R和和M MS S的对应元素的的对应元素的“逻辑和逻辑和”所形成的矩所形成的矩阵称为阵称为M MR R与与M MS S的的逻辑和逻辑和，记为，记为M MR RM MS S。

20、即。即 M MR RM MS S=(=(r rijijssijij) )。其中，其中，0 00=0,00=0,01=11=10=10=11 1。 运算是取最大运算是取最大 （1 1）把）把M MR R和和M MS S的对应元素的的对应元素的“逻辑乘逻辑乘”所形成的矩所形成的矩阵称为阵称为M MR R与与MSMS的的逻辑乘逻辑乘 ，记为，记为M MR RM MS S。即。即 M MR RM MS S=(=(r rijijs sijij) )。其中其中,0,00=00=01=11=10=0,10=0,11=11=1运算是取最小运算是取最小 （3 3）设）设M MR R是是n np p，M MS S

21、是是p pm m阶的布尔矩阵，定义阶的布尔矩阵，定义M MR R与与M MS S的的“布尔乘法布尔乘法”运算运算“”,”,令令M MR RM MS S=M=MT T=(=(t tijij) )nmnm，则则“”“”运算是先取最小，再取最大运算是先取最小，再取最大 11221()()()(),1,2,;1,2,ijijijippjpikkjktrsrsrsrsin jm 二、求二、求RSRS，RSRS，RSRS关系矩阵关系矩阵(1)M(1)MRSRS= M= MR RM MS S；(2)M(2)MRSRS= M= MR RM MS S；(3)M(3)MRSRS= M= MR RMMS S。三、闭

22、包的运算三、闭包的运算(1)M(1)Mr(R)r(R)=M=MR RM MI I； r(Rr(R)=RI)=RI(2)M(2)Ms(R)s(R)=M=MR RM MR RT T； s(Rs(R)=RR)=RR-1-1(3)M(3)MR+R+= =M Mt(Rt(R) )=M=MR RM MR R2 2M MR Rn n。 R R+ += =t(Rt(R)=RR)=RR2 2R Rn n 6 6 等价关系与划分等价关系与划分 内容：等价关系、等价类、划分、等价关系与划分的关系内容：等价关系、等价类、划分、等价关系与划分的关系6.1 6.1 等价关系等价关系一、定义一、定义定义定义1 1 设设R

23、R是非空集合是非空集合A A上的二元关系，若上的二元关系，若R R同时具有同时具有以下三个性质：以下三个性质： (1)R(1)R是自反的；是自反的；(2)R(2)R是对称的；是对称的；(3)R(3)R是传递的。是传递的。则称则称R R是是A A上的等价关系，记为上的等价关系，记为“”。 R R是等价关系是等价关系二、例：二、例：12,AIR RRRR二、例：二、例：1.1.平面上三角形集合中，三角形的相似关系，全等关平面上三角形集合中，三角形的相似关系，全等关系都是等价关系。系都是等价关系。2.2.实数集上实数集上n n阶方阵集合中，矩阵的相似、正交关系阶方阵集合中，矩阵的相似、正交关系也是等

24、价关系。也是等价关系。3.3.恒等关系和全关系是等价关系。恒等关系和全关系是等价关系。4. 4. 定义在人的集合上的定义在人的集合上的 “年龄相等年龄相等”是等价关系，是等价关系，但但“相互认识相互认识”、“同学同学”、 “朋友朋友”关系都不是关系都不是等价关系。等价关系。5.5.整数整数Z Z上的上的“相等相等”、“模模n n同余同余”关系都是等价关关系都是等价关系。系。 设设X=1,2,X=1,2,7,8,7,8，R=(R=(x,y)|x,yXx,y)|x,yX且且x=y(mod3)x=y(mod3)，其中其中x=y(mod3) x=y(mod3) 表示表示x-yx-y可以被可以被3 3整

25、除，称整除，称R R为为X X上的模上的模3 3同余关系，则同余关系，则R R是是X X上的等价关系。上的等价关系。6.2 6.2 等价类等价类一、定义一、定义定义定义2 2 设设R R是非空集合是非空集合A A上的一个等价关系，上的一个等价关系，XX，令令 xxR R=y|yXy|yX且且( (x,y)Rx,y)R 则称集合则称集合 xxR R为为x x关于关于R R的等价类，简称的等价类，简称x x的等价类，简的等价类，简记为记为xx。例：例：在上例中的等价关系在上例中的等价关系R R的三个不同等价类为：的三个不同等价类为：二、说明：二、说明：1.1.集合集合X X中的八个元素各有一个等价

26、类中的八个元素各有一个等价类; ; 2. 2. 各个等价类之间或者相等或者不相交各个等价类之间或者相等或者不相交; ; 3. 3. 所有等价类的并就等于所有等价类的并就等于X X。11,4,74722,5,85833,66RRRRRRRR三、性质三、性质定理定理1 1 设设R R是非空集合是非空集合X X上的等价关系，上的等价关系，XX ，则，则(1)(1) xxR R且且 xxR RX X; ;(2) (2) 若若( (R R, ,则则 xxR R=yyR R; ; (3) (3) 若若( ( R R, , 则则 xxR RyyR R=;=;(4) (4) xxR R=X=X。6.3 6.3

27、 商集商集定义定义3 3 设设R R是非空集合是非空集合X X上的一个等价关系，以上的一个等价关系，以R R的不相的不相交的等价类为元素构成的集合称为交的等价类为元素构成的集合称为X X在在R R下的商集，下的商集，简称为简称为X X的商集，记为的商集，记为X/RX/R，即，即X/R=X/R=xxR R|xX|xX 。例：例：1.1.在上例中，在上例中，X X在在R R下的商集是：下的商集是： X/R=1,2,3=1,4,7,2,5,8,3,6X/R=1,2,3=1,4,7,2,5,8,3,6。2.2.非空集合非空集合X X上的全关系上的全关系E EX X是是X X上的等价关系上的等价关系,

28、,XX, ,有有 xxE E=X, =X, 商集商集 X/E=XX/E=X。3. X3. X上的恒等关系上的恒等关系I IX X是等价关系，是等价关系，XX, ,有有 xxI IX X=x,=x, 商集商集X/I=X/I=xxI I| | XX = =x|x| XX 。6.4 6.4 划分划分一、定义一、定义定义定义4 4 设设X X是非空集合，若是非空集合，若X X的一些非空子集形成的集的一些非空子集形成的集族族=A Ai i iIiI满足下列条件：满足下列条件： (1) (1) I I，若，若lrlr, , 则则A Al lArAr=;=; (2) A (2) Ai i=X=X。 则称则称

29、为为X X的一个划分，的一个划分，中元素中元素A Ai i为为的划分块。的划分块。二、说明：二、说明：(1)(1)集合集合A A的商集就是集合的商集就是集合A A的一个划分；的一个划分；(2)(2)当划分块的块数有限时，将划分当划分块的块数有限时，将划分写成：写成： =1 1 , ,2 2, , , n n ，n n为块数。为块数。 显然，对于有限集合来说，它的划分块数一定是显然，对于有限集合来说，它的划分块数一定是有限的。有限的。(3)(3)但对无限集合划分块数不一定有限。但对无限集合划分块数不一定有限。 例：例：1.1.给定整数集合给定整数集合Z Z的一个划分：的一个划分： 1 1=E,O

30、,=E,O,其中其中E E是偶数集，是偶数集，O O是奇数集是奇数集; ; I I的另外划分的另外划分: : 2 2=Z=Z+ +,Z,Z- -,0;,0; 3 3=,-2,-1,0,1,2,-2,-1,0,1,2, 等等。等等。2. 2. 考虑集合考虑集合A=A=a,b,c,da,b,c,d 上的子集族：上的子集族： 1 1=a,b,c,da,b,c,d; 2 2=a,b,c,da,b,c,d; 3 3=a,b,c,da,b,c,d都是都是A A上的划分。上的划分。 a,b,c,da,b,c,d 都是都是1 1的划分块；的划分块； a,ba,b 、 c,dc,d 和和 a,b,c,da,b,

31、c,d 分别是分别是2 2和和3 3的划的划分块。分块。 4 4=a,b,c,a,da,b,c,a,d 5 5=a,b,da,b,d等都不是等都不是A A的划分。的划分。6.5 6.5 等价关系与划分之间的联系等价关系与划分之间的联系 它们之间的关系可以用三个定理来说明。它们之间的关系可以用三个定理来说明。定理定理1 1 对非空集合对非空集合X X上的任意一个等价关系上的任意一个等价关系R R，X X的商的商集集X/RX/R就是就是X X的划分。的划分。 这个划分称为由等价关系这个划分称为由等价关系R R诱导出来的诱导出来的X X的划分，的划分，记为记为R R。说明：说明：X X上的等价关系上

32、的等价关系R R可以诱导出可以诱导出X X上的一个划分，上的一个划分，那么给定那么给定X X上的一个划分是否可以诱导出上的一个划分是否可以诱导出X X上的一个等上的一个等价关系呢？价关系呢？定理定理2 2 设设是非空集合是非空集合X X上的一个划分，令上的一个划分，令X X上的关系上的关系为为R R如下：如下： R R=(=(x,y)|x,yXx,y)|x,yX且且x x和和y y属于的同一个属于的同一个划分块划分块, ,则则R R为为X X上的等价关系。这个等价关系称为上的等价关系。这个等价关系称为由划分由划分诱导出的诱导出的X X上的等价关系。并且上的等价关系。并且 R R= =i ii

33、i，i i。定理定理3 3 对非空集合对非空集合X X上的一个划分上的一个划分和和X X上的一个等价上的一个等价关系关系R R，有，有: : 诱导诱导R RR R诱导诱导。说明：说明：集合集合X X上的划分上的划分和和X X上的等价关系上的等价关系R R之间可以建之间可以建立一一对应关系。立一一对应关系。二、例题：二、例题：例例1 1 在集合在集合X=1,2,3X=1,2,3上求出尽可能多的等价关系。上求出尽可能多的等价关系。 推广：推广：X=1,2,3,4,|R|=15X=1,2,3,4,|R|=15个；个； X=1,2,3,4,5,|R|=52X=1,2,3,4,5,|R|=52个个. .

34、例例2 2 给定集合给定集合X=1,2,3,4,5X=1,2,3,4,5，找出，找出X X上的等价关系，上的等价关系，此关系此关系R R能产生划分能产生划分1,2,3,4,51,2,3,4,5，并画出关系图。，并画出关系图。 对上述三个定理的说明：对上述三个定理的说明： 1.1.集合集合X X上的任一等价关系可以唯一地诱导出上的任一等价关系可以唯一地诱导出X X上的上的一个划分；一个划分； 2.2.集合集合X X上的任一划分可以唯一地诱导出上的任一划分可以唯一地诱导出X X上的一个上的一个等价关系。等价关系。 3.X3.X上给出的一个划分与给出的一个等价关系是没上给出的一个划分与给出的一个等价

35、关系是没有什么实质区别的。有什么实质区别的。 对于一个问题中的某个关系对于一个问题中的某个关系R R可能不是等价关系。可能不是等价关系。如果如果R R很重要，希望它是一个等价关系就好了，那么很重要，希望它是一个等价关系就好了，那么可以用可以用R R的等价闭包（的等价闭包（R R的自反、对称和传递闭包），的自反、对称和传递闭包），记为记为e(Re(R) )。e(Re(R) )是是X X上包含上包含R R的所有等价关系的交。的所有等价关系的交。习题课（习题课（3 3） 例例1 1 在集合在集合A=1,2,3A=1,2,3上求出尽可能多的等价关系。上求出尽可能多的等价关系。推广：推广：A=1,2,3

36、,4, |R|=15A=1,2,3,4, |R|=15个；个； A=1,2,3,4,5,|R|=52A=1,2,3,4,5,|R|=52个。个。例例2 2 给定集合给定集合 A=1,2,3,4,5A=1,2,3,4,5，找出，找出A A上的等价关系，上的等价关系，此关系此关系R R能产生划分能产生划分1,21,2，33，4,54,5，并画出关系，并画出关系图。图。习题课（习题课（4 4） 例例1 1 R R是整数集是整数集I I上的关系，上的关系，mRnmRn定义为定义为m m2 2n n2 2，则，则 (1) (1) 证明：证明：R R是等价关系；是等价关系；(2) (2) 确定确定R R的

37、等价类。的等价类。例例2 2设设R R是是A A上的一个自反关系，证明：上的一个自反关系，证明： R R是等价关系是等价关系若若( (R R且且( (a aR R, ,则则( (b bR R 。例例3 3 设设A=1,2,3A=1,2,3，A A上的两个关系如图所示，则它们上的两个关系如图所示，则它们是否是等价关系？是否是等价关系？例例4 4 设设R R1 1,R,R2 2是是A A上的等价关系上的等价关系, ,则则R R1 1RR2 2也是也是A A上的等上的等价关系吗？价关系吗？132231例例5 5 设设R R是集合是集合A A上的一个自反的和传递的关系；上的一个自反的和传递的关系； S

38、 S是是A A上的一个关系，使得上的一个关系，使得( (a,b)Sa,b)S(a,b)R(a,b)R且且 ( (b,a)Rb,a)R。证明：。证明：S S是是A A上的等价关系。上的等价关系。例例6 6 设设R R是是A A上的二元关系，上的二元关系，S=(S=(a,b)|a,b)| cAcA, ,使得使得( (a,c)Ra,c)R且且( (c,b)Rc,b)R 。证明：若。证明：若R R是等价关系，则是等价关系，则S S 也是等价关系。也是等价关系。 说明：本题可以证明说明：本题可以证明R RS S。例例7 7 设设AA1 1,A,A2 2, ,A,An n 是集合是集合A A的划分，若的划

39、分，若A Ai iBB，1in1in，证明：，证明：AA1 1B,AB,A2 2B,B, ,A An nBB 是集合是集合ABAB的划分。的划分。例例8 8设设S=1,2,3,4,S=1,2,3,4,并设并设A AS SS,S,在在A A上定义关系上定义关系R R为为: : ( (a,b)R(c,d)a,b)R(c,d)a+ba+b= =c+dc+d。 证明证明:(:(1) 1) R R是是A A上的等价关系；上的等价关系；(2) (2) 计算计算A/RA/R。例例9 9 设设X=1,2,X=1,2,n, S=X,n, S=XX X。R R是是S S上的如下的关系：上的如下的关系： ( (I,

40、j),(k,l)SI,j),(k,l)S，( (I,j)R(k,l)I,j)R(k,l)i+ji+j= =k+lk+l。证明：。证明：（1 1）R R是等价关系；（是等价关系；（2 2）求等价类个数。）求等价类个数。例例1010设设A=1,2,3,4A=1,2,3,41,2,3,41,2,3,4，A A上的二元关系上的二元关系R R定定义为：义为：( (x,y)R(u,v)x,y)R(u,v)|x-y|x-y|=|=|u-vu-v| |，证明：，证明： (1)R(1)R是是A A上的等价关系；上的等价关系；(2)(2)确定由确定由R R对集合对集合A A的划分。的划分。例例1111设设R R1

41、 1是是A A上的等价关系，上的等价关系，R R2 2是是B B上的等价关系。在上的等价关系。在 S=AS=AB B上定义关系上定义关系R R如下：如下：(x(x1 1,y,y1 1)R(x)R(x2 2,y,y2 2) )(x(x1 1,x,x2 2) ) R R1 1且且(y(y1 1,y,y2 2) ) R R2 2证明：证明：R R是是S S上的等价关系上的等价关系。例例12 12 设设 x x1 1,x,x2 2X,X,x x1 1RxRx2 2f(xf(x1 1)=f(x)=f(x2 2) )，求，求R R等价类。等价类。 （x=fx=f-1-1(y(yi i)|f(x)=)|f(

42、x)=y yi i,y,yi iY Y ，i=1,2,ni=1,2,n）例例1313 设设X=1,2,3,Y=1,2,S=X=1,2,3,Y=1,2,S=f|f:Xf|f:XY Y 。是是S S上上的二元关系：的二元关系： f,gSf,gS，则，则fgfgI Im m(f(f)=)=I Im m(g(g) )。证明。证明: : (1) (1)是是S S上的等价关系上的等价关系; ; (2) (2)求等价类的集合。求等价类的集合。例例14 14 P113 (2)P113 (2)例例15 15 P113 (3)P113 (3)例例16 16 设设N N是自然数，定义是自然数，定义N N上的关系上的

43、关系R R如下：如下： R=(R=(x,y)|xNx,y)|xN，yNyN，x+yx+y是偶数是偶数 ，则，则 (1)(1)证明：证明：R R是一个等价关系；是一个等价关系； (2)(2)求关系求关系R R的等价类。的等价类。8 8 偏序关系与偏序集偏序关系与偏序集 序关系研究的是集合中的元素的次序，它提供了序关系研究的是集合中的元素的次序，它提供了一种比较集合中各个元素一种比较集合中各个元素“大小大小”的工具。序关系主的工具。序关系主要包括：偏序关系、拟序关系、全序关系和良序关系。要包括：偏序关系、拟序关系、全序关系和良序关系。其中最重要的是偏序关系。其中最重要的是偏序关系。8.18.1偏序

44、关系偏序关系一、定义一、定义定义定义1 1 设设R R是非空集合是非空集合A A上的一个二元关系，若上的一个二元关系，若R R同时同时具有以下三个性质：具有以下三个性质： (1)R(1)R是自反的；是自反的；(2)R(2)R是反对称的；是反对称的；(3)R(3)R是传递的。是传递的。则称则称R R是是A A上的上的偏序关系偏序关系，简称偏序，记为，简称偏序，记为“”。例：例：1.1.在集合在集合A A的的2 2A A上定义的上定义的“”、“”是偏序关是偏序关系。系。2.2.在整数集合在整数集合Z Z上的上的 “”、 “” 、“| |”是偏序关是偏序关系，系，但但“模模n n同余关系同余关系”不

45、是偏序关系。不是偏序关系。定义定义2 2 设设R R是非空集合是非空集合A A上的一个二元关系，若上的一个二元关系，若R R同时具同时具有下列性质：有下列性质：(1)R(1)R是反自反的；是反自反的；(2)R(2)R是反对称的；是反对称的；(3)R(3)R是传递的。是传递的。则称则称R R是是A A上的上的拟序关系拟序关系，记为，记为“”。例：例：1.1.在整数集合在整数集合Z Z上的上的“”，“”都是拟序关系。都是拟序关系。2.2.在集合在集合A A的的2 2A A上定义的上定义的“”, ,“”是拟序关系。是拟序关系。说明：说明：1.1.偏序关系也称弱偏序关系或半序关系；拟序关偏序关系也称弱

46、偏序关系或半序关系；拟序关系也称为强偏序关系。系也称为强偏序关系。2.2.有些书上把定义有些书上把定义2 2中的条件（中的条件（2 2）省略。）省略。3.3.证明：若证明：若R R是是A A上的拟序关系，则上的拟序关系，则R R是反对称的。是反对称的。二、偏序与拟序的联系与区别二、偏序与拟序的联系与区别定理定理1 1 设设R R是是A A上的一个二元关系，则上的一个二元关系，则(1)(1)若若R R是是A A上的偏序关系，则上的偏序关系，则RRRR0 0是是A A上的拟序关系；上的拟序关系；(2)(2)若若R R是是A A上的拟序关系，则上的拟序关系，则R RR R0 0是是A A上的偏序关系

47、。上的偏序关系。区别：区别：偏序与拟序的区别就在于一个是自反的，一个偏序与拟序的区别就在于一个是自反的，一个是反自反的。由于它们类似，因此，只要把偏序关系是反自反的。由于它们类似，因此，只要把偏序关系搞清楚了，拟序关系也就很容易搞清楚了。因此，在搞清楚了，拟序关系也就很容易搞清楚了。因此，在下面只讨论偏序关系。下面只讨论偏序关系。8.28.2偏序集偏序集定义定义3 3 设设R R的集合的集合A A上的一个偏序关系，集合上的一个偏序关系，集合A A对偏序关对偏序关系系R R形成一个二元组，记为形成一个二元组，记为(A,R)(A,R)，称，称(A,R)(A,R)为偏序集。为偏序集。例例：1.1.（

48、Z,Z,）是偏序集。）是偏序集。2.(22.(2A A, ,) )是偏序集。是偏序集。3.A3.A2,4,6,82,4,6,8，R R1 1整除关系，整除关系，R R2 2整倍数关系。整倍数关系。R R1 1=(2,2),(2,4),(2,6),(2,8),(4,4),(4,8),(6,6),(8,8),=(2,2),(2,4),(2,6),(2,8),(4,4),(4,8),(6,6),(8,8), R R2 2=(2,2),(4,2),(6,2),(8,2),(4,4),(8,4),(6,6),(8,8)=(2,2),(4,2),(6,2),(8,2),(4,4),(8,4),(6,6),

49、(8,8)。于是于是(A,R(A,R1 1),(A,R),(A,R2 2) )都是偏序集。都是偏序集。说明：说明：在一个集合上可以定义多个偏序关系，从而可在一个集合上可以定义多个偏序关系，从而可以形成多个偏序集。因此，在一个集合上定义多个偏以形成多个偏序集。因此，在一个集合上定义多个偏序关系时，一定要说明某个偏序集是对哪个关系的。序关系时，一定要说明某个偏序集是对哪个关系的。四、对偶四、对偶 集合集合A A上的偏序关系上的偏序关系“”的逆的逆“-1-1”也是也是A A上的上的偏序关系，以后用偏序关系，以后用“”表示表示“”的逆关系的逆关系“-1-1”。 若若xyxy但但xyxy，则记为，则记为

50、x xy y。称。称(A,)(A,)是是(A,)(A,)的对偶。的对偶。8.3 8.3 HasseHasse图图 利用偏序关系的良好性质，可以把它的关系图简利用偏序关系的良好性质，可以把它的关系图简化为比较简单的化为比较简单的HasseHasse图。图。 1.1. 由于偏序关系是自反的，所以在其关系图中，对由于偏序关系是自反的，所以在其关系图中，对每个顶点到自身的矢线（环）可以省略不画。每个顶点到自身的矢线（环）可以省略不画。 2. 2. 又由于偏序关系是传递的，则若又由于偏序关系是传递的，则若a,b,ca,b,c是三个不是三个不同的元素且同的元素且abab，bcbc，则，则acac。这时在关

51、系图中，。这时在关系图中，从从a a到到c c的矢线可以省去不画。的矢线可以省去不画。3. 3. 最后，若最后，若abab，abab且又不存在元素且又不存在元素c c，caca，b b使得使得acbacb，则称，则称b b是是a a的直接上元素的直接上元素(b(b覆盖覆盖a)a)。（1 1）若）若b b是是a a的直接上元素，则把代表的直接上元素，则把代表b b的点，画在代的点，画在代表表a a的点的上方且用一条边联结。的点的上方且用一条边联结。（2 2）若）若a a与与b b两个元素中，两个元素中，a a不是不是b b且且b b也不是也不是a a的直接的直接上元素，则上元素，则a a与与b

52、b之间无线联络。一般把它们画在一个之间无线联络。一般把它们画在一个水平线上。水平线上。4.4.在在HasseHasse图中，总认为方向向上的，因此不用矢线，图中，总认为方向向上的，因此不用矢线，按着以上方法画出的偏序关系图称为按着以上方法画出的偏序关系图称为HasseHasse图。图。例：例：1.1.设设A=aA=a，则，则2 2A A上定义的包含关系上定义的包含关系“”是是2 2A A上的偏序关系，其上的偏序关系，其HasseHasse图如图图如图(a)(a)所示。所示。例：例：1.1.设设A=aA=a，则，则2 2A A上定义的包含关系上定义的包含关系“”是是2 2A A上上的偏序关系，其

53、的偏序关系，其HasseHasse图如图图如图(a)(a)所示。所示。若若A=A=a,ba,b ，则，则2 2A A上定义的包含关系上定义的包含关系“”是是2 2A A上的偏上的偏序关系，其序关系，其HasseHasse图如图图如图(b)(b)所示。所示。若若A=A=a,b,ca,b,c ，则，则2 2A A上定义的包含关系上定义的包含关系“”是是2 2A A上上的偏序关系，其的偏序关系，其HasseHasse图如图图如图(c)(c)所示。所示。2.2.设设A=2,3,6,12,24,36A=2,3,6,12,24,36，容易验证，容易验证A A上的整除关系是上的整除关系是A A上的偏序关系，

54、其上的偏序关系，其HasseHasse图如图图如图(d)(d)所示。所示。 (a) (b) (c) (d) a?aa,b?ba,b,caa,bb?cb,ca,c2436326128.4 8.4 最大最大( (小小) )元素、极大元素、极大( (小小) )元元定义定义1 1 设设(A,)(A,)是一个偏序集，是一个偏序集，B BA A，则，则(1)(1)若若aB,aB,使得使得 xBxB，均有，均有xaxa，则称，则称a a为为B B的的最最大元素大元素。(2)(2)若若aB,aB,使得使得 xBxB，均有，均有ax ax ，则称，则称a a为为B B的的最最小元素小元素。(3)(3)存在存在a

55、BaB，若，若B B中没有任何元素中没有任何元素x x，满足，满足a ax x且且ax ax ，则称，则称a a为为B B的的极大元极大元。(4)(4)存在存在aBaB，若，若B B中没有任何元素中没有任何元素x x，满足，满足a ax x且且xa xa ，则称，则称a a为为B B的的极小元极小元。例例: : 集合集合A=1,2,3,4,6,12A=1,2,3,4,6,12上的整除关系上的整除关系“| |”是是A A上上偏序关系，偏序关系，HasseHasse图如图所示。图如图所示。令令 B B1 1=2,4,6,12=2,4,6,12；B B2 2=2,3,4,6=2,3,4,6 。例例:

56、 :集合集合A=1,2,3,4,6,12A=1,2,3,4,6,12上的整除关系上的整除关系“| |”是是A A上偏上偏序关系，序关系，HasseHasse图如图所示。图如图所示。令令B B1 1=2,4,6,12=2,4,6,12，则，则B B1 1最大元最大元1212，最小元，最小元2 2；B B1 1极大元极大元1212，极小元，极小元2 2。令令B B2 2=2,3,4,6=2,3,4,6 ，则，则B B2 2的最大元：的最大元：无无，最小元：，最小元：无无；B B2 2的极大元：的极大元：4 4，6 6，最小元：，最小元：2 2，3 3。说明：说明：如何区别最大如何区别最大( (小小

57、) )元与极大元与极大( (小小) )元。元。 1.B1.B的最大的最大( (小小) )元应大元应大( (小小) )于或等于于或等于B B中其它各元素中其它各元素; ;2.B2.B的极大的极大( (小小) )元应不小于元应不小于B B中其它各元素。即它大中其它各元素。即它大( (小小) )于或等于于或等于B B中的一些元素，并与中的一些元素，并与B B中另一些元素无中另一些元素无关系关系; ;3.3.最大最大( (小小) )元不一定存在，若存在必唯一元不一定存在，若存在必唯一; ;4.4.在非空集合中，极大在非空集合中，极大( (小小) )元必存在，但不一定唯一。元必存在，但不一定唯一。 8.

58、5 8.5 上上( (下下) )界、上界、上( (下下) )确界确界定义定义2 2 设设(A,)(A,)是一个偏序集，是一个偏序集，B BA A，则，则(1)(1)若存在若存在aAaA，使得，使得 xB xB ，均有，均有xaxa，则称，则称a a为为B B的上界；的上界；(2)(2)若存在若存在aAaA，使得，使得 xBxB，均有，均有axax，则称，则称a a为为B B的的下界；下界； (3)(3)若若B B的一切上界元素形成的集合中有最小元素，则的一切上界元素形成的集合中有最小元素，则称此称此最小上界最小上界为为B B的的上确界上确界，记为，记为supBsupB；(4)(4)若若B B的

59、一切下界元素形成的集合中有最大元素，则的一切下界元素形成的集合中有最大元素，则称此称此最大下界最大下界为为B B的的下确界下确界，记为，记为infBinfB。例：例：集合集合A=2,3,4,6,9,12,18A=2,3,4,6,9,12,18，A A上整除关系上整除关系“| |”是是偏序关系，其偏序关系，其HasseHasse图如图所示。图如图所示。令令 B1=2,4B1=2,4；B2=4,6,9B2=4,6,9；B3=2,3B3=2,3。例：例：集合集合A=2,3,4,6,9,12,18A=2,3,4,6,9,12,18，A A上整除关系上整除关系“| |”是是偏序关系，其偏序关系，其Has

60、seHasse图如图所示。图如图所示。令令B B1 1=2,4=2,4，则，则 B B1 1的上界是：的上界是：4,124,12；上确界是：；上确界是：4 4。 B B1 1的下界是：的下界是：2 2； 下确界是：下确界是：2 2。令令B B2 2=4,6,9=4,6,9，则，则B B2 2的上界：无；上确界：无。的上界：无；上确界：无。B B2 2的下界：无；下确界：无。的下界：无；下确界：无。令令B B3 3=2,3=2,3，则，则B B3 3的上界是：的上界是：6,12,186,12,18；上确界：；上确界：6 6。B B3 3的下界是：无；的下界是：无； 下确界：无。下确界：无。121