离散数学古天龙章答案

1、P201. 用枚举法写出下列集合。大于5小于13的所有偶数。A=6,8,10,1220的所有因数A=1,2,4,5,10,20小于20的6的正倍数A=6,12,182. 用描述法写出下列集合能被5整除的整数集合A5x|x是整数平面直角坐标系中单位圆内的点集A|x2+y214. 求下列集合的基数 9 1 3 2 16. 求下列集合的幂集1，2解：空集，1，2，1，2 解：空集，空集，a，空集，a 解：空集，1，2，2，1，2，215. 设全集U=1，2，3,4,5，集合A=1，4，B=1，2，5，C=2，4，确定下列集合。 1，3,5 1，4, 5 空集，1，2，4，1，4，2，418. 对任意

2、集合A，B和C，证明下列各式（A-(BUC)）=(A-B)-C)证：（A-(BUC)）=A(BUC)=A(BC) (A-B)-C)=(AB)C=ABC所以 （A-(BUC)）=(A-B)-C)（A-(BUC)）=(A-C)-B证：（A-(BUC)）=A(BUC)=ABC(A-C)-B)=(AC)B所以 （A-(BUC)）=(A-C)-BP(A)UP(B)P(AUB) 原题有错 （注这里中的“”代表包含于符号）证：任取CP（A）UP(B)由定义CP（A）或CP（B）若CP（A），则CA,则CAUB若CP(B)，则CB,则CAUB故CAUB，即CP(AUB) 证毕P(A)P(B)=P(AB)证：先

3、证P(A)P(B)P(AB)任取 CP(A)P(B)，且CP(A), CP(B)由定义CA且CB,得CAB,即CP(AB)所以 P(A)P(B)P(AB)再证P(AB)P(A)P(B)任取CP(AB),即C=ABCA,且CB,CP(A)且CP(B)所以CP(A)P(B) 得证21. 用集合表示图1.7中各阴影部分。a. (BC)-(ABC) ; b. b.(AB) -(ABC) ;c. U-(AUBUC) ; d .B-(AB)U(BC); e .ABC27. 某班有25个学生，其中14人会打篮球，12 人会打排球，6人会打篮球和排球，5人会打篮球和网球，还有2人会打这三种球。已知6个会打网球

4、的人都会打篮球或排球，求该班同学中不会打球的人数。解：设 A=x|x会打篮球，B=x|x会打排球，C=x|x会打网球 由题意知 |A|=14 ,|B|=12，|C|=6 ,|AB|=6，|AC|=5， |ABC|=2，|C(AUB)|=6， |C(AUB)|=|(CA)U(CB)|=|CA|+|CB|-|C(AUB)|=6, |BC|=6+|ABC|-|AC|=3, 所以 |AUBUC|=|A|+|B+|C|-|AB|-|BC|-(|BC|+|ABC| =14+12+6-6-3-5+2=20 所以 该班同学中不会打球的人有25-20+5人。30. 假设在“离散数学”课程的第一次考试中14个学生

5、得优，第二次考试中18个学生得优。如果22个学生在第一次或第二次考试得优，问有多少学生两次考试都得优。解：设 A=x|x第一次得优的同学，B=x|x第二次得优的同学由已知：|A|=14，|B|=18,|AUB|=22，由 |AUB|=|A|+|B|-|AB|=22所以 |AB|=32-22=10两次考试都得优的有10人。3. 设集合A=1,23，B=1,3,5和C=a,b。求如下笛儿卡积。、（AC）（BC） （AC）(BC)，, 、(AB)C,4. 对于集合A和B,证明。（AB）C(AC)(BC)证： 对任意(AB)C,由笛儿卡积定义，有x(AB),yC.那么xA且xB，由笛儿卡积定义，故 A

6、C (x,y)BC (AC)(BC)故 （AB）C (AC)(BC)对任意(AC)(BC)由交集知，AC,且BC，由笛儿卡积定义，xA,yC,且xB,yCxAB,yC. 由笛儿卡积定义知，(AB)故 （AC(BC) (AB)C, 证毕(AB)C(AC)(BC)证： 任取 (AB)C,由笛儿卡积定义知， xAB, yC, 故AC或BC(AC(BC),(AB)C(AC)(BC)任取(AC)(BC),由笛儿卡积定义知，AC或BC,由笛儿卡积定义知，xA或xB, yC,xAB,yC,由笛儿卡积定义知，(AB)C(AC)(BC)(AB)C证毕 5. 对于集合A=1,2,3和B=2,3,4,6，求从A到B

7、的整除关系R=,R=|xA, yB, x能整除y从B到A的整除关系R=,R=|xB, yA, x能整除y 6. 对于集合A=1,2,3,4,6,8,12， 求 A上的小于等于关系R=, ,A上的不等于关系R=|xA, yA , xyR=, 7. 对于集合A=a,b,c和B=a,a,b,a,c,b,c, 求从P(A)到B的包含关系R|xP(A) xB, xy P(A),a,b,c,a,b,a,c,b,c,a,b,cR=,8. 对于集合A=3,5,7,9和B=2,3,4,6,8,10，求关系矩阵、从A到B的整除关系 0 1 0 1 0 0 0 0 0 0 0 1 MR 0 0 0 0 0 0 0

8、0 0 0 0 0 9. 对于集合A=2,3,4,6,7,8,10，求如下关系的关系矩阵A上的大于关系 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 MR 1 1 1 0 0 0 0 1 1 1 1 0 0 0 1 1 1 1 1 0 0 1 1 1 1 1 1 0 14. 设A=a,b,c,d,e,f,g,其中a,b,c,d,e,f和g分别表示7人，且a,b和c都是18岁，d和e都是21岁，f,和g都是23岁，试给出A上的同龄关系，并用关系矩阵和关系图表示解：R, 1 1 1 0 0 0 0 1 1 1 0 0 0 0 c 1 1 1 0 0 0 0 e

9、MR 0 0 0 1 1 0 0 0 0 0 1 1 0 0 a b f 0 0 0 0 0 1 1 0 0 0 0 0 1 1 g gP6915. 判断集合A=a,b,c上的如下关系所具有的性质。 R1=, 自反性、反对称性、传递性 R4=, 自反性、对称性、传递性 R5=AA 对称性、自反性、传递性 R6= 自反性、对称性、传递性16. 判断集合A=3,5,6，7,10,12上的如下关系所具有的性质。 A上的小于等于关系 自反性、反对称性、传递性 A上的恒等关系 自反性、对称性、反对称性、传递性19. 对于图2.16中给出的集合A=1，2,3上的关系，写出相应的关系表达式和关系矩阵，并分析

10、他们各自具有的性质。R2=, 1 1 1 1 MR2= 1 0 1 1 1 1 2 （对称性） 3 R2 R11=, 1 1 1 0 MR11= 1 1 1 0 1 1 2 3 （自反性、对称性 ）25. 对于集合A=a,b,c到集合B=1,2的关系；R=,和S=,求RS,RS,RS,SR,R和S。解： RS=,; RS=,; RS=; SR=; R=ABR=,; S=ABS=,.27. 对于集合A=1,2,3,4,5,6上的关系R=|(x-y)A，S=|y是x的倍数和 T=|x整除y，y是素数，试写出各关系中的元素，各关系的关系矩阵和关系图， 并计算下列各式。 解：R=, , ,;S=, ,

11、 , ,;T=, , 0 1 1 0 0 0 R的关系图： 1 0 1 1 0 0 1 2 MR= 1 1 0 1 1 0 0 1 1 0 1 1 0 0 1 1 0 1 6 0 0 0 1 1 0 4 3 5其余略； RS=, , , , , , (RT)S RT=, (RT)S=,32. 对于集合A=a,b,c上的如下关系，求各个关系的各次幂。 R1=, R1=, 1 0 0 MR1= 0 1 0 0 0 1 1 0 0 1 0 0 1 0 0 MR1= 1 0 0 MR1=MR1MR1= 1 0 0 = 1 0 0 =MR1 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 （

12、n=0） 0 0 1 MR1的n次方= 1 0 0 1 0 0 (n1) 0 0 0 R3=,; 1 0 0 0 1 1 MR3= 0 1 0 MR3= 0 0 1 0 0 1 0 0 0 0 1 1 0 1 1 0 0 1 MR3=MR3MR3= 0 0 1 0 0 1 = 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 0 0 MR3=MR3MR3= 0 0 0 0 0 1 = 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 MR3的4次方=MR3MR3= 0 0 0 0 0 1 = 0 0 0 0 0 0 0 0 0 0 0

13、 0 33. 对于题29中的关系R和S，求下列各式，并给出所得关系的关系矩阵和关系图。解： 题29中的关系R和S如下：R=,;S=,;IA=,;r(R)=RIA=, ,;S(R)=RR的负一次方=, ,;t(R)=RRR(R的4次方） 0 1 0 0 0 1 0 0 0 1 0 0 1 0 1 0 MR= 1 0 1 0 MR=MRMR= 1 0 1 0 1 0 1 0 = 0 1 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 1 0 1 0 1 0 1 0 0 1 0 0 0 1 0 1 MR=MRMR= 0 1 0

14、1 1 0 1 0 = 1 1 1 0 0 1 0 0 0 0 0 1 1 0 1 0 1 0 1 0 0 1 0 0 0 0 0 1 0 1 0 1 0 1 0 0 1 1 1 0 1 1 1 0 1 0 1 0 1 1 1 1 (MR的4次方）=MRMR= 1 0 1 0 0 0 0 1 = 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 0 1 1 1 1 1 1 1 1 Mt(R)= 1 1 1 1 =AA. 1 1 1 1 37. 对于集合0,1,2,3上的如下关系，判定哪些关系式等价关系。 ,; 是等价关系。 ,; 自反性、对称性成立； 传递性不成立，因为R,R,但R.

15、38. 对于人类集合上的如下关系，判定哪些是等价关系。|x与y有相同的父母； 是等价关系。R,满足自反性；对称性：若R，则R,对称性成立。传递性：若RR，则R,传递性成立。|x与y有相同的年龄 是等价关系。39. 设R和S是集合A上的等价关系，判定下列各式中哪些是等价关系。 RS解： RS仍具有自反性和对称性，但不一定具备传递性，故不是等价关系。任意xA,有R,S,RS. 自反性成立。对任意RS,则R或S.由于RS是等价关系，R或S,则R 对称性成立。传递性不成立，反例：A1,2,3R=,S=, RS 自反性：因为任意xA,有R,且S, 所以RS,自反性成立。对称性：任取RS,故R,且S,由于

16、R和S是等价关系， 故R且S,所以RS。传递性：任取RS，RS，即R且S，R且S， 由于R和S是等价关系，所以R,且S, 所以RS,传递性成立。综上所述，RS是等价关系。41. 对于正整数集合上的关系R=,|ab=cd，试证明R是等价关系。自反性：任取aZ,bZ+， ab=ab， ,R，自反性成立。对称性：任取,R，即ab=cd，cd=ab，故,R， 对称性成立。传递性：任取,R，,R， ab=cd，cd=ef，ab=ef， ,R,传递性成立。 45.对于题37中的等价关系R，求集合A中各元素的等价类和A的商集解：0R=01R=12R=23R=3A/R=0123不是等价关系47.对于集合A=a

17、,b,c,d,e,f,g的划分S=a,c,eb,d,f,g求划分S所对应的等价关系解：R=a,c,ea,c,eUb,db,dUf,gf,g=,52. 画出如下集合A上整除关系的哈斯图解：A=1,2,3,4,5,6,7,8 R=| x,yA,且x能被y整除8 4 6 2 3 5 7 1 A=1,2,3,5,7,11,132357 1113153. 对于题52中关系和，求子集1,2,3,5和子集2,3,7的上界，下界，上确界和下确界解：集合上界下界上确界下确界1,2,3,5无1无12,3,7无无无无集合上界下界上确界下确界1,2,3,5无1无12,3,7无无无无56.对于如图所示的集合A上的偏序关

18、系所对应的哈斯图，求集合A的极大值，极小值，最大值和最小值解：heg f cba极大值极小值最大值最小值bababgfedbcak极大值极小值最大值最小值ha,kh无P861.对于集合A=x,y,z和B=1,2,3,判断下列A到B的关系哪些构成函数,解：不是函数,解：是函数,解：是函数,解：不是函数,解：是函数,解：不是函数2. 判断下列哪些是函数|xR是函数|xZ,yZ,x=y+1是函数3.对于集合A=a,b,c,A到A可以定义多少个不同的函数 =274. 对于集合A=x,y,z,AA到A可以定义多少个不同的函数|AA|=33所以5. 对于集合A=1,2,3，A到AA可以定义多少个不同的函数

19、|AA|=9所以8. 下列哪些是单射函数，满射函数或双射函数f:(是正整数集合)，f(x)=3x;所以是单射函数，不是满射，不是双射f:,f(x)=|x|;所以不是单射函数，不是满射，不是双射集合A=0,1,2,3到B=0,1,2,3,4的函数f,f(x)=;所以不是函数；f:,f(x)=x+1所以是单射函数，是满射，是双射f:,f(x)=所以是单射函数，不是满射，不是双射f:,f(x)=|2x|+1所以不是单射函数，不是满射，不是双射9. 对于集合A和B，且|A|=m，|B|=n,问A到B可以定义多少个不同的函数？A到B可以定义多少个不同的单射函数（mn）A到B可以定义多少个不同的满射函数A

20、到B可以定义多少个不同的双射函数（m=n）14. 对于集合A=a,b,c,d,B=1,2,3和C=a,b,c计算如下函数f：和g：的复合函数f=,g=,=,f=,g=,=,f=,g=,=,f=,g=,=,16. 对于集合A=a,b,c,d和B=1,2,3,4,判断如下函数f:A的逆关系是否为函数f=,逆关系是函数f=,逆关系不是函数f=,逆关系是函数f=,逆关系是函数18. 对于函数f:,f()=,证f是单射函数，满射函数证明：单射性，任取 若，则有x1x2或y1y2又f()= f()=若f()= f()，即=即x1+y1=x2+y2可求得 x1=x2且y1=y2x1-y1=x2-y2若x1x

21、2或y1y2 f()f()即单射性成立满射性，对任意的令f()=,即=有x+y=u x-y=v所以x= y= 不是满射19.对于函数f:,f()=,求逆函数解：f=,|xZ,yZ =,|xZ,yZ令=即 x+2=ux=u-2所以 x-y=v y=u-v-2所以（）=所以=,|uZ,vZP1401 判断下列语句哪些是命题，并给出是命题的语句的真假第28届奥林匹克运动会开幕式在北京举行 是命题，真值为真大于2的偶数均可分解为两个指数的和 是命题，真值不确定蓝色和黑色可以调配成绿色 是命题，真值为假明天我去上海 是命题，真值不确定今天天气真舒服啊 不是命题X+Y sp思路:即证 (pr)(qs)(r

22、(ps)(sp)是否为重言式证: (pr)(qs)(r(ps)(sp) (pr)(qs)(r(ps)(sp) (pr)(qs)(rp)(rs)(sp) (pr)(qs)(rp)(rs)(sp) (pr)(qs)(rp)(rs)sp (pr)(rp)sp (pr)sp prs 非永真 所以，上述推理不是有效推理39.用真值表证明题38中的推理 真值表解:将(pr)(qs)(r(ps)(sp)的真值表列出，非永真，所以推理不正确40.用主析取范式证明题38中的推理 证: (pr)(qs)(r(ps)(sp) M0M2M3M4M6M7M8M9M10M11M12M13M14M1551.符号化下述推理并证明其有效性:如果今天下大雨，则马路上不好行走； 如果马路难走，则我不去逛书店；如果我不去逛书店，则在家学习，所以 如果今天下大雨，则我在家学习。 p:今天下大雨 q:马路上不好走 s:我不去逛书店 r:我在家学习 前提:pq, qs, sr 结论:pr 证明: pq 前提引入 qs 前提引