第三章 二元关系备选PPT讲稿.ppt

《第三章 二元关系备选PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《第三章 二元关系备选PPT讲稿.ppt（100页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第三章 二元关系备选第1页，共100页，编辑于2022年，星期二9等价关系等价关系与等价类试验证R是等价关系，画出R的关系图，列出R的关系矩阵 解：（1）R=（2）R的关系矩阵 第2页，共100页，编辑于2022年，星期二10相容关系关系例：已知相容关系图，求出最大相容类第3页，共100页，编辑于2022年，星期二10相容关系关系最大相容类集合为第4页，共100页，编辑于2022年，星期二例题选讲例例1.设A，B，C，D代表任意集合，判断以下命题是否恒真，如果不是，请举一反例。(1)AB CDAC BD(2)AB CDA-DB-C(3)AB B=A(B-A)(4)A-B=B-A A=B解：(1

2、)不为真。举反例如下：令A1,B=1,4,C=2,D=2,3则AB且CD，但AC BD，与结论矛盾。第5页，共100页，编辑于2022年，星期二例题选讲(2)由于CDDC，又由A B可得 ADBC即AD BC成立。(3)由于A(BA)=A B故有：B=A(BA)B=A B A B即A B的充要条件为B=A B或A=AB或AB=第6页，共100页，编辑于2022年，星期二例题选讲(4)易见，当A=B时，必有A-B=B-A 由A-B=B-A得(A-B)B=(B-A)B 即：(AB)B=(BA)B 即：B-A=BA同理可证：AB从而得到：AB第7页，共100页，编辑于2022年，星期二例题选讲例例2

3、.设：A、B是任意的集合(1)试证明(A)(B)=(AB)(2)(A)(B)=(AB)成立吗？为什么？解：(1)证明 S(A)(B)，则S(A)且S(B)，因此：SA且SB S AB 即S(AB)(A)(B)(AB)反之，设S(AB)，则S AB，第8页，共100页，编辑于2022年，星期二例题选讲因此SA且SBS(A)且S(B)于是S(A)(B)(AB)(A)(B)由上知(A)(B)(AB)(2)(A)(B)(AB)成立。其证明如下：设：S(A)(B)，则S(A)或S(B)因此 SA或SB SAB即S(AB)故(A)(B)(AB)成立第9页，共100页，编辑于2022年，星期二例题选讲(AB

4、)(A)(B)不成立设：S(AB)，则SAB。但此时无法推断SA，也无法推断SB，因此既不能得出S(A)，也不能得出S(B)。例如：设 A=a,c，B=c,b则 AB=a,b,c，设 S=a,b，则SAB即 S(AB)但 S(A)且S(B)因此 S(A)(B)第10页，共100页，编辑于2022年，星期二例题选讲例3.设S=1,2,3,10，是S上的整除关系，求 的哈斯图，并求其中的最大元，最小元。最小上界，最大下界。分析：画哈斯图的关键在于确定结点的层次和元素间的盖住关系。画图的基本步骤是：(1)确定偏序集中的极小元，并将这些极小元放在哈斯图的最底层；(2)若第n层的元素已确定完毕，从A中剩

5、余的元素中选取至少能盖住第n层中一个元素的元素，将这些元素放在哈斯图的第n+1层。第11页，共100页，编辑于2022年，星期二例题选讲在排列结点的位置时，注意把盖住较多元素的结点放在中间，将只盖住一个元素的结点放在两边，以减少连线的交叉；(3)将相邻两层的结点根据盖住关系进行连线。第12页，共100页，编辑于2022年，星期二例题选讲在画哈斯图时应该注意下面几个问题：(1)哈斯图中不应该出现三角形，如果出现三角形，一定是盖住关系没找对。纠正的方法是重新考察这3个元素在偏序集中的顺序，然后将不满足盖住关系的那条边去掉。(2)哈斯图中不应该出现水平线段。出现这种错误的原因在于没有将“较大”元素放

6、在“较小”元素的上方。纠正时只要根据“大小”顺序将“较大”的元素放到更高的一层，将水平线改为斜线就可以了。(3)哈斯图中要尽量减少线的交叉。图形中线的交叉多少主要取决于同一层结点的排列顺序，第13页，共100页，编辑于2022年，星期二例题选讲如果出现交叉过多，可以适当调整结点的排列顺序。最后，如何确定哈斯图中极大元、极小元、最大元、最小元、最小上界和最大下界。方法如下：(1)如果图中有孤立结点，那么这个结点既是极小元，也是极大元，并且图中既无最小元，也无最大元。（除只有唯一孤立结点的情况）(2)除了孤立结点以外，其它的极小元是图中所有向下通路的终点，其它的极大元是图中所有向上通路的终点。第1

7、4页，共100页，编辑于2022年，星期二例题选讲例例4.设Z+=x|xZx0，1，2是Z+的2个划分，1=x|x Z+，2=Z+，求划分1，2所确定的Z+上的等价关系。分析：等价关系和划分是两个不同的概念。等价关系是有序对的集合，而划分是子集的集合。但对于给定的集合A，A上的等价关系R和A的划分是一一对应的。即：Rx 和y在的同一划分块里。本题中，1的划分块都是单元集，没有含两个以上 元素的划分块；第15页，共100页，编辑于2022年，星期二例题选讲2中只有一个划分块Z+，Z+包含了集合中的全体元素。R1就是Z+上的恒等关系；R2就是Z+上的全域关系。例例5.对下面给定的集合A和B，构造从

8、A到B的双射函数 分析：构造从集合A到B的双射函数，一般可采用下面的方法：(1)若A，B都是有穷集合，可以先用列元素的方法表示A，B第16页，共100页，编辑于2022年，星期二例题选讲然后，顺序将A中的元素与B中的元素建立对应。(2)若A，B是实数区间，可以采用直线方程作为从A到B的双射函数。例如：A1,2，B2,6是实数区间。先将A，B区间分别标记在直角坐标系的x轴和y轴上，过(1,2)和(2,6)两点的直线方程将A中的每个数映到B中的每一个数。因此，该直线方程：就是从A到B的双射函数。第17页，共100页，编辑于2022年，星期二例题选讲这种通过直线方程构造双射函数的方法对任意两个同类型

9、的实数区间(同为闭区间、开区间或半开半闭区间)都是适用的。此外，对于某些特殊的实数区间，可能选择其它严格单调的初等函数更方便。对于本题:(3)A是一个无穷集合，B是自然数集N 只须将A中的元素排成一个有序序列，且指定这个序列的初始元素，这就叫做把A“良序化”。例如：构造从整数集Z到自然数集N的双射，如下排列：第18页，共100页，编辑于2022年，星期二例题选讲Z：0，-1，1，-2，2，-3，3，.N：0，1，2，3，4，5，6，.即：显然f是从Z到N的双射。第19页，共100页，编辑于2022年，星期二3.4 例 题 选 解 【例3.4.1】设A、B为集合，已知 A-B=B-A，证明：A=

10、B。证明 A-B=B-A AB=BA ABB=BAB =BA =B-A AB 第20页，共100页，编辑于2022年，星期二同理：A-B=B-A AB=BA ABA=BAA AB=A-B=BA 由、可得：A=B 第21页，共100页，编辑于2022年，星期二 【例3.4.2】设A、B为集合，证明：P（A）P（B）P（AB）。并举例说明不能将“”换成“=”。证明 x，x（P（A）P（B）xP（A）xP（B）不妨设xP（A），则有 xAx（AB），所以 xP（AB），故P（A）P（B）P（AB）。第22页，共100页，编辑于2022年，星期二例如，A=a,b B=b,c AB=a,b,c，则 P（

11、A）=,a,b,a,b,P(B)=,b,c,b,c P（A）P（B）=,a,b,c,a,b,b,c而 P（AB）=,a,b,c,a,b,a,c,b,c,a,b,c所以P（A）P（B）P（AB）。第23页，共100页，编辑于2022年，星期二 【例3.4.3】设A i是实数集合，它被定义为：则 证明 （1）先证 设则必存在某个自然数k，使 xA k，即 则有x1，故xA 0。所以 第24页，共100页，编辑于2022年，星期二（2）再证 设xA 0，即x1，故必有0，使x=1-，令 则，即 xA k，所以 故 第25页，共100页，编辑于2022年，星期二【例3.4.4】证明（A-B）B=AB。

12、证明 (A-B）B=（AB）B =（AB）-B）（B-（AB）=（A BB）（B（AB）=（AB）（B（AB）=（AB）B=AB 第26页，共100页，编辑于2022年，星期二习 题 三 1证明：如果Ba，那么aB。2试用描述法表示下列集合：(1)小于5的非负整数集合。(2)10与20之间的素数集合。(3)小于65的12的正倍数集合。(4）能被5整除的自然数的集合。第27页，共100页，编辑于2022年，星期二3.选择适宜的客体域和谓词公式表示下列集合：(1)奇整数集合。(2)10的倍数集合。(3)永真式的集合。4对任意元素a,b,c,d，证明：a,a,bc，c，d当且仅当a=c且b=d第28

13、页，共100页，编辑于2022年，星期二 5 如 果 AB,BC，那 么AC对任意A,B,C都成立吗？都不成立吗？举例说明你的结论。6列举出下列集合的元素：(1)S=x|xI(3x12)，I为整数集合 (2)S=x|x是十进制的数字 (3)S=x|(x=2)(x=5)第29页，共100页，编辑于2022年，星期二7下面命题的真值是否为真，说明理由。(1)aa (2)aa(3)aa,a (4)aa,a(5）(6）(7）(8）(9）对任意集合A，B，C，若AB，BC则AC。(10）对任意集合A，B，C，若AB，BC则AC。(11）对任意集合A，B，C，若AB，BC则AC。(12）对任意集合A，B，

14、C，若AB，BC则AC。第30页，共100页，编辑于2022年，星期二 8列举下列集合的所有子集:（1）（2）1,2,3 (3)1,2,3（4）(5)1,22,1,1,2,1,1,2 9 A、B、C均 是 集 合，若AC=BC且AC=BC，则必有A=B。10.设A=a,求A的幂集P(A)以及A的幂集的幂集P(P(A)。11设A、B、C、D为4个集合，已知AB且CD，证明：ACBD。第31页，共100页，编辑于2022年，星期二12设A、B为集合，证明：P（A）P（B）=P（AB）。13证明定理3.2.3。14设A、B、C为集合，证明：（A-B）-C=（A-C）-（B-C）。15设A、B为集合，

15、证明：（A-B）-C=A-（BC）。16设A、B、C为集合，证明：（AB）-C=（A-C）（B-C）。17证明：对任意集合A、B和C有，（AB）C=A（BC）的充分必要条件是CA。第32页，共100页，编辑于2022年，星期二18设A、B、C是集合，若CA，证明：（AB）C=A（BC）。19设全集E=a，b，c，d，e，f，g，子集A=a，b，d，e，B=c，d，f，g，C=c，e，求下面集合：（1）AB（2）（AB）（3）（AB）（AC）第33页，共100页，编辑于2022年，星期二 20设A，B是全集E的子集，已知AB，证明：BA。21设A、B为集合，且AB，证明：AB=E，其中E为全集。

16、22证明：（A-B）B=AB。23设Bi是实数集合，它被定义为：证明：第34页，共100页，编辑于2022年，星期二24设某校有58个学生，其中15人会打篮球，20人会打排球，38人会踢足球，且其中只有3人同时会三种球，试求同时会两种球的学生共有几人。25求1到500的整数中（1和500包含在内）分别满足以下条件的数的个数：（1）同时能被4，5和7整除。（2）不能被4和5，也不能被7整除。（3）可以被4整除，但不能被5和7整除。（4）可以被4或5整除，但不能被7整除。第35页，共100页，编辑于2022年，星期二定理 4.5.4 对非空集合A上的关系R1、R2，则（1）r(R1)r(R2)=r

17、(R1R2)（2）s(R1)s(R2)=s(R1R2)（3）t(R1)t(R2)t(R1R2)第36页，共100页，编辑于2022年，星期二证明(1）和（2）的证明留作练习，下面仅证明（3）。因为R1R2 R1,由定理4.5.3知 t(R1R2)t(R1)同理 t(R1R2)t(R2)所以 t(R1R2)t(R1)t(R2)第37页，共100页，编辑于2022年，星期二4.11 例 题 选 解 【例4.11.1】证明：非空的对称、传递关系不可能是反自反关系。证明 设R是集合A上的对称、传递关系，若R非空，则x，yA，有x,yR。由于R对称，因此y,xR，又由于R是传递的，因此x,xR。因此非空

18、的对称、传递关系不可能是反自反关系。第38页，共100页，编辑于2022年，星期二 【例4.11.2】设R、S均是A上的等价关系，证明：R。S于A上等价iff S。R=R。S。证明（先证必要性）x,z x,z S。Ry（x,ySy,z R）y（z ,yRy,xS）(由于R、S均是对称的)z ,xR。S x,z R。S (由于R。S于A上是对称的)故S。R=R。S。第39页，共100页，编辑于2022年，星期二 （再证充分性）(1)xA，由于R、S均是自反的，因此x,xR且 x,xS，所以x,xR。S，即R。S是自反的。(2)x,y x,yR。St（x,tRt,yS）t（t,xRy,tS）(由于

19、R、S均是对称的)y,xS。R y,xR。S (由于S。R=R。S)即R。S是对称的。第40页，共100页，编辑于2022年，星期二(3)x,y，y,z x,yR。Sy,z R。S x,yR。Sy,z S。R (由于S。R=R。S)x,z R。S。S。R x,z R。(S。S)。R (关系的复合满足结合律)x,z R。S。R （由于S传递，因此S。SS）x,z R。R。S （由于S。R=R。S)x,z R。S （由于R传递，因此R。RR）即R。S是传递的。第41页，共100页，编辑于2022年，星期二【例4.11.3】设R、S均是A上的等价关系，证明：RS于A上等价 iff R。SRS且S。R

20、RS。证明（先证必要性）x,yR。St（x,tRt,yS）t（x,tRSt,yRS）x,yRS (由于RS传递)即R。SRS。同理可证：S。RRS。（再证充分性）第42页，共100页，编辑于2022年，星期二(1)xA，由于R、S均是自反的，因此x,xR且 x,xS，所以x,xRS，即RS是自反的。(2)x,y x,yRSx,yRx,yS y,xRy,xS）(由于R、S均是对称的)y,xRS即RS是对称的。第43页，共100页，编辑于2022年，星期二 【例4.11.4】设R、S均是非空集合A上的偏序关系，证明：RS也是A上的偏序关系。证明(1)xA，由于R、S均是自反的，因此有x,xR且x,

21、xS，即x,xRS，故RS自反。(2)x,yxy x,yRSx,yRx,yS y,xRy,xS （由于R、S均是反对称的）y,xRS 故RS反对称。第44页，共100页，编辑于2022年，星期二(3)x,y，y,z x,y(RS)y,z (RS)(x,yRx,yS)(y,z Ry,z S)(x,yRy,z R)(x,ySy,z S)x,z Rx,z S （由于R、S均是传递的）x,z RS故RS传递。因此，RS也是偏序关系。第45页，共100页，编辑于2022年，星期二 【例4.11.5】A=a,b上有多少不同的偏序关系？解 因为偏序关系与哈斯图一一对应，所以只要画出所有不同的哈斯图，就可求出

22、其不同的偏序关系，详见图4.11.1。所以该集合上共有3个不同的偏序关系。【例4.11.6】给出A=a,b,c上既是等价关系又是偏序关系的R。解 R=IA 第46页，共100页，编辑于2022年，星期二图 4.11.1 第47页，共100页，编辑于2022年，星期二【例4.11.7】设A=1,2,3,4,5,6,9,24,54,R是A上的整除关系。(1)画出偏序关系R的 Hasse 图。(2)求A关于R的极大元、极小元。(3)设B=2，3，求B的上界和上确界。(4)找出A，R中的长度为4的反链。解（1）关系R的 Hasse 图见图4.11.2。（2）A关于R的极大元：54，24，5；极小元：1

23、，5。（3）B的上界：6，54，24；下界：1。（4）长度为4的反链：4，5，6，9。第48页，共100页，编辑于2022年，星期二图 4.11.2 第49页，共100页，编辑于2022年，星期二 【例4.11.10】设f：AB是函数，并定义一个函数g：BP（A）。对于任意的bB，有 g（b）=x|（xA）（f（x）=b）请证明：若f是A到B的满射，则g是B到P（A）的单射。证明 对任意b1，b2B（b1b2），由于f是满射，因此a1，a2A，使得f（a1）=b1，f（a2）=b2。又由于b1b2且f是函数，因此a1a2。又 g（b1）=x|（xA）(f（x）=b1）g（b2）=x|（xA）（

24、f（x）=b2）第50页，共100页，编辑于2022年，星期二 因此有a1g（b1），a2(g（b2），但a1 g（b2），a2 g（b1），所以g（b1）g（b2），故g为单射。第51页，共100页，编辑于2022年，星期二 【例4.11.11】设X，R为X X上的关系，定义为 f,gR Ran f=Ran g 证明:R是X X上的等价关系，且存在双射：X X/RP（X）-.证明（1）fX X，由于 Ran f=Ran f，因此f,fR，即R是自反的。f,gf,gR Ran f=Ran g Ran g=Ran f g,fR 即R是对称的。第52页，共100页，编辑于2022年，星期二 f,g

25、，g,h f,gRg,h R (Ran f=Rang)(Rang=Ranh )Ran f=Ran h f,h R 即R是传递的。综上，R是X X上的等价关系。第53页，共100页，编辑于2022年，星期二 （2）定义：X X/RP（X）-：fRX X/R，（fR）=Ran f，于是（fR）=（gR）Ran f=Ran g f,gRfR=gR 因而是单射。第54页，共100页，编辑于2022年，星期二 又AP（X）-，AX，A，取定元素aA，定义f：XX为则（fR）=Ran f=A，因而是满射。综上所述，存在双射：X X/RP（X）-。第55页，共100页，编辑于2022年，星期二【例4.11.

26、12】设f：AB，g：BC是两个函数，证明：（1）若f。g是满射且g是单射，则f是满射。（2）若f。g是单射且g是满射，则f是单射。（注：这里函数的复合为右复合。）第56页，共100页，编辑于2022年，星期二 证明 （1）bB，因为g是函数，所以存在cC，使得g（b）=c。由f。g是满射，对该元素c，存在aA，使得f。g（a）=c，即g（f（a）=c。由g（b）=c，所以g（f（a）=g（b）=c。由g是单射，所以有 f（a）=b。即bB，aA，使得f（a）=b。因此f是满射。第57页，共100页，编辑于2022年，星期二 （2）对任意b1，b2B（b1b2），由于f是单射，所以a1，a2A

27、，使得f（a1）=b1，f（a2）=b2。由于b1b2且f是函数，所以a1a2。再由f。g是单射，可得 f。g（a1）f。g（a2），即 g（f（a1）g（f（a2），所以g（b1）g（b2）。因此g是单射。第58页，共100页，编辑于2022年，星期二 【例4.11.13】设f：AB是函数，并定义一个函数g：BP（A）。对于任意的bB，有 g（b）=x|（xA）（f（x）=b）证明若f是A到B的满射，则g是B到P（A）的单射。证明 如果f是A到B的满射，则对每个bB,至少存在一个aA,使f(a)=b,故g的定义域为B。第59页，共100页，编辑于2022年，星期二 若有b1,b2B,且b1b

28、2,g(b1)=x|（xA）（f（x）=b1）g（b2）=y|（yA）（f（y）=b2）因为b1b2,f(x)f(y),而f是函数，故xy,所以g(b1)g(b2)。因此g是B到P（A）的单射。第60页，共100页，编辑于2022年，星期二习 题 四 1已知A=,求P(A)A。2设A=1,2,3,R为实数集,请在笛卡儿平面上表示出AR和RA。3以下各式是否对任意集合A，B，C，D均成立？试对成立的给出证明，对不成立的给出适当的反例。第61页，共100页，编辑于2022年，星期二（1）(A-B)C=(AC)-(BC)（2）(AB)(CD)=(AB)(CD)（3）(A-B)(C-D)(AC)-(B

29、D)（4）(AB)(CD)=(AC)(BD)第62页，共100页，编辑于2022年，星期二4设A,B,C,D为任意集合，求证：（1）若AC，BD，那么ABCD。（2）若 C,ACBC，则 AB。（3）(AB)-(CD)(A-C)B)(A(B-D)。5证明定理4.1.3中的（2）、（3）、（4）、（6）。6证明定理4.1.4和定理4.1.5。第63页，共100页，编辑于2022年，星期二 7给定集合A=1，2，3，R，S均是A上的关系，R=1,2,2,1IA，S=1,1,2,3 （1）画出R，S的关系图；（2）说明R，S所具有的性质；（3）求RS。第64页，共100页，编辑于2022年，星期二

30、8设A0,1,2,3,4,5，B=1,2,3，用列举法描述下列关系，并作出它们的关系图及关系矩阵：（1）R1=x,y|x(AByAB（2）R2=x,y|x(AyBx=y2（3）R3=x,y|x(AyAx+y=5（4）R4=x,y|x(AyAk(x=kykNk2)（5）R5=x,y|x(AyA(x=02x3)第65页，共100页，编辑于2022年，星期二 9设R,S为集合A上任意关系，证明：（1）Dom(RS)=Dom(R)Dom(S)（2）Ran(RS)Ran(R)Ran(S)10设A=1，2，3，4,5，A上关系 R=1，2，3，4，2，2,S=4，2，2,5,3,1，1,3。试求RS的关系

31、矩阵。11设A=1，2，3，4，A上关系 R1，4，3，1，3，2,4,3。求 R的各次幂的关系矩阵。第66页，共100页，编辑于2022年，星期二12证明定理4.3.1中的（1）、（4）、（5）及（6）13设Aa,b,c,d，A上二元关系R1，R2分别为 R1=b,b,b,c,c,a R2=b,a,c,a,c,d,d,c计算R1R2，R2R1，R2 1,R2 2。第67页，共100页，编辑于2022年，星期二14设A=0，1，2，3，R和S均是A上的二元关系:R=x，y|（y=x+1）（y=x/2）S=x，y|（x=y+2）（1）用列元素法表示R，S；（2）说明R，S所具有的性质；（3）求R

32、S。15证明定理4.3.3中的（2）、（3）、（6）。第68页，共100页，编辑于2022年，星期二 16设R1,R2,R3,R4,R5都是整数集上的关系，且 xR1y|x-y|=1 xR2yxy0 xR3yx|y(x整除y)xR4yx+y=5 xR5yx=yn(n是整数)请用T(True)和F(False)填写表4.1。第69页，共100页，编辑于2022年，星期二表 4.1 第70页，共100页，编辑于2022年，星期二 17证明定理4.4.2和定理4.4.6。18设A=0，1，2，3，RAA且 R=x，y|x=yx(yA。(1)画出R的关系图；(2)写出关系矩阵 MR；(3)R具有什么性

33、质？19设A为一集合，|A|=n,试计算（1）A上有多少种不同的自反的（反自反的）二元关系（2）A上有多少种不同的对称的二元关系？（3）A上有多少种不同的反对称的二元关系？第71页，共100页，编辑于2022年，星期二 20设R为A上的自反关系，证明：R是传递的iff RR=R。并举例说明其逆不真。21请判断下述的结论和理由正确吗？并说明理由。（1）如果R对称且传递，那么R必自反，因为由R对称可知xRy蕴涵yRx，而由R传递及xRy,yRx，可知xRx。（2）如果R反自反且传递，那么R必定是反对称的,因为若R对称可知xRy蕴涵yRx，而由R传递及xRy,yRx，可导出xRx,从而得到矛盾。第7

34、2页，共100页，编辑于2022年，星期二 22证明：当关系R传递且自反时，R2R。23设R、S、T均是集合A上的二 元 关 系，证 明：若 RS，则TRTS。24设R为集合A上任一关系，求证对一切正整数n有第73页，共100页，编辑于2022年，星期二 25设R是集合A上的二元关系，R在A上是反传递的定义为：若x,yR,y,zR,则x,zR即xyz(xRyyRzxRz)。证明：R是反传递的，当且仅当（RR）R=。第74页，共100页，编辑于2022年，星期二26证明定理4.5.1中的（2）。27证明定理4.5.2中的（1）、（3）。28证明定理4.5.3中的（1）、（2）。29证明定理4.5

35、.4中的（1）、（2）及对（3）t(R1R2)=t(R1)t(R2)举出反例。30证明定理4.5.5中的（3）。第75页，共100页，编辑于2022年，星期二 31设R是X=1,2,3,4，5上的二元关系，R=1,2,2,1,1,5,5,1,2,5,5,2,3,4,4,3I A。请给出关系矩阵并画出关系图；若R是等价关系，则求出等价类。32 若 a,c,e,b,d,f是 集合A=a,b,c,d,e,f的一个划分，求其等价关系R。33若1，3，5，2，4是集合A=1,2,3,4,5的一个划分，求其等价关系R。第76页，共100页，编辑于2022年，星期二 34 设 S=1,2,3,4,5且 A=

36、SS,在A上定义关系R:a,bRa,b当且仅当ab=ab。（1）证明R是一个等价关系。（2）计算A/R。35设R是集合A上的二元关系，R在A上是循环的充分必要条件是：若aRb并且bRc，则cRa。证明：R为等价关系当且仅当R是自反的和循环的。第77页，共100页，编辑于2022年，星期二 36设R，S为A上的两个等价关系，且RS。定义A/R上的关系R/S：x,yR/S当且仅当x,yS 证明：R/S为A/R上的等价关系。第78页，共100页，编辑于2022年，星期二 37设A 1，2,，A m为集合A的划分，证明：对任意集合B，A1B，A 2B，AmB-必为集合AB的划分。38设R1表示整数集上

37、模m1相等关系，R2表示模 m2相等关系，1，2分别是R1，R2对应的划分。证明：1细分于2当且仅当m1是m 2的倍数。第79页，共100页，编辑于2022年，星期二 39确定下面集合A上的关系R是不是偏序关系。（1）A=Z,aRba=2b（2）A=Z,aRbb2|a（3）A=Z,aRb存在k使a=bk（4）A=Z,aRbab第80页，共100页，编辑于2022年，星期二 40设A=a，b，c，d，e，A上的偏序关系R=c,a,c,dI A。(1)画出R的哈斯图；(2)(1)画出R的哈斯图；求A关于R的极大元和极小元。41偏序集A，的哈斯图如图4.1所示。（1）用列举元素法求R；（2）求A关于

38、R的最大元和最小元；（3）求子集c，d，e的上界和上确界；（4）求子集a，b，c的下界和下确界。第81页，共100页，编辑于2022年，星期二图 4.1 第82页，共100页，编辑于2022年，星期二图 4.2 第83页，共100页，编辑于2022年，星期二 42图4.2为一偏序集A,R的哈斯图。（1）下列命题哪些为真？aRb，dRa，cRd，cRb，bRe，aRa，eRa；（2）画出R的关系图；（3）指出A的最大、最小元（如果有的话），极大、极小元；（4）求出子集B1=c,d,e,B2=b,c,d,B 3=b,c,d,e的上界、下界，上确界、下确界（如果有的话）。第84页，共100页，编辑于

39、2022年，星期二 43设R是集合A=a，b，c，d上的偏序关系，关系矩阵为第85页，共100页，编辑于2022年，星期二 （1）写出R的表达式；（2）画出R的哈斯图；（3）求子集B=a，b关于R的上界和上确界。44对下列每一条件构造满足该条件的有限集和无限集各一个。（1）非空有序集，其中有子集没有最大元素。（2）非空有序集，其中有子集有下确界，但它没有最小元素。（3）非空有序集，其中有一子集存在上界，但它没有上确界。第86页，共100页，编辑于2022年，星期二 45图4.3给出了集合S=a,b,c,d上的四个关系图。请指出哪些是偏序关系图，哪些是全序关系图，哪些是良序关系图，并对偏序关系图

40、画出对应的哈斯图。第87页，共100页，编辑于2022年，星期二图 4.3 第88页，共100页，编辑于2022年，星期二 46下列集合中哪些是偏序集合，哪些是全序集合，哪些是良序集合？（1）P(N),（2）P(N),（3）Pa,（4）P(),第89页，共100页，编辑于2022年，星期二 47设R是集合S上的关系，SS，定 义 S上 的 关 系 R为：RR(SS）。确定下述各断言的真假：（1）如果R传递，则R传递。（2）如果R为偏序关系，则R也是偏序关系。（3）如果S,R为全序集，则S,R也是全序集。（4）如果S,R为良序集，则S,R也是良序集。第90页，共100页，编辑于2022年，星期二

41、 48设A,为一有限全序集，|A|2，R是AA上的关系，根据R下列各定义，确定AA,R是否为偏序集、全序集或良序集。设x，y，u，v为A中任意元素。（1）x,yRu,vxuyv （2）x,yRu,vxuxu(x=uyv)（3）x,yRu,vxu （4）x,yRu,vxuxu第91页，共100页，编辑于2022年，星期二49指出下列各关系是否为A到B的函数：（1）AB N，R=x,y|xAyBx+y100（2）A=B=R（实数集），S=x,y|xAyBy=x2（3）A 1,2,3,4，B AA，R=1,2,3,2,3,4,3,1,4,4,2,3（4）A=1,2,3,4，B=AA，S=1,2,3,

42、2,3,4,3,2,3第92页，共100页，编辑于2022年，星期二50设f：XY，g：XY，求证：（1）fg为X到Y的函数当且仅当f=g。（2）fg为X到Y的函数当且仅当f=g。51 设 f和 g为 函 数，且 有 fg和Dom(g)Dom(f)。证明f=g。52证明定理4.8.2中的（2）、（3）。53设f:XY，ABX，求证f(A)f(B)。54令f=,，,为一函数。计算f()，f()，f(,)。第93页，共100页，编辑于2022年，星期二 55 设 X,Y均 是 有 穷 集 合。|X|=n,|Y|=m,分别找出从X到Y存在单射、满射、双射的必要条件。试计算集合X到集合Y有多少个不同的

43、单射函数和多少个不同的满射函数及多少个不同的双射函数。第94页，共100页，编辑于2022年，星期二 55 设 X,Y均 是 有 穷 集 合。|X|=n,|Y|=m,分别找出从X到Y存在单射、满射、双射的必要条件。试计算集合X到集合Y有多少个不同的单射函数和多少个不同的满射函数及多少个不同的双射函数。56考虑下列实数集上的函数：f(x)=2x2+1，g(x)=-x+7，N(x)=2x，k(x)=sin x 求gf，fg，ff，gg，fN，fk，kN。第95页，共100页，编辑于2022年，星期二 57 设 X=1,2，3，请 找 出XX中满足下列各式的所有函数。（1）f2(x)=f(x)（f等

44、幂）（2）f2(x)=x（f2为恒等函数）（3）f3(x)=x（f3为恒等函数）第96页，共100页，编辑于2022年，星期二58设A，A，B，C为集合。（1）求A，（2）若AB，则ACBC。59设N为X上的函数，证明下列条件中（1）与（2）等价,（3）与（4）等价。（1）N为一单射。（2）对任意X上的函数f，g，fNgN蕴涵f=g。（3）N为一满射。（4）对任意X上的函数f，g，NfNg蕴涵fg。第97页，共100页，编辑于2022年，星期二 60设A=l，2，3，作出全部A上的置换，并以三个函数值组成的字的字典序排列这些置换。试计算 p 2p 3，p 3p 3，p 3p 2，并求x，使得

45、p 3p x=p xp 3=i。第98页，共100页，编辑于2022年，星期二 61下列函数为实数集上的函数，如果它们可逆，请求出它们的反函数。（1）y=3x+1 （2）y=x2-1 （3）y=x2-2x （4）y=tg x+1 62根据自然数集合的定义计算：（1）47，35 （2）6-5，42 （3）25 第99页，共100页，编辑于2022年，星期二66证明：1，3，5，2n+1,是可数集。67设A，B为可数集，证明：AB为可数集。68设f：AB为一满射。（1）A为无限集时，B是否一定为无限集？（2）A为可数集时，B是否一定为可数集？69设f：AB为一单射。（1）A为无限集时，B是否一定为无限集？（2）A为可数集时，B是否一定为可数集？70证明定理4.10.12。71.若|A|=|B|,|C|=|D|,则|AC|=|BD|。第100页，共100页，编辑于2022年，星期二