《离散数学》试题及答案.pdf
离散数学试题及答案一、填空题一、填空题1 1 设集合 A,B，其中 A1,2，3,B=1,2，则 A-B33；33，11，3 3，2 2，3,13,1，2,32,3.2.设有限集合 A，|A|=n，则（AA）=2 2.3 3。设集合 A=a，b,B=1，2,则从 A 到 B 的所有映射是 1 1=(a a，1 1）,(,(b b，1),1),2 2=(a a，2)2)，(b b,2,2），3 3=（a a，1)1)，(b b，2 2）,4 4=（a a,2),2)，（b b,1),1)，其中双射的是 3 3,4 4。4。已知命题公式 G(PQ)R，则 G 的主析取范式是（P P Q QR R）5。设 G 是完全二叉树，G 有 7 个点,其中 4 个叶点，则 G 的总度数为1212,分枝点数为3 3.6 6 设 A、B 为两个集合，A=1,2，4,B=3，4，则从 AB44;AB1,21,2，3 3，4 4；AB11，2 2。7.设 R 是集合 A 上的等价关系，则R 所具有的关系的三个特性是自反性，对称性传递性。8 8。设命题公式 G(P(QR），则使公式 G 为真的解释有（1 1，0 0，0),0),(1(1，0,10,1）,（1,11,1，0)0)9.设集合 A1，2,3，4，A 上的关系 R1=(1,4），（2，3)，（3，2）,R2=（2，1)，（3,2),（4,3),则 R1R2=（1,31,3）,（2,2),(32,2),(3，1)1),R2R1=(2(2，4)4)，(3(3，3 3），（4,24,2）_ _R12=(2(2，2),2),（3 3，3 3）。mnn n2 2(A）-（B)10.设有限集 A,B，|A=m,|B=n，则|(AB）=2。1111 设 A，B,R 是三个集合，其中R 是实数集，A=x|-1x1，xR,B=x|0 x 2，xR，则 AB=1 1=x0=x0,B-A=x|1 x 2x|1 x 6(D）下午有会吗?5 5 设 I 是如下一个解释：Da,b,21P(a,a)P(a,b)P(b,a)P(b,b)1010则在解释 I 下取真值为 1 的公式是（D）。（A)xyP(x,y)（B）xyP（x，y）(C）xP(x，x)（D）xyP(x，y）.6.若供选择答案中的数值表示一个简单图中各个顶点的度，能画出图的是（C).(A）(1,2，2,3，4，5)（B)(1，2，3,4，5,5）（C）（1，1，1,2，3）(D）（2,3,3，4，5,6）.7.设 G、H 是一阶逻辑公式，P 是一个谓词，GxP(x），HxP(x),则一阶逻辑公式 GH是(C）.(A）恒真的(B)恒假的(C)可满足的(D）前束范式。8 8设命题公式 G（PQ)，HP（QP),则 G 与 H 的关系是(A）.（A）GH（B)HG（C）GH(D)以上都不是。9设 A,B 为集合，当(D）时 ABB。(A)AB（B)AB（C)BA（D)AB.10设集合 A=1,2,3,4，A 上的关系 R（1，1)，（2,3）,（2,4）,(3,4）,则 R 具有（B)。(A)自反性（B）传递性(C）对称性(D)以上答案都不对1111下列关于集合的表示中正确的为（B)。（A)aa，b，c(B）aa,b，c（C）a，b,c（D)a，ba，b，c1212 命题xG（x)取真值 1 的充分必要条件是(A)。(A)对任意 x，G（x）都取真值 1。（B）有一个 x0，使 G(x0)取真值 1.（C)有某些 x，使 G（x0）取真值 1.（D）以上答案都不对。13。设 G 是连通平面图，有 5 个顶点，6 个面，则 G 的边数是(A A)。第 2 页 共 13 页离散数学试题及答案（A）9 条(B）5 条（C)6 条(D)11条.14.设 G 是 5 个顶点的完全图，则从G 中删去（A）条边可以得到树。(A)6(B)5（C)10（D）4.0111110100，则 G 的顶点数与边数分别为（D）15。设图 G 的相邻矩阵为。110111010110110(A)4，5(B)5，6(C）4,10三、计算证明题三、计算证明题(D）5，8。1 1。设集合 A1,2，3,4，6，8,9，12，R 为整除关系。(1)画出半序集(A,R）的哈斯图;(2)写出 A 的子集 B=3，6,9，12的上界，下界，最小上界,最大下界;(3)写出 A 的最大元，最小元，极大元，极小元。解：解：（1 1）8 84 42 21 112126 63 39 9（2）B 无上界，也无最小上界。下界1,3；最大下界是 3（3）A 无最大元，最小元是1，极大元 8，12,9；极小元是 12.设集合 A1,2，3，4,A 上的关系 R(x,y)|x，yA 且 x y,求(1)画出 R 的关系图;(2)写出 R 的关系矩阵。14解解:（1)1)2 1 1 1 13（2 2）MMR R 1 1 1 10 00 00 0 1 10 00 0 1 11 10 0 1 11 11 1 3.设 R 是实数集合，是 R 上的三个映射，（x）=x+3,（x）=2x，（x)x/4，试求复合映射，,，.解：解：（1)(x）)(x）+32x+32x+3.(2）(x)（x)+3（x+3）+3x+6,第 3 页 共 13 页离散数学试题及答案(3）(（x）)(x)+3x/4+3，(4)（(x）（x)/42x/4=x/2,(5)()+32x/4+3x/2+3.4.设 I 是如下一个解释：D=2,3,a3b2f（2)3f（3）2P（2，2）0P(2,3）P(3，2）P(3,3）011试求（1)P（a，f（a）P（b，f(b)；(2)xy P(y，x）.解解:（1)P（a,f(a）)P（b，f（b）)=P（3，f（3)P(2,f（2）)=P(3，2）P（2,3）=10=0.(2)xy P（y，x)=x(P(2,x）P（3,x)）5 5。设集合 A1,2，4，6,8，12，R 为 A 上整除关系.(1)画出半序集（A，R）的哈斯图；(2)写出 A 的最大元，最小元，极大元，极小元；(3)写出 A 的子集 B=4,6,8,12的上界,下界,最小上界，最大下界。解：解：（1 1）（2 2）无最大元,最小元 1，极大元 8,12;极小元是 1.(3)(3)B 无上界,无最小上界。下界 1,2；最大下界 2。=(P(2,2）P(3,2)（P(2，3)P（3，3）=（01)（01）=11=1.第 4 页 共 13 页离散数学试题及答案6.设命题公式 G=(PQ)（Q(PR)）,求 G 的主析取范式。解：解：G=（PQ)(Q(PR）)=(PQ)(Q（PR）)=（PQ)(Q(PR）)=（PQ）（QP)(QR)=(PQR)(PQR）（PQR)(PQR）（PQR)（PQR)7.(9 分）设一阶逻辑公式：G=(xP(x)yQ(y)）xR（x），把 G 化成前束范式.解：解：G=(xP（x）yQ(y)xR(x)9。设 R 是集合 A=a，b，c，d。R 是 A 上的二元关系，R=(a，b），（b,a），（b,c),（c，d),(1)求出 r(R),s（R）,t（R）；(2)画出 r（R）,s(R),t（R）的关系图.解解:（1 1）第 5 页 共 13 页=（PQR）（PQR）（PQR)（PQR）（PQR)=m3m4m5m6m7=(3，4,5，6,7）.=（xP(x）yQ（y）xR(x)=(xP(x)yQ（y）xR(x)=(xP(x)yQ(y）)zR（z）=xyz（(P(x)Q(y)R(z)离散数学试题及答案r（R）RIA（a,b),（b，a）,（b,c),（c,d）,(a,a)，（b，b)，(c，c）,（d，d),s(R)RR1（a,b)，（b，a),(b,c），(c，b)（c，d）,(d，c）,t（R)RR2R3R4（a，a),（a，b),（a,c），(a,d)，(b，a）,（b，b),(b，c)，（b，d)，(c，d）；(2)关系图:1111。通过求主析取范式判断下列命题公式是否等价：（1）G=（PQ)（PQ R）(2)H=(P(QR）(Q（PR）)解：解：G(PQ）(PQ R)(PQ R)（PQ R）（PQ R）m6m7m3 (3,6，7）H=（P（Q R)(Q（PR）)(PQ）(QR）（PQ R）（PQ R）（PQ R)(PQ R）（PQ R)（PQ R)(PQ R)（PQ R）（PQ R)m6m3m7G，H 的主析取范式相同,所以 G=H.13.设 R 和 S 是集合 Aa，b,c,d上的关系，其中R(a,a),（a,c），(b，c），(c,d),S（a，b)，（b,c)，(b,d）,(d,d)。a ab br(R)r(R)d dc ca ab bs(R)s(R)d da ab bt(R)t(R)d dc cc c(1)试写出 R 和 S 的关系矩阵；(2）计算 R S,RS，R1，S1R1。第 6 页 共 13 页离散数学试题及答案解：解：10（1)MR0001000010MS00100000100011000001(2）R S（a，b),(c，d),RS（a,a），（a,b）,(a,c）,(b,c)，（b,d),(c，d)，(d,d），R1（a，a)，(c,a），(c,b），（d，c）,S1R1(b，a)，（d,c）。四、证明题四、证明题1。利用形式演绎法证明:PQ，RS，PR蕴涵 QS。解：解：（1）PR(2）RP（3)PQPQ(1）PQ(2)（3)（4）RQ(5）QR（6）RS(7)QSQ(4)PQ（5)（6)Q（7）（8）QS2.设 A，B 为任意集合，证明:（A-B）C=A-(BC).解：解：(A-B）-C=(A B)C A(BC)A(BC)A(BC)3.(本题 10 分）利用形式演绎法证明:AB，CB，CD蕴涵 AD。解：解：（1)AD（附加)P第 7 页 共 13 页(2）AB离散数学试题及答案(3)BQ（1)(2）PQ(4)(4）CB(5）BC(6)CQ（3)(5）P(7）CD（8）D(9)ADQ(6)（7)D(1）(8)所以 AB,CB,CD蕴涵 AD。4。（本题 10 分）A，B 为两个任意集合，求证:A(AB）=（AB）B。解：解：4.A（AB）=A(AB）A(AB)（AA)(AB)(AB)(AB）AB而(AB)B=（AB)B=(AB）(BB)=(AB)=AB所以:A（AB)=(AB)B.第 8 页 共 13 页离散数学试题及答案参考答案参考答案一、填空题1.3；3，1，3，2，3,1，2，3.2.2 2.n n2 23.1=(a，1），(b,1)，2=（a,2）,(b，2），3=(a,1）,（b,2),4=（a，2）,（b,1);3，4。4.（PQR）.5.12，3.6.4，1，2,3,4,1,2.7.自反性；对称性；传递性。8.（1，0,0）,(1，0，1),(1，1,0）.9.(1，3)，（2，2),(3，1)；（2，4)，（3,3),(4,2）；（2，2），(3,3）。10.2mn。11.x 1x 0，xR;x|1 x 2，xR；x|0 x1,xR。12.12；6。13.(2,2)，（2，4），(2，6），（3,3),（3,6），（4,4),（5，5），(6，6）.14.x（P（x)Q(x)）.15.21。16.（R（a)R(b）（S（a）S(b）.17.（1，3），(2,2)；（1，1),(1，2），（1，3)。二、选择题二、选择题1.C。2.D.3.B.4。B.5.D.6。C。7.C。8.A.9。D.10.B。11.B。13。A.14。A。15。D三、计算证明题三、计算证明题1.(1）8 84 42 21 112126 63 39 9第 9 页 共 13 页离散数学试题及答案(2)B 无上界，也无最小上界。下界1,3;最大下界是 3.(3）A 无最大元，最小元是1，极大元 8,12，90+；极小元是 1.2.2.R=(1,1），(2,1），（2,2),(3，1），(3,2），(3,3),(4，1）,（4，2)，(4,3),(4，4)。（1)1423 1 10 00 00 0(2)MM1 11 10 00 0 R R 1 11 11 10 0 1 11 11 11 1 3.(1)(（x）(x）+32x+32x+3.（2)（(x)(x)+3（x+3)+3x+6,(3）(（x）)（x）+3x/4+3，(4)(（x)(x)/42x/4=x/2,（5）(）+32x/4+3x/2+3。4.（1)P(a，f(a）)P（b,f(b)）=P（3，f（3）P（2，=P（3,2)P(2,3)=10=0.（2）xy P(y,x)=x（P(2，x）P(3,x）)=(P(2,2)P(3，2）)（P(2，3)P（3，3)）=(01)（01）=11=1。5 5。（1）128462第 10 页 共 13 页1f（2）离散数学试题及答案（2）无最大元，最小元1，极大元 8,12;极小元是 1.(3）B 无上界,无最小上界。下界 1,2；最大下界 2。6.G=(PQ)(Q（PR)=（PQ）（Q（PR)）=(PQ)（Q(PR）=（PQ)(QP)（QR）=（PQR)(PQR)（PQR）（PQR)（PQR）（PQR)=（PQR)(PQR）(PQR)(PQR）(PQR）=m3m4m5m6m7=(3,4，5，6,7）.7.G=(xP（x）yQ（y)）xR（x）=（xP(x)yQ（y)）xR(x）=（xP(x)yQ(y）)xR(x)=（xP（x)yQ(y)zR（z）=xyz(P(x）Q（y)）R（z）)9。（1）r(R）RIA（a，b)，(b，a）,（b,c）,(c，d），(a，a），(b，b），（c,c）,（d,d),s（R）RR1（a,b)，(b，a),（b,c），(c,b）（c,d）,(d，c），t（R)RR2R3R4（a，a），（a，b)，（a,c),(a,d)，(b,a），（b，b），(b，c)，(b，d）,（c，d）；（2)关系图：a ab br(R)r(R)d dc ca ab bs(R)s(R)d da ab bt(R)t(R)d dc cc c1111。G（PQ)（PQR)（PQR)（PQR)（PQR）第 11 页 共 13 页离散数学试题及答案m6m7m3（3，6,7）H=（P(QR)）（Q（PR）)(PQ）(QR)(PQR）(PQR)(PQR)（PQR)(PQR)(PQR）（PQR)(PQR)(PQR)m6m3m7(3，6,7）G，H 的主析取范式相同,所以 G=H。1010010013。（1)M0010011R0001M0S000000000001（2)R S（a，b),(c，d),RS（a,a)，(a，b）,(a，c)，(b，c)，(b，d），（c,d）,（d，R1（a,a),(c，a),(c，b）,（d，c）,S1R1（b,a),(d,c)。四四 证明题证明题1。证明：PQ，RS,PR蕴涵 QS（1)PRP（2)RPQ(1）（3）PQP（4)RQQ(2)（3）(5)QRQ(4）(6)RSP(7）QSQ(5)(6)（8)QSQ（7）2。证明:(A-B）C=（AB)C=A(BC)=A(BC)第 12 页 共 13 页d）,离散数学试题及答案=A（BC)3.证明：A B，C B,CD蕴涵 A D（1）AD(附加）PQ(1）（2）P（2)A B(3)B（4）C B(5)B C(6)CQ（4)Q（3)（5）P(7）CD（8）DQ（6)（7)D（1)(8)（9）A D所以 A B，C B，CD 蕴涵 A D。5.证明:A(AB）=A（A B）A(AB)（A A）（A B)(AB）（A B）A B而(AB）B=（A B)B=（A B)（BB)=（A B)=AB所以:A（A B）=（A B）B.第 13 页 共 13 页
