《集合论-第三章2》由会员分享，可在线阅读，更多相关《集合论-第三章2（52页珍藏版）》请在金锄头文库上搜索。
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。2021/6/71第二章第二章 习题课（习题课（1 1）例例1 1 设设X Xa,b,ca,b,c，给出，给出X X上的一个二元关系，使其同上的一个二元关系，使其同时时不满足不满足自反性、反自反性、对称性、反对称和传递自反性、反自反性、对称性、反对称和传递性的二元关系，并画出性的二元关系，并画出R R的关系图。的关系图。例例2 2 设设A A是集合，是集合，R,SR,S XXXX且且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 2021/6/72例例4 4 设设X X是一个集合，是一个集合，|X|X|n n，求：，求： (1) X(1) X上的二元关系有多少？上的二元关系有多少？ (2) (2) X
4、 X上的自反的二元关系有多少？上的自反的二元关系有多少？ (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上上既是既是自反的自反的又是又是反自反的关系有多少？
5、反自反的关系有多少？ (7) 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) 2021/6/73 (8) X (8) X上自反的且对称的关系有多少？上自反的且对称的关系有多少？ 与与“反自反且对称关系有多少？反自反且对称关系有多少？”一样多一样多2 2(n2-n)/2(n2-n)/2 (9) X(9) X上自反的或对称的关系有多少？上自反的或对称的关系有多少？ |BC|=2|BC|=2n2-nn2-
6、n+2+2(n2+n)/2(n2+n)/2-2-2(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) R I 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-
7、3-3(n2-n)/2(n2-n)/22 2n n+2+2n n2021/6/74例例5 5 设设 A=1,2,3A=1,2,3，R R是是A A的幂集的幂集2 2A A上的二元关系且上的二元关系且 R=(a,b)|aR=(a,b)|ab b ，则，则R R不满足下列哪些性质？不满足下列哪些性质？为什么？为什么？aRb aRb a ab b (1) (1) 自反性自反性 (2) (2) 反自反性反自反性 (3) (3) 对称性对称性 (4) (4) 反对称性反对称性 (5) (5) 传递性传递性 不满足自反性、反自反性、反对称性、传递性不满足自反性、反自反性、反对称性、传递性 例例6 6 设设
8、R R是复数集合是复数集合C C上的一个二元关系且满足上的一个二元关系且满足xRyxRyx-y=a+bix-y=a+bi，a,ba,b为非负整数，试确定为非负整数，试确定R R的性质。的性质。若若a=b=0a=b=0时，时，R=I(R=I(恒等关系恒等关系) )，满足满足自反性、对称、反自反性、对称、反对称性、传递性对称性、传递性若若a a、b b不全为零不全为零0 0时，时，满足反满足反自反性、反对称性自反性、反对称性2021/6/755 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的二元关系，则的二元关系，则nmnm矩阵矩阵M MR R=(r=(rijij) )n n
10、m m称为称为A A到到B B的二元关系的二元关系R R的关系矩阵，简称关的关系矩阵，简称关系矩阵。其中系矩阵。其中2021/6/76(2) (2) 若若R R是是A A上的关系，则上的关系，则nnnn矩阵称为矩阵称为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)，则关系则关系“”的关系矩阵为的关系矩阵为：2021/6/77三、关系矩阵包含关系的信息三、关系矩阵包含关系的信息 设设M MR R是关系是关系R R的关系矩阵，则的关系矩阵，则 (1) R(1) R是自反的是自反的M MR R的对称线上的元素全为的对称线上的元素全为1 1。 (2) R(2) R是反自反的是反自反的M MR R对称线上的元素全为对称线上的元素全为0 0。 (3) R(3) R是对称的是对称的MRMR是对称的。是对称的。 (4) R(4) R是反对称的是反对称的若若ij,ij,则则r r
12、ijij与与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 R R R (6) R (6) R-1-1的关系矩阵为的关系矩阵为M MR RT T。2021/6/785.25.2关系图关系图定义定义1 1 设设A A，B B为有限集合，为有限集合，A=aA=a1 1,a,a2 2, ,a,an n, , B=bB=b1 1,b,b2 2, ,b,bm m,R,R是是A A到到B B的一个二元
13、关系。的一个二元关系。 首先在平面上用首先在平面上用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到作一条带箭头的线指到作一条带箭头的线指向顶点向顶点b bj j ； 若若(a(ai i,b,bj j) ) R R ，则，则
14、a ai i与与b bj j之间没有线联结。之间没有线联结。 用这种方法构造的图形称为用这种方法构造的图形称为A A到到B B的关系的关系R R的关系图，的关系图，简称关系图。简称关系图。 2021/6/79当当A AB B时时，A A上的关系上的关系R R的关系图画法类似。把的关系图画法类似。把A A中的中的每一个元素在平面上用点表示，并在这些点旁边标上每一个元素在平面上用点表示，并在这些点旁边标上元素的名字。元素的名字。 若若(a(ai i,b,bj j) )R R，则从代表，则从代表a ai i的点的点画画一条带箭头的一条带箭头的线指向代表线指向代表a aj j的点。的点。 若若(a(a
15、i 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画在画在右边。右边。2021/6/7102.2.例例(1)(1)设设A=1,2,3,4,B=a,b,cA=1,2,3,4,B=a,b,c
16、，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),(3,3),(4,4)，则，则R R的关系图如图的关系图如图2 2所示。所示。 图图1 图图22021/6
17、/711二、关系图包含关系的所有信息二、关系图包含关系的所有信息(1) R(1) R是自反的是自反的 R R的关系图的每个顶点都有一个环。的关系图的每个顶点都有一个环。(2) R(2) R是反自反的是反自反的 R R的关系图的每个顶点都没有环。的关系图的每个顶点都没有环。(3) R(3) R是对称的是对称的在在R R的关系图中，若两个不同的顶点的关系图中，若两个不同的顶点间有弧，则必有方向相反的两条弧（对称弧）。间有弧，则必有方向相反的两条弧（对称弧）。(4) R(4) R是反对称是反对称在在R R的关系图中，若两个不同的顶点的关系图中，若两个不同的顶点之间有弧，则弧只有一条。之间有弧，则弧只
18、有一条。(5) R(5) R是传递的是传递的在在R R的关系图中，任意从某点沿箭头的关系图中，任意从某点沿箭头所指的方向经过二步走到另一点，则从该点必能一步走所指的方向经过二步走到另一点，则从该点必能一步走到另一点。到另一点。2021/6/7125.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。即。即 M MR RM MS S=(r=(rijijssijij) )。其中，其中，
20、0 00=0,00=0,01=11=10=10=11 1。 运算是取最大运算是取最大 2021/6/713（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是是npnp，M MS S是是pmpm阶的布尔矩阵，定义阶的布尔矩阵，定义M MR R与与M MS
21、 S的的“布尔乘法布尔乘法”运算运算“”,”,令令M MR RM MS S=M=MT T=(t=(tijij) )nmnm，则则“”“”运算是先取最小，再取最大运算是先取最小，再取最大 2021/6/714二、求二、求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。三、闭包的运算三、闭包的运算(1)M(1)Mr(R)r(R)=M=MR RM MI I； r(R)=RIr(R)=RI(2)M(2)Ms(R)s(R)=M=MR RM MR
22、 RT T； s(R)=RRs(R)=RR-1-1(3)M(3)MR+R+=M=Mt(R)t(R)=M=MR RM MR R2 2M MR Rn n。 R R+ +=t(R)=RR=t(R)=RR2 2RRn n 2021/6/7156 6 等价关系与划分等价关系与划分 内容：等价关系、等价类、划分、等价关系与划分的关系内容：等价关系、等价类、划分、等价关系与划分的关系6.1 6.1 等价关系等价关系一、定义一、定义定义定义1 1 设设R R是非空集合是非空集合A A上的二元关系，若上的二元关系，若R R同时具有同时具有以下三个性质：以下三个性质： (1)R(1)R是自反的；是自反的；(2)R
23、(2)R是对称的；是对称的；(3)R(3)R是传递的。是传递的。则称则称R R是是A A上的等价关系，记为上的等价关系，记为“”。 R R是等价关系是等价关系二、例：二、例：2021/6/716二、例：二、例：1.1.平面上三角形集合中，三角形的相似关系，全等关平面上三角形集合中，三角形的相似关系，全等关系都是等价关系。系都是等价关系。2.2.实数集上实数集上n n阶方阵集合中，矩阵的相似、正交关系也阶方阵集合中，矩阵的相似、正交关系也是等价关系。是等价关系。3.3.恒等关系和全关系是等价关系。恒等关系和全关系是等价关系。4. 4. 定义在人的集合上的定义在人的集合上的 “年龄相等年龄相等”是
24、等价关系，是等价关系，但但“相互认识相互认识”、“同学同学”、 “朋友朋友”关系都不是等关系都不是等价关系。价关系。5.5.整数整数Z Z上的上的“相等相等”、“模模n n同余同余”关系都是等价关关系都是等价关系。系。 设设X=1,2,X=1,2,7,8,7,8，R=(x,y)|x,yXR=(x,y)|x,yX且且x=y(mod3)x=y(mod3)，其中其中x=y(mod3) x=y(mod3) 表示表示x-yx-y可以被可以被3 3整除，称整除，称R R为为X X上的模上的模3 3同余关系，则同余关系，则R R是是X X上的等价关系。上的等价关系。2021/6/7176.2 6.2 等价类
25、等价类一、定义一、定义定义定义2 2 设设R R是非空集合是非空集合A A上的一个等价关系，上的一个等价关系， x x x xXX，令，令xxR R=y|yX=y|yX且且(x,y)R (x,y)R 则称集合则称集合xxR R为为x x关于关于R R的等价类，简称的等价类，简称x x的等价类，简的等价类，简记为记为xx。例：例：在上例中的等价关系在上例中的等价关系R R的三个不同等价类为：的三个不同等价类为：二、说明：二、说明：1.1.集合集合X X中的八个元素各有一个等价类中的八个元素各有一个等价类; ; 2. 2. 各个等价类之间或者相等或者不相交各个等价类之间或者相等或者不相交; ; 3
26、. 3. 所有等价类的并就等于所有等价类的并就等于X X。2021/6/718三、性质三、性质定理定理1 1 设设R R是非空集合是非空集合X X上的等价关系，上的等价关系， x,yx,yx,yx,yXX ，则，则(1)(1) xxR R且且 xxR R X X; ;(2) (2) 若若( (x,y)x,y)x,y)x,y)R R, ,则则 xxR R=yyR R; ; (3) (3) 若若( (x,y)x,y)x,y)x,y) R R, , 则则 xxR RyyR R=;=;(4) (4) xxR R=X=X。6.3 6.3 商集商集定义定义3 3 设设R R是非空集合是非空集合X X上的一
27、个等价关系，以上的一个等价关系，以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。2021/6/7192.2.非空集合非空集合X X上的全关系上的全关系E EX X是是X X上的等价关系上的等价关系, , x x x xX,X,有有xxE E=X,
28、=X, 商集商集 X/E=XX/E=X。3. X3. X上的恒等关系上的恒等关系I IX X是等价关系，是等价关系， x x x xX,X,有有xxI IX X=x,=x, 商集商集X/I=xX/I=xI I| |x x x xX =x|X =x|x x x xXX。6.4 6.4 划分划分一、定义一、定义定义定义4 4 设设X X是非空集合，若是非空集合，若X X的一些非空子集形成的集族的一些非空子集形成的集族=A=Ai i iIiI满足下列条件：满足下列条件： (1) (1) l,rl,rl,rl,rI I，若，若lr, lr, 则则A Al lAr=;Ar=; (2) A (2) Ai
29、i=X=X。 则称则称为为X X的一个划分，的一个划分，中元素中元素A Ai i为为的划分块。的划分块。2021/6/720二、说明：二、说明：(1)(1)集合集合A A的商集就是集合的商集就是集合A A的一个划分；的一个划分；(2)(2)当划分块的块数有限时，将划分当划分块的块数有限时，将划分写成：写成： =1 1 , ,2 2, , n n ，n n为块数。为块数。 显然，对于有限集合来说，它的划分块数一定是显然，对于有限集合来说，它的划分块数一定是有限的。有限的。(3)(3)但对无限集合划分块数不一定有限。但对无限集合划分块数不一定有限。 例：例：1.1.给定整数集合给定整数集合Z Z的
30、一个划分：的一个划分： 1 1=E,O,=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, 等等。等等。2021/6/7212. 2. 考虑集合考虑集合A=a,b,c,dA=a,b,c,d上的子集族：上的子集族： 1 1=a,b,c,d;=a,b,c,d; 2 2=a,b,c,d;=a,b,c,d; 3 3=a,b,c,d=a,b,c,d都是都是A A上的划分。上的划分。 a,b,c,da,b,c,d都是都是1 1的划分块；的划分块
31、； a,ba,b、c,dc,d和和a,b,c,da,b,c,d分别是分别是2 2和和3 3的划的划分块。分块。 4 4=a,b,c,a,d=a,b,c,a,d 5 5=a,b,d=a,b,d等都不是等都不是A A的划分。的划分。6.5 6.5 等价关系与划分之间的联系等价关系与划分之间的联系 它们之间的关系可以用三个定理来说明。它们之间的关系可以用三个定理来说明。2021/6/722定理定理1 1 对非空集合对非空集合X X上的任意一个等价关系上的任意一个等价关系R R，X X的商的商集集X/RX/R就是就是X X的划分。的划分。 这个划分称为由等价关系这个划分称为由等价关系R R诱导出来的诱
32、导出来的X X的划分，的划分，记为记为R R。说明：说明：X X上的等价关系上的等价关系R R可以诱导出可以诱导出X X上的一个划分，上的一个划分，那么给定那么给定X X上的一个划分是否可以诱导出上的一个划分是否可以诱导出X X上的一个等上的一个等价关系呢？价关系呢？定理定理2 2 设设是非空集合是非空集合X X上的一个划分，令上的一个划分，令X X上的关系上的关系为为R R如下：如下： R R=(x,y)|x,yX=(x,y)|x,yX且且x x和和y y属于的同一个属于的同一个划分块划分块, ,则则R R为为X X上的等价关系。这个等价关系称为上的等价关系。这个等价关系称为由划分由划分诱导
33、出的诱导出的X X上的等价关系。并且上的等价关系。并且 R R= =i ii i，i i。2021/6/723定理定理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|
34、=15个；个； X=1,2,3,4,5,|R|=52X=1,2,3,4,5,|R|=52个个. .例例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，并画出关系图。，并画出关系图。 2021/6/724对上述三个定理的说明：对上述三个定理的说明： 1.1.集合集合X X上的任一等价关系可以唯一地诱导出上的任一等价关系可以唯一地诱导出X X上的上的一个划分；一个划分； 2.2.集合集合X X上的任一划分可以唯一地诱导出上的任一划分可以唯一地诱导出X X上的
35、一个上的一个等价关系。等价关系。 3.X3.X上给出的一个划分与给出的一个等价关系是没有上给出的一个划分与给出的一个等价关系是没有什么实质区别的。什么实质区别的。 对于一个问题中的某个关系对于一个问题中的某个关系R R可能不是等价关系。可能不是等价关系。如果如果R R很重要，希望它是一个等价关系就好了，那么可很重要，希望它是一个等价关系就好了，那么可以用以用R R的等价闭包（的等价闭包（R R的自反、对称和传递闭包），记的自反、对称和传递闭包），记为为e(R)e(R)。e(R)e(R)是是X X上包含上包含R R的所有等价关系的交。的所有等价关系的交。2021/6/725习题课（习题课（3 3
36、） 例例1 1 在集合在集合A=1,2,3A=1,2,3上求出尽可能多的等价关系。上求出尽可能多的等价关系。推广：推广：A=1,2,3,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，并画出关系，并画出关系图。图。2021/6/726习题课（习题课（4 4） 例例1 1 R R是整数集是整数集I I上的关系，上的
37、关系，mRnmRn定义为定义为m m2 2n n2 2，则，则 (1) (1) 证明：证明：R R是等价关系；是等价关系；(2) (2) 确定确定R R的等价类。的等价类。例例2 2设设R R是是A A上的一个自反关系，证明：上的一个自反关系，证明： R R是等价关系是等价关系若若( (a,b)a,b)a,b)a,b)R R且且(a(a,c),c),c),c)R,R,则则(b(b,c),c),c),c)R R 。例例3 3 设设A=1,2,3A=1,2,3，A A上的两个关系如图所示，则它们是上的两个关系如图所示，则它们是否是等价关系？否是等价关系？例例4 4 设设R R1 1,R,R2 2是
38、是A A上的等价关系上的等价关系, ,则则R R1 1RR2 2也是也是A A上的等价上的等价关系吗？关系吗？2021/6/727例例5 5 设设R R是集合是集合A A上的一个自反的和传递的关系；上的一个自反的和传递的关系； S S是是A A上的一个关系，使得上的一个关系，使得(a,b)S(a,b)S(a,b)R(a,b)R且且 (b,a)R(b,a)R。证明：。证明：S S是是A A上的等价关系。上的等价关系。例例6 6 设设R R是是A A上的二元关系，上的二元关系，S=(a,b)|S=(a,b)| cA,cA,使得使得(a,c)R(a,c)R且且(c,b)R(c,b)R。证明：若。证明
39、：若R R是等价关系，则是等价关系，则S S 也是等价关系。也是等价关系。 说明：本题可以证明说明：本题可以证明R RS S。例例7 7 设设AA1 1,A,A2 2, ,A,An n 是集合是集合A A的划分，若的划分，若A Ai iBB，1in1in，证明：，证明：AA1 1B,AB,A2 2B,B,A,An nBB是集合是集合ABAB的划分。的划分。2021/6/728例例8 8设设S=1,2,3,4,S=1,2,3,4,并设并设A ASS,SS,在在A A上定义关系上定义关系R R为为: : (a,b)R(c,d) (a,b)R(c,d)a+b=c+da+b=c+d。 证明证明:(:(
40、1) 1) R R是是A A上的等价关系；上的等价关系；(2) (2) 计算计算A/RA/R。例例9 9 设设X=1,2,X=1,2,n, S=XX,n, S=XX。R R是是S S上的如下的关系：上的如下的关系： (I,j),(k,l)S(I,j),(k,l)S，(I,j)R(k,l)(I,j)R(k,l)i+j=k+li+j=k+l。证明：。证明：（1 1）R R是等价关系；（是等价关系；（2 2）求等价类个数。）求等价类个数。例例1010设设A=1,2,3,41,2,3,4A=1,2,3,41,2,3,4，A A上的二元关系上的二元关系R R定义定义为：为：(x,y)R(u,v)(x,y
41、)R(u,v)|x-y|=|u-v|x-y|=|u-v|，证明：，证明： (1)R(1)R是是A A上的等价关系；上的等价关系；(2)(2)确定由确定由R R对集合对集合A A的划分。的划分。例例1111设设R R1 1是是A A上的等价关系，上的等价关系，R R2 2是是B B上的等价关系。在上的等价关系。在 S=ABS=AB上定义关系上定义关系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上的等价关系上的等价关系。2021
42、/6/729例例12 12 设设f :Xf :Xf :Xf :XY Y Y Y，定义定义定义定义X X X X上的等价关系上的等价关系上的等价关系上的等价关系R R R R如下：如下：如下：如下： 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)=y)|f(x)=yi i,y,yi iYY，i=1,2,ni=1,2,n）例例1313 设设X=1,2,3,Y=1,2,S=f|f:XX=1,2,3,Y=1,2,S=f|f:XYY。是是S S上上的二元关系：的
43、二元关系： f,gSf,gS，则，则fgfgI Im m(f)=I(f)=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上的关系上的关系R R如下：如下： R=(x,y)|xNR=(x,y)|xN，yNyN，x+yx+y是偶数是偶数 ，则，则 (1)(1)证明：证明：R R是一个等价关系；是一个等价关系； (2)(2)求关系求关系R R的等价类。
44、的等价类。2021/6/7308 8 偏序关系与偏序集偏序关系与偏序集 序关系研究的是集合中的元素的次序，它提供了序关系研究的是集合中的元素的次序，它提供了一种比较集合中各个元素一种比较集合中各个元素“大小大小”的工具。序关系主的工具。序关系主要包括：偏序关系、拟序关系、全序关系和良序关系。要包括：偏序关系、拟序关系、全序关系和良序关系。其中最重要的是偏序关系。其中最重要的是偏序关系。8.18.1偏序关系偏序关系一、定义一、定义定义定义1 1 设设R R是非空集合是非空集合A A上的一个二元关系，若上的一个二元关系，若R R同时具同时具有以下三个性质：有以下三个性质： (1)R(1)R是自反的
45、；是自反的；(2)R(2)R是反对称的；是反对称的；(3)R(3)R是传递的。是传递的。则称则称R R是是A A上的上的偏序关系偏序关系，简称偏序，记为，简称偏序，记为“”。2021/6/731例：例：1.1.在集合在集合A A的的2 2A A上定义的上定义的“ ”、“”是偏序关系。是偏序关系。2.2.在整数集合在整数集合Z Z上的上的 “”、 “” 、“| |”是偏序是偏序关系，关系，但但“模模n n同余关系同余关系”不是偏序关系。不是偏序关系。定义定义2 2 设设R R是非空集合是非空集合A A上的一个二元关系，若上的一个二元关系，若R R同时具同时具有下列性质：有下列性质：(1)R(1)
46、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.偏序关系也称弱偏序关系或半序关系；拟序关偏序关系也称弱偏序关系或半序关系；拟序关系也称为强偏序关系。系也称为强偏序关系。2.2.有些书上把定义有些书上把定义2 2中的条件（中的条件（2 2）省略。）省略。3.3.证明：若证明
47、：若R R是是A A上的拟序关系，则上的拟序关系，则R R是反对称的。是反对称的。2021/6/732二、偏序与拟序的联系与区别二、偏序与拟序的联系与区别定理定理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上的偏序关系。上的偏序关系。区别：区别：偏序与拟序的区别就在于一个是自反的，一个偏序与拟序的区别就在于一个是自反的，一个是反自反的。由于它们类似，因此，只要把偏序
48、关系是反自反的。由于它们类似，因此，只要把偏序关系搞清楚了，拟序关系也就很容易搞清楚了。因此，在搞清楚了，拟序关系也就很容易搞清楚了。因此，在下面只讨论偏序关系。下面只讨论偏序关系。2021/6/7338.28.2偏序集偏序集定义定义3 3 设设R R的集合的集合A A上的一个偏序关系，集合上的一个偏序关系，集合A A对偏序关对偏序关系系R R形成一个二元组，记为形成一个二元组，记为(A,R)(A,R)，称，称(A,R)(A,R)为偏序集。为偏序集。例例：1.1.（Z,Z,）是偏序集。）是偏序集。2.(22.(2A A, , ) )是偏序集。是偏序集。3.A3.A2,4,6,82,4,6,8，
49、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),(8,8)。于是于是(A,R(A,R1 1),(A,R),(A,R2 2) )都是偏序集。都是偏序集。说明：说明：在一个集合上可
50、以定义多个偏序关系，从而可在一个集合上可以定义多个偏序关系，从而可以形成多个偏序集。因此，在一个集合上定义多个偏以形成多个偏序集。因此，在一个集合上定义多个偏序关系时，一定要说明某个偏序集是对哪个关系的。序关系时，一定要说明某个偏序集是对哪个关系的。2021/6/734四、对偶四、对偶 集合集合A A上的偏序关系上的偏序关系“”的逆的逆“-1-1”也是也是A A上的上的偏序关系，以后用偏序关系，以后用“”表示表示“”的逆关系的逆关系“-1-1”。 若若xyxy但但xyxy，则记为，则记为x xy y。称。称(A,)(A,)是是(A,)(A,)的对偶。的对偶。8.3 Hasse8.3 Hasse
51、图图 利用偏序关系的良好性质，可以把它的关系图简利用偏序关系的良好性质，可以把它的关系图简化为比较简单的化为比较简单的HasseHasse图。图。 1.1. 由于偏序关系是自反的，所以在其关系图中，对由于偏序关系是自反的，所以在其关系图中，对每个顶点到自身的矢线（环）可以省略不画。每个顶点到自身的矢线（环）可以省略不画。 2. 2. 又由于偏序关系是传递的，则若又由于偏序关系是传递的，则若a,b,ca,b,c是三个不是三个不同的元素且同的元素且abab，bcbc，则，则acac。这时在关系图中，。这时在关系图中，从从a a到到c c的矢线可以省去不画。的矢线可以省去不画。2021/6/7353
52、. 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 b之间无线联络。一般把它们画在一个之间无线联络。一般把它们画在一个水平线上。水平线上。4
53、.4.在在HasseHasse图中，总认为方向向上的，因此不用矢线，图中，总认为方向向上的，因此不用矢线，按着以上方法画出的偏序关系图称为按着以上方法画出的偏序关系图称为HasseHasse图。图。例：例：1.1.设设A=aA=a，则，则2 2A A上定义的包含关系上定义的包含关系“ ”是是2 2A A上上的偏序关系，其的偏序关系，其HasseHasse图如图图如图(a)(a)所示。所示。2021/6/736例：例：1.1.设设A=aA=a，则，则2 2A A上定义的包含关系上定义的包含关系“ ”是是2 2A A上上的偏序关系，其的偏序关系，其HasseHasse图如图图如图(a)(a)所示。
54、所示。若若A=a,bA=a,b，则，则2 2A A上定义的包含关系上定义的包含关系“ ”是是2 2A A上的偏上的偏序关系，其序关系，其HasseHasse图如图图如图(b)(b)所示。所示。若若A=a,b,c A=a,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上的偏序关系，其上的偏序关系，其HasseHasse图如图图如图(d)(d
55、)所示。所示。 (a) (b) (c) (d) 2021/6/7378.4 8.4 最大最大( (小小) )元素、极大元素、极大( (小小) )元元定义定义1 1 设设(A,)(A,)是一个偏序集，是一个偏序集，B B A A，则，则(1)(1)若若 aB,aB,使得使得 xBxB，均有，均有xaxa，则称，则称a a为为B B的的最大最大元素元素。(2)(2)若若 aB,aB,使得使得 xBxB，均有，均有ax ax ，则称，则称a a为为B B的的最小最小元素元素。(3)(3)存在存在aBaB，若，若B B中没有任何元素中没有任何元素x x，满足，满足a ax x且且ax ax ，则称，则
56、称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 。2021/6/738例例: :集合集合A=1,2,3,4,6,12A=1,2,3,4,6,12上的整除关系上的
57、整除关系“| |”是是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。说明：说明：如何区别最大如何区别最大( (小小) )元与极大元与极大( (小小) )元。元。 1.B1.B的最大的最大( (小小)
58、 )元应大元应大( (小小) )于或等于于或等于B B中其它各元素中其它各元素; ;2.B2.B的极大的极大( (小小) )元应不小于元应不小于B B中其它各元素。即它大中其它各元素。即它大( (小小) )于或等于于或等于B B中的一些元素，并与中的一些元素，并与B B中另一些元素无关系中另一些元素无关系; ;3.3.最大最大( (小小) )元不一定存在，若存在必唯一元不一定存在，若存在必唯一; ;4.4.在非空集合中，极大在非空集合中，极大( (小小) )元必存在，但不一定唯一。元必存在，但不一定唯一。 2021/6/7398.5 8.5 上上( (下下) )界、上界、上( (下下) )确界
59、确界定义定义2 2 设设(A,)(A,)是一个偏序集，是一个偏序集，B B A 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的一切下界元素形成的集合中有最大元素，则的一切下界元素形成的集合
60、中有最大元素，则称此称此最大下界最大下界为为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。2021/6/740例：例：集合集合A=2,3,4,6,9,12,18A=2,3,4,6,9,12,18，A A上整除关系上整除关系“| |”是偏序关系，其是偏序关系，其HasseHasse图如图所示。图如图所示。令令
61、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的下界是：无；的下界是：无； 下确界：无。下确界：无。1218964232021/6/741说明：说明
62、：1.B1.B的上的上( (下下) )界和上界和上( (下下) )确界可能在确界可能在B B中中, ,可能可能不在不在B B中中, ,但一定在但一定在A A中。中。 2.2.上上( (下下) )界不一定存在，若存在不一定唯一。界不一定存在，若存在不一定唯一。 3.3.上上( (下下) )确界不一定存在，若存在必唯一。确界不一定存在，若存在必唯一。 由上面的讨论可知，对集合由上面的讨论可知，对集合A A上的偏序关系上的偏序关系“”而言，一般说来，只是对而言，一般说来，只是对A A中的部分元素才有此关系，中的部分元素才有此关系，即即xyxy与与yxyx可以同时不成立。可以同时不成立。 但若对于但若
63、对于A A中的两个特定的元素中的两个特定的元素a a和和b b，不是，不是abab就是就是baba，则这时说，则这时说a a与与b b是可以比较是可以比较“大小大小”的两个的两个元素，否则就说元素，否则就说a a与与b b不能比较不能比较“大小大小”。 若某个集合中任意两个元素均可以比较若某个集合中任意两个元素均可以比较“大小大小”，则称这样的集合为全序集合。，则称这样的集合为全序集合。2021/6/7428.58.5全序关系与全序集全序关系与全序集定义定义1 1设设(A,)(A,)是偏序集，若是偏序集，若 x,yx,yx,yx,yAA，xyxy与与yxyx至至少有一个成立，则称偏序关系少有一
64、个成立，则称偏序关系“”为为A A上的上的全序关系全序关系，或称为线性序关系。具有全序关系的集合或称为线性序关系。具有全序关系的集合A A称为称为全序集全序集或线性序集，记为或线性序集，记为(A,)(A,)。说明：说明：偏序集与全序集的主要区别就在于：全序集中偏序集与全序集的主要区别就在于：全序集中任意两个元素均可以比较任意两个元素均可以比较“大小大小”，而在偏序集中，而在偏序集中，则未必能比较则未必能比较“大小大小”。例：例：1.N1.N上的上的 “”关系是全序关系，关系是全序关系，所以所以(N,)(N,)是全序集。是全序集。 2.A=,a,a,b,a,b,c2.A=,a,a,b,a,b,c
65、上上的的“”是全序关系，是全序关系，(A,(A, ) )是是全序集。全序集。4321a,b,ca,ba2021/6/7433. N3. N上的整除关系不是全序关系。上的整除关系不是全序关系。4.4.非空集合非空集合A A的幂集的幂集2 2A A上的包含关系也不是全序关系。上的包含关系也不是全序关系。8.68.6链与反链链与反链定义定义2 2 设设(A,)(A,)是一个偏序集，是一个偏序集，B B A A，则，则 (1)(1)若若 x,yx,yx,yx,yBB，xyxy与与yxyx必有一个成立，则称必有一个成立，则称B B为为A A的一个的一个链链，B B中元素的个数称为链的长度。中元素的个数称
66、为链的长度。 (2)(2)若若 x,yx,yx,yx,yBB，xyxy与与yxyx均不成立，则称均不成立，则称B B为为A A的一的一个个反链反链，B B中元素的个数称为反链的长度。中元素的个数称为反链的长度。例：例：在在A=2,3,4,6,9,12,18A=2,3,4,6,9,12,18上定义的上定义的“| |”，形成一，形成一个偏序集个偏序集(A,(A,| |) )。HasseHasse图如图所示。其中图如图所示。其中2,4,12,3,6,18,3,9,182,4,12,3,6,18,3,9,18都是链。都是链。4,6,9,12,18,4,9,2,34,6,9,12,18,4,9,2,3是
67、反链。是反链。说明：说明：对于全序集对于全序集(A,)(A,)，显然，显然A A是链，是链，A A的任意子集也都是链的任意子集也都是链, ,但偏序集未必。但偏序集未必。1218964232021/6/744定理定理1 1 设设(A,)(A,)是一个偏序集，若是一个偏序集，若A A中最长链的长度为中最长链的长度为n n，则，则A A的全部元素可以被分成的全部元素可以被分成n n个互不相交的反链的并。个互不相交的反链的并。证：证：对对n n进行归纳证明。进行归纳证明。当当n=1n=1时，时，A A本身就是一条反链，定理结论显然成立。本身就是一条反链，定理结论显然成立。假设假设n=kn=k时，结论成
68、立。时，结论成立。当当n=kn=k1 1时时, ,令令M M为为A A中所有极大元的集合，显然中所有极大元的集合，显然M M是一是一条反链。而且条反链。而且AMAM中最长链的长度为中最长链的长度为k k，由归纳假设可，由归纳假设可把把AMAM分成分成k k个互不相交反链的并。再加上反链个互不相交反链的并。再加上反链M M，则，则A A可分成可分成k k1 1条反链的并。条反链的并。说明：说明：这个定理称为偏序集的分解定理，这是组合数这个定理称为偏序集的分解定理，这是组合数学中三大存在定理之一，有广泛的应用。学中三大存在定理之一，有广泛的应用。2021/6/745推论推论: :设设(A,)(A,
69、)是一个偏序集是一个偏序集,|X|=mn+1,|X|=mn+1,则则A A中或存在一中或存在一条长至少为条长至少为m+1(n+1)m+1(n+1)的反链，或存在一条长至少为的反链，或存在一条长至少为n n1(m+1)1(m+1)的链。的链。证：证：假设结论不成立，则假设结论不成立，则A A中每个链长度均为中每个链长度均为n n，而且，而且每个反链的长度均每个反链的长度均m m。 由定理可知，由定理可知，A A可分解成可分解成n n个互不相交反链的并，并个互不相交反链的并，并且每个反链长度均且每个反链长度均m m，所以，所以A A中最多有中最多有m mn n个元素，这个元素，这与题设矛盾，故推论
70、得证。与题设矛盾，故推论得证。例题：例题：证明：每个由证明：每个由n n2 2+1+1个实数组成的数列中必有一个个实数组成的数列中必有一个长至少为长至少为n+1n+1的不减子序列，或有一个长至少为的不减子序列，或有一个长至少为n+1n+1的不的不增子序列。增子序列。2021/6/7468.78.7例题例题例例1 1 非空集合非空集合A A上存在二元关系上存在二元关系R R，使得，使得R R既是既是A A上的等价上的等价关系又是关系又是A A上的偏序关系吗？上的偏序关系吗？解：解：存在存在,A,A上的恒等关系就满足。上的恒等关系就满足。例例2 2在在A=1,2,3,4,6,8,12,24A=1,
71、2,3,4,6,8,12,24和和B=2,3,4,8,9,10,11B=2,3,4,8,9,10,11上定义的整除关系上定义的整除关系“| |”，画出，画出HasseHasse图，指出最大图，指出最大( (小小) )元，极大元，极大( (小小) )元。元。解：如图解：如图(a)(a)所示所示最大元：最大元：24 24 最小元：最小元：1 1极大元：极大元：24 24 极小元：极小元：1 1如图如图(b)(b)所示所示最大元最大元: :无无 极大元极大元:8,9,10,11:8,9,10,11最小元最小元: :无无 极小元极小元:2,3,11 :2,3,11 (a) (b)(a) (b)( (元
72、素元素1111既是极大元又是极小元既是极大元又是极小元) ) 2021/6/747例例3 3 设偏序集设偏序集(A,)(A,)的关系图如图的关系图如图(a)(a)所示。所示。(1)(1)画出画出(A,)(A,)的的HasseHasse图。图。(2)(2)设设B Bb,c,b,c,求求B B的上界集合的上界集合C C和上确界和上确界; ;下界集合下界集合D D和和下确界。下确界。解：解：1.(A,)1.(A,)的的HasseHasse图如图图如图(b)(b)所示。所示。 2.2.设设B=b,cB=b,c，则，则A A中无任意元素同时中无任意元素同时“大于大于”b b和和“大大于于”c c，故，故
73、C C，无上确界；而，无上确界；而D Ddd，下确界：，下确界：d d。(a) (b) 2021/6/748例例4 4 设集合设集合A=a,b,c,d,eA=a,b,c,d,e上关系上关系R R定义如下：定义如下： R=(a,a),(a,b),(a,c),(a,d),(a,e),(b,b),(b,c),R=(a,a),(a,b),(a,c),(a,d),(a,e),(b,b),(b,c), (b,e),(c,c),(c,e),(d,d),(d,e),(e,e) (b,e),(c,c),(c,e),(d,d),(d,e),(e,e)。1.1.验证验证(A,R)(A,R)是偏序集是偏序集; ; 2
74、.2.画出画出HasseHasse图。图。3.3.若若A A上的关系如下，则又如何？上的关系如下，则又如何？ R=(a,a),(a,b),(a,c),(a,d),(a,e),(b,b),(b,c),R=(a,a),(a,b),(a,c),(a,d),(a,e),(b,b),(b,c), (b,e),(c,c),(c,d),(c,e),(d,d),(d,e),(e,e) (b,e),(c,c),(c,d),(c,e),(d,d),(d,e),(e,e)。 解：解：1.1. R R所对应的关系矩阵为所对应的关系矩阵为M MR R如下：如下：2021/6/749由关系矩阵可知：由关系矩阵可知：(1)
75、(1)对角线上的所有元素全为对角线上的所有元素全为1 1，故，故R R是自反的；是自反的；(2)r(2)rijijr rjiji11，故，故R R是反对称的；是反对称的；(3)(3)计算计算R R2 2对应的矩阵对应的矩阵M MR R2 2=M=MR R。因此。因此R R是传递的。是传递的。故故R R是是A A上的偏序关系，从而上的偏序关系，从而(A,R)(A,R)是偏序集。是偏序集。 2.2.(A,R)(A,R)对应的对应的HasseHasse图如图所示。图如图所示。 3.3.R R的关系矩阵为：的关系矩阵为：因为因为(b,c)R(b,c)R，(c,d)R(c,d)R，但，但(b,d)(b,d) R R，故故R R不是传递的。不是传递的。因此因此R不是不是A上的偏序关系。上的偏序关系。cebad2021/6/750总总 结结二元关系二元关系 二元运算二元运算 aRb aaRb ab b 是，否是，否 结果是对象结果是对象X,Y=X,Y=映射、运算、关系映射、运算、关系数学模型数学模型概念：二元关系、性质，合成，闭包概念：二元关系、性质，合成，闭包R R+ +,R,R* *，等价关系、，等价关系、 等价类、集合的划分，偏序关系、全序关系。等价类、集合的划分，偏序关系、全序关系。2021/6/751部分资料从网络收集整理而来，供大家参考，感谢您的关注！
