离散数学第三章-二元关系备选.ppt

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

1、9等价关系等价关系与等价类定义定义：设X是一个集合，R是X中的二元关系，若R是自反的，对称的和可传递的，则称R是等价关系。例：下列关系均为等价关系（1）实数（或I、N集上）集合上的“=”关系（相等）（2）人类中的同姓关系（3）命题集合上的等价关系例：设X=1,2,3,4,5,6,7，为整数9等价关系等价关系与等价类试验证R是等价关系，画出R的关系图，列出R的关系矩阵解：（1）R=（2）R的关系矩阵10相容关系关系例：已知相容关系图，求出最大相容类10相容关系关系最大相容类集合为例题选讲例例1.设A，B，C，D代表任意集合，判断以下命题是否恒真，如果不是，请举一反例。(1)ABCDACBD(2)

2、ABCDA-DB-C(3)ABB=A(B-A)(4)A-B=B-AA=B解：(1)不为真。举反例如下：令A1,B=1,4,C=2,D=2,3则AB且CD，但ACBD，与结论矛盾。例题选讲(2)由于CDDC，又由AB可得ADBC即ADBC成立。(3)由于A(BA)=AB故有：B=A(BA)B=ABAB即AB的充要条件为B=AB或A=AB或AB=例题选讲(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例题选讲例例2.设：A、B是任意的集合(1)试证明(A)(B)=(AB)(2)(A)(B)=

3、(AB)成立吗？为什么？解：(1)证明S(A)(B)，则S(A)且S(B)，因此：SA且SBSAB即S(AB)(A)(B)(AB)反之，设S(AB)，则SAB，例题选讲因此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或SBSAB即S(AB)故(A)(B)(AB)成立例题选讲(AB)(A)(B)不成立设：S(AB)，则SAB。但此时无法推断SA，也无法推断SB，因此既不能得出S(A)，也不能得出S(B)。例如：设A=a,c，B=c,b则AB=a,b,c，设S

4、=a,b，则SAB即S(AB)但S(A)且S(B)因此S(A)(B)例题选讲例3.设S=1,2,3,10，是S上的整除关系，求的哈斯图，并求其中的最大元，最小元。最小上界，最大下界。分析：画哈斯图的关键在于确定结点的层次和元素间的盖住关系。画图的基本步骤是：(1)确定偏序集中的极小元，并将这些极小元放在哈斯图的最底层；(2)若第n层的元素已确定完毕，从A中剩余的元素中选取至少能盖住第n层中一个元素的元素，将这些元素放在哈斯图的第n+1层。例题选讲在排列结点的位置时，注意把盖住较多元素的结点放在中间，将只盖住一个元素的结点放在两边，以减少连线的交叉；(3)将相邻两层的结点根据盖住关系进行连线。例

5、题选讲在画哈斯图时应该注意下面几个问题：(1)哈斯图中不应该出现三角形，如果出现三角形，一定是盖住关系没找对。纠正的方法是重新考察这3个元素在偏序集中的顺序，然后将不满足盖住关系的那条边去掉。(2)哈斯图中不应该出现水平线段。出现这种错误的原因在于没有将“较大”元素放在“较小”元素的上方。纠正时只要根据“大小”顺序将“较大”的元素放到更高的一层，将水平线改为斜线就可以了。(3)哈斯图中要尽量减少线的交叉。图形中线的交叉多少主要取决于同一层结点的排列顺序，例题选讲如果出现交叉过多，可以适当调整结点的排列顺序。最后，如何确定哈斯图中极大元、极小元、最大元、最小元、最小上界和最大下界。方法如下：(1

6、)如果图中有孤立结点，那么这个结点既是极小元，也是极大元，并且图中既无最小元，也无最大元。（除只有唯一孤立结点的情况）(2)除了孤立结点以外，其它的极小元是图中所有向下通路的终点，其它的极大元是图中所有向上通路的终点。例题选讲例例4.设Z+=x|xZx0，1，2是Z+的2个划分，1=x|xZ+，2=Z+，求划分1，2所确定的Z+上的等价关系。分析：等价关系和划分是两个不同的概念。等价关系是有序对的集合，而划分是子集的集合。但对于给定的集合A，A上的等价关系R和A的划分是一一对应的。即：Rx和y在的同一划分块里。本题中，1的划分块都是单元集，没有含两个以上元素的划分块；例题选讲2中只有一个划分块

7、Z+，Z+包含了集合中的全体元素。R1就是Z+上的恒等关系；R2就是Z+上的全域关系。例例5.对下面给定的集合A和B，构造从A到B的双射函数分析：构造从集合A到B的双射函数，一般可采用下面的方法：(1)若A，B都是有穷集合，可以先用列元素的方法表示A，B例题选讲然后，顺序将A中的元素与B中的元素建立对应。(2)若A，B是实数区间，可以采用直线方程作为从A到B的双射函数。例如：A1,2，B2,6是实数区间。先将A，B区间分别标记在直角坐标系的x轴和y轴上，过(1,2)和(2,6)两点的直线方程将A中的每个数映到B中的每一个数。因此，该直线方程：就是从A到B的双射函数。例题选讲这种通过直线方程构造

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

9、A AB 同理：A-B=B-A AB=BA ABA=BAA AB=A-B=BA 由、可得：A=B【例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）。例如，A=a,bB=b,cAB=a,b,c，则 P（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）。【例3.4.3】设A i

10、是实数集合，它被定义为：则 证明 （1）先证 设则必存在某个自然数k，使 xA k，即 则有x1，故xA 0。所以 （2）再证 设xA 0，即x1，故必有0，使x=1-，令 则，即 xA k，所以 故【例3.4.4】证明（A-B）B=AB。证明 (A-B）B=（AB）B=（AB）-B）（B-（AB）=（ABB）（B（AB）=（AB）（B（AB）=（AB）B=AB习题三1证明：如果Ba，那么aB。2试用描述法表示下列集合：(1)小于5的非负整数集合。(2)10与20之间的素数集合。(3)小于65的12的正倍数集合。(4）能被5整除的自然数的集合。3.选择适宜的客体域和谓词公式表示下列集合：(1)

11、奇整数集合。(2)10的倍数集合。(3)永真式的集合。4对任意元素a,b,c,d，证明：a,a,bc，c，d当且仅当a=c且b=d5如果AB,BC，那么AC对任意A,B,C都成立吗？都不成立吗？举例说明你的结论。6列举出下列集合的元素：(1)S=x|xI(3x12)，I为整数集合(2)S=x|x是十进制的数字(3)S=x|(x=2)(x=5)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、(12）对任意集合A，B，C，若AB，BC则AC。8列举下列集合的所有子集:（1）（2）1,2,3(3)1,2,3（4）(5)1,22,1,1,2,1,1,29 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。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为集合，证明：（A-B）-C=A-（BC）。16设A、B、C为集合，证明：（AB

13、）-C=（A-C）（B-C）。17证明：对任意集合A、B和C有，（AB）C=A（BC）的充分必要条件是CA。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）20设A，B是全集E的子集，已知AB，证明：BA。21设A、B为集合，且AB，证明：AB=E，其中E为全集。22证明：（A-B）B=AB。23设Bi是实数集合，它被定义为：证明：24设某校有58个学生，其中15人会打篮球，20人会打排球，38人会踢足球，且其中只有3人同时会

14、三种球，试求同时会两种球的学生共有几人。25求1到500的整数中（1和500包含在内）分别满足以下条件的数的个数：（1）同时能被4，5和7整除。（2）不能被4和5，也不能被7整除。（3）可以被4整除，但不能被5和7整除。（4）可以被4或5整除，但不能被7整除。定理4.5.4对非空集合A上的关系R1、R2，则（1）r(R1)r(R2)=r(R1R2)（2）s(R1)s(R2)=s(R1R2)（3）t(R1)t(R2)t(R1R2)证明(1）和（2）的证明留作练习，下面仅证明（3）。因为R1R2R1,由定理4.5.3知 t(R1R2)t(R1)同理t(R1R2)t(R2)所以t(R1R2)t(R1

15、)t(R2)4.11例 题 选 解【例4.11.1】证明：非空的对称、传递关系不可能是反自反关系。证明设R是集合A上的对称、传递关系，若R非空，则x，yA，有x,yR。由于R对称，因此y,xR，又由于R是传递的，因此x,xR。因此非空的对称、传递关系不可能是反自反关系。【例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。（再证充分性）(1)xA，由于R、S均是自反的，

16、因此x,xR且x,xS，所以x,xR。S，即R。S是自反的。(2)x,y x,yR。St（x,tRt,yS）t（t,xRy,tS）(由于R、S均是对称的)y,xS。R y,xR。S (由于S。R=R。S)即R。S是对称的。(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是传递的。【例4.11.3】设R、S均是A上的等价关系，证明

17、：RS于A上等价 iff R。SRS且S。RRS。证明（先证必要性）x,yR。St（x,tRt,yS）t（x,tRSt,yRS）x,yRS (由于RS传递)即R。SRS。同理可证：S。RRS。（再证充分性）(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是对称的。【例4.11.4】设R、S均是非空集合A上的偏序关系，证明：RS也是A上的偏序关系。证明(1)xA，由于R、S均是自反的，因此有x,xR且x,xS，即x,xRS，故RS自反。(2)x,yxy x

18、,yRSx,yRx,yS y,xRy,xS （由于R、S均是反对称的）y,xRS故RS反对称。(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也是偏序关系。【例4.11.5】A=a,b上有多少不同的偏序关系？解因为偏序关系与哈斯图一一对应，所以只要画出所有不同的哈斯图，就可求出其不同的偏序关系，详见图4.11.1。所以该集合上共有3个不同的偏序关系。【例4.11.6】给出A=a,b,c上既是等价关系又是偏序关系的R。解R=I

19、A图 4.11.1【例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，5。（3）B的上界：6，54，24；下界：1。（4）长度为4的反链：4，5，6，9。图 4.11.2【例4.11.10】设f：AB是函数，并定义一个函数g：BP（A）。对于任意的bB，有g（b）=x|（xA）（f（x）=b）请证明：若f是A到B的

20、满射，则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）（f（x）=b2）因此有a1g（b1），a2(g（b2），但a1g（b2），a2g（b1），所以g（b1）g（b2），故g为单射。【例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

21、是自反的。f,gf,gR Ran f=Ran g Ran g=Ran f g,fR即R是对称的。f,g，g,h f,gRg,h R (Ran f=Rang)(Rang=Ranh )Ran f=Ran h f,h R即R是传递的。综上，R是X X上的等价关系。（2）定义：X X/RP（X）-：fRX X/R，（fR）=Ran f，于是（fR）=（gR）Ran f=Ran g f,gRfR=gR 因而是单射。又AP（X）-，AX，A，取定元素aA，定义f：XX为则（fR）=Ran f=A，因而是满射。综上所述，存在双射：X X/RP（X）-。【例4.11.12】设f：AB，g：BC是两个函数，证明

22、：（1）若f。g是满射且g是单射，则f是满射。（2）若f。g是单射且g是满射，则f是单射。（注：这里函数的复合为右复合。）证明（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是满射。（2）对任意b1，b2B（b1b2），由于f是单射，所以a1，a2A，使得f（a1）=b1，f（a2）=b2。由于b1b2且f是函数，所以a1a2。再由f。g是单射，可得f。g（a1）f。g（a2），即g（f（

23、a1）g（f（a2），所以g（b1）g（b2）。因此g是单射。【例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。若有b1,b2B,且b1b2,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）的单射。习题四1已知A=,求P(A)A。2设A=1,2,3

24、,R为实数集,请在笛卡儿平面上表示出AR和RA。3以下各式是否对任意集合A，B，C，D均成立？试对成立的给出证明，对不成立的给出适当的反例。（1）(A-B)C=(AC)-(BC)（2）(AB)(CD)=(AB)(CD)（3）(A-B)(C-D)(AC)-(BD)（4）(AB)(CD)=(AC)(BD)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。7给定集合A=1，2，3，R，S均是A上的关系，R

25、=1,2,2,1IA，S=1,1,2,3（1）画出R，S的关系图；（2）说明R，S所具有的性质；（3）求RS。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)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

26、，2，2,S=4，2，2,5,3,1，1,3。试求RS的关系矩阵。11设A=1，2，3，4，A上关系R1，4，3，1，3，2,4,3。求R的各次幂的关系矩阵。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。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）求RS。15证明定理4.3.3中的（2）

27、、（3）、（6）。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。表 4.1 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具有什么性质？19设A为一集合，|A|=n,试计算（1）A上有多少种不同的自反的（反自反的）二元关系（2）A上有多少种不同的对称的二元关系？（3）A上有多少种不同的反对称的二元关系？20设R为

28、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,从而得到矛盾。22证明：当关系R传递且自反时，R2R。23设R、S、T均是集合A上的二 元 关 系，证 明：若 RS，则TRTS。24设R为集合A上任一关系，求证对一切正整数n有25设R是集合A上的二元关系，R在A上是反传递的定义为：若x,yR,y

29、,zR,则x,zR即xyz(xRyyRzxRz)。证明：R是反传递的，当且仅当（RR）R=。26证明定理4.5.1中的（2）。27证明定理4.5.2中的（1）、（3）。28证明定理4.5.3中的（1）、（2）。29证明定理4.5.4中的（1）、（2）及对（3）t(R1R2)=t(R1)t(R2)举出反例。30证明定理4.5.5中的（3）。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的一个划分，求

30、其等价关系R。33若1，3，5，2，4是集合A=1,2,3,4,5的一个划分，求其等价关系R。34 设 S=1,2,3,4,5且 A=SS,在A上定义关系R:a,bRa,b当且仅当ab=ab。（1）证明R是一个等价关系。（2）计算A/R。35设R是集合A上的二元关系，R在A上是循环的充分必要条件是：若aRb并且bRc，则cRa。证明：R为等价关系当且仅当R是自反的和循环的。36设R，S为A上的两个等价关系，且RS。定义A/R上的关系R/S：x,yR/S当且仅当x,yS证明：R/S为A/R上的等价关系。37设A 1，2,，A m为集合A的划分，证明：对任意集合B，A1B，A 2B，AmB-必为集

31、合AB的划分。38设R1表示整数集上模m1相等关系，R2表示模m2相等关系，1，2分别是R1，R2对应的划分。证明：1细分于2当且仅当m1是m 2的倍数。39确定下面集合A上的关系R是不是偏序关系。（1）A=Z,aRba=2b（2）A=Z,aRbb2|a（3）A=Z,aRb存在k使a=bk（4）A=Z,aRbab40设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关于R的最大元和最小元；（3）求子集c，d，e的上界和上确界；（4

32、）求子集a，b，c的下界和下确界。图 4.1 图 4.2 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的上界、下界，上确界、下确界（如果有的话）。43设R是集合A=a，b，c，d上的偏序关系，关系矩阵为（1）写出R的表达式；（2）画出R的哈斯图；（3）求子集B=a，b关于R的上界和上确界。44对下列每一条件构造满足该条件的有限集和无限集各一个。（1）非空有序集，其中有子集没

33、有最大元素。（2）非空有序集，其中有子集有下确界，但它没有最小元素。（3）非空有序集，其中有一子集存在上界，但它没有上确界。45图4.3给出了集合S=a,b,c,d上的四个关系图。请指出哪些是偏序关系图，哪些是全序关系图，哪些是良序关系图，并对偏序关系图画出对应的哈斯图。图 4.3 46下列集合中哪些是偏序集合，哪些是全序集合，哪些是良序集合？（1）P(N),（2）P(N),（3）Pa,（4）P(),47 设 R是 集 合 S上 的 关 系，SS，定 义 S上 的 关 系 R为：RR(SS）。确定下述各断言的真假：（1）如果R传递，则R传递。（2）如果R为偏序关系，则R也是偏序关系。（3）如果

34、S,R为全序集，则S,R也是全序集。（4）如果S,R为良序集，则S,R也是良序集。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,vxuxu49指出下列各关系是否为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,

35、4，B=AA，S=1,2,3,2,3,4,3,2,350设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(,)。55 设 X,Y均 是 有 穷 集 合。|X|=n,|Y|=m,分别找出从X到Y存在单射、满射、双射的必要条件。试计算集合X到集合Y有多少个不同的单射函数和多少个不同的满射函数及多少个不同的双射函数。55 设

36、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。57设X=1,2，3，请找出XX中满足下列各式的所有函数。（1）f2(x)=f(x)（f等幂）（2）f2(x)=x（f2为恒等函数）（3）f3(x)=x（f3为恒等函数）58设A，A，B，C为集合。（1）求A，（2）若AB，则ACBC。59设N为X上的函数，证

37、明下列条件中（1）与（2）等价,（3）与（4）等价。（1）N为一单射。（2）对任意X上的函数f，g，fNgN蕴涵f=g。（3）N为一满射。（4）对任意X上的函数f，g，NfNg蕴涵fg。60设A=l，2，3，作出全部A上的置换，并以三个函数值组成的字的字典序排列这些置换。试计算p 2p 3，p 3p 3，p 3p 2，并求x，使得 p 3p x=p xp 3=i。61下列函数为实数集上的函数，如果它们可逆，请求出它们的反函数。（1）y=3x+1（2）y=x2-1（3）y=x2-2x（4）y=tg x+162根据自然数集合的定义计算：（1）47，35（2）6-5，42（3）2566证明：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|。