离散数学课件第三、四章习题课

郭芸Email:苏州大学计算机科学与技术学院第三、四章习题课1、证明：X上的非空、对称和传递的关系不是反自反的。

2、设R是X上的自反的和传递的关系，证明：

R

R=R.3.x,y,zX,如果xRy,yRz,则有zRx.证明：若R是自反的，则R是X上的等价关系。

4、设f:X

Y和g:Y

Z是映射，使得gf是一个满射，且g是一个入射。证明f是满射。

5、设f:X

Y和g:Y

Z是映射，使得gf是一个入射，且f是一个满射。证明g是入射。思考题6、仅由0,1构成的无限序列集合是不可数的。即T={a0a1a2…an…|nN,an=0or1}为不可数集。7、将(1)推广：由0,1,2,…,9构成的无限序列集合也是不可数集。8、S={(x,y)|x,yR0<x,y<1}为不可数集。（提示：构造f:S→(0,1)为双射函数）9、证明：RR…R=Rn

是不可数集。10、II是可数集。(I为整数集)思考题证：Ex1(思考题1)X上的非空、对称和传递的关系不是反自反的。

设<x,y>R,R是X上非空、对称和传递的关系，由R对称可知，<y,x>R,由R传递可知，<x,x>,<y,y>R,所以R不是反自反的。

任取<x,z>RR,Ex2(思考题2)设R是X上的自反的和传递的关系，证明：RR=R.证：则存在yX,使得<x,y>,<y,z>R,由R是传递的知<x,z>R,故RRR.任取<x,z>R,由R是自反的知<z,z>R,再由复合关系的定义可知<x,z>RR,故RRR.综上，RR=R.x,yX,若

xRy,Ex3(思考题3)

x,y,zX,如果xRy,yRz,则有zRx.证明：若R是自反的，则R是X上的等价关系。证：由R是自反的可知yRy,再利用题设条件可得，yRx,故R是对称的。x,y,zX,如果xRy,yRz,

则由题设条件可得zRx.由R是对称的可知xRz,故R是传递的。所以R是X上的等价关系。任取yY,Ex4(思考题4)设f:XY和g:YZ是映射，使得gf是一个满射，且g是一个入射。证明f是满射。

证：因为g是映射，

故必有z=g(y)Z.由于gf是满射，

故对zZ,必有xX,使得gf(x)=z.从而有gf(x)=g(y),即g(f(x))=g(y).又因为g是入射，故有f(x)=y.所以f是满射。设g(y1)=g(y2),Ex5(思考题5)

设f:X

Y和g:Y

Z是映射，使得gf是一个入射，且f是一个满射。证明g是入射。

证：因为f是满射，

故必有x1,x2X,使f(x1)=y1,f(x2)=y2.从而有g(f(x1))=g(f(x2)),

即gf(x1)=gf(x2).又因为gf

是一个入射，所以x1=x2,从而y1=y2.所以g是入射。

从而

A=M∪D∪B,A-B=M∪D.

否则，由B是可数集且A=B∪P可得,

由定理2知P必含可数子集D,Ex6(4-5习题的(2))如果A是不可数集，B是A的可数子集，则(A-B)~A.证：记P=A-B,则P是无限集。A为可数集，与题设矛盾。因为P是无限集，记M=P-D,即P=M∪D.

因为D,B均为可数集，D∪B~D,M~M,

且M∩(D∪B)=,M∩D=,由4-4的习题(3)知M∪D∪B~M∪D,即A~A-B.Ex7(4-5习题的(4))如果A和B都是可数集，则AB也是可数集。证一：由于A和B都是可数集，可设A={a0,a1,a2,…}B={b0,b1,b2,…}作函数f:AB

NN,使得f(<am,bn>)=<m,n>,显见f是双射，从而AB~NN.又由定理5知，NN~N.所以，AB~N,即AB是可数集。Ex7(4-5习题的(4))如果A和B都是可数集，则AB也是可数集。证二：由于A和B都是可数集，所以A~N,B~N,由4-4习题的(4)知，AB~NN.又由定理5知，NN~N.所以，AB~N,即AB是可数集。考试遇到类似题目时，若要用该方法证明，则要把4-4习题的(4)补证一下。Ex8(4-5习题的(5))

设A是有限集，B是可数集，则AB也是可数集。证：设A={a0,a1,…,an},B={b0,b1,…},则A∪B={a0,a1,…,an,b0,b1,…},显见A∪B是可数集。由4-5习题的(4)知，(A∪B)B是可数集。

而AB是(A∪B)B的无限子集,由定理3知，AB也是可数集。

则T必可表示为：T={t1,t2,…},其中ti=ai1ai2…(i=1,2,…),aij=0或1(i,j=1,2,…)Ex9(思考题(6))仅由0,1构成的无限序列集合T={a0a1a2…an…|nN,an=0or1}为不可数集。构造一个T内的序列r=r1r2…,使rj=1,ajj10,ajj=1j=1,2,…因而T是不可数集。这样，rjajj,即r与所有实数t1,t2,…不同，说明rT.证：假设T是可数集，这与r为T中的序列产生矛盾。类似可证：由0,1,2,…,9构成的无限序列集合也是不可数集。Ex10(思考题(8))

S={(x,y)|x,yR0<x,y<1}为不可数集。证：(x,y)S,令x=0.a1a2…,y=0.b1b2…,ai,bi{0,1,…,9}(i=1,2,…)则0<x<1,0<y<1,作映射f:S(0,1),f((x,y))=0.a1b1a2b2…,显见f为双射。所以S~(0,1),从而S为不可数集。Ex11(思考题(9))

RR…R=Rn是不可数集。证：先证RR=R2是不可数集。

由习题4-4的(4)知，RR~(0,1)(0,1).而Rn~(0,1)n,所以，RR是不可数集。由例4.4.2知，R~(0,1),

由Ex5.5知，(0,1)(0,1)~(0,1)是不可数集，假设(0,1)n-1~(0,1),则(0,1)n=所以Rn也是不可数集.(0,1)n-1(0,1)~(0,1)(0,1)~(0,1)