离散数学古天龙14章答案.doc

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

2、21，4, 35 8空集，1，2 ，4，1 ，4，2，4 918.对任意集合 A，B 和 C，证明下列各式（A-(BUC)）=(A-B)-C) 2证：（A-(BUC)）=A(BUC)=A(BC)(A-B)-C)=(AB)C=ABC所以 （A-(BUC)）=(A-B)-C)（A-(BUC)）=(A-C)-B 3证：（A-(BUC)）=A(BUC)=ABC(A-C)-B)=(AC)B所以 （A-(BUC)）=(A-C)-BP(A)UP(B)P(AUB) 原题有错 （注这里 中的 “”代表包含于符号） 5 5 6证：任取 CP（A）UP(B)由定义CP（A ）或 CP （B）若 CP（A ） ，则

3、CA,则 CAUB若 CP(B)，则 CB,则 CAUB故 CAUB，即 CP(AUB) 证毕P(A)P(B)=P(AB) 6证：先证 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(B

4、C); e .ABC27.某班有 25 个学生，其中 14 人会打篮球，12 人会打排球，6 人会打篮球和排球，5 人会打篮球和网球，还有 2 人会打这三种球。已知 6 个会打网球的人都会打篮球或排球，求该班同学中不会打球的人数。解：设 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

5、|-|BC|-(|BC|+|ABC|=14+12+6-6-3-5+2=20所以 该班同学中不会打球的人有 25-20+5 人。30.假设在“离散数学”课程的第一次考试中 14 个学生得优，第二次考试中 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。求如下笛儿卡积。、 （

6、AC）（BC ）（AC）(BC)，,、(A B)C,4.对于集合 A 和 B,证明。（AB）C(AC)(BC)证：对任意(A B)C,由笛儿卡积定义，有 x(A B),y C.那么 xA 且 xB，由笛儿卡积定义，故 A C (x,y)BC (A C)(BC)故 （AB）C (AC)(BC)对任意 (A C)(BC)由交集知，AC,且B C，由笛儿卡积定义，xA,yC,且 xB,yCxAB,yC. 由笛儿卡积定义知， (AB)故 （AC(BC) (AB)C,证毕(A B)C(AC)(B C)证： 任取 (A B)C,由笛儿卡积定义知，xAB, yC, 故 A C 或 BC (A C(BC),(

7、A B)C(AC)(BC)任取 (AC)(BC),由笛儿卡积定义知， AC 或BC,由笛儿卡积定义知，xA 或 xB, yC,xAB,yC,由笛儿卡积定义知， (AB)C(A C)(B C)(AB)C证毕 5.对于集合 A=1,2,3和 B=2,3,4,6，求从 A 到 B 的整除关系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,

8、求从 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 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

9、 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 eMR 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 ggP6915.判断集合 A=a,b,c上的如下关系所具有的性质。 R1=,自反性、反对称性、传递性 R4

10、=,自反性、对称性、传递性 R5=AA对称性、自反性、传递性 R6=自反性、对称性、传递性16.判断集合 A=3,5,6，7,10,12上的如下关系所具有的性质。 A 上的小于等于关系自反性、反对称性、传递性 A 上的恒等关系自反性、对称性、反对称性、传递性19.对于图 2.16 中给出的集合 A=1，2,3上的关系，写出相应的关系表达式和关系矩阵，并分析他们各自具有的性质。R2=, 1 1 1 1 MR2= 1 0 1 1 1 1 2 （对称性）3R2 R11=,1 1 1 0 MR11= 1 1 1 0 1 1 23 （自反性、对称性 ）25.对于集合 A=a,b,c到集合 B=1,2的关

11、系；R=,和 S=,求 RS,RS,RS,S R,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=,;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 35其余略； RS=, (RT)SRT=,(RT)S=,32.

12、对于集合 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 （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

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

14、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 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 次方）=MR

15、MR= 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 =A A. 1 1 1 1 37.对于集合0,1,2,3上的如下关系，判定哪些关系式等价关系。 ,;是等价关系。 ,;自反性、对称性成立；传递性不成立，因为R,R, 但 R.38.对于人类集合上的如下关系，判定哪些是等价关系。|x 与 y 有相同的父母；是等价关系。 R,满足自反性；对称性：若R，则R,对称性成立。传递性：若R R ，则R,传递性成立。|x 与 y 有相同的年龄是等价关系。39.设 R 和 S 是集合 A 上的

16、等价关系，判定下列各式中哪些是等价关系。 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,由于 R 和 S 是等价关系，故R 且S, 所以 RS。传递性：任取RS ，R S ，即R 且S ，R 且 S，由于 R 和 S 是等价关系，所以R,且S,所以R S,传递性成立。综上所述，RS 是等价关系。41.对于正整数集合上的关系 R=,|ab=cd，试证明 R 是等价关系。自反性：任取 aZ ,bZ+， ab=ab，,R，自反性成立。对称性：任取,R，即 ab=cd，cd=ab，故, R，对称性成立。传递性：任取,R，,R ，