《离散数学》试题及答案(可打印修改).pdf

离散数学试题及答案第 1 页 共 13 页一、填空题一、填空题 1 设集合 A,B，其中 A1,2,3,B=1,2,则 A-B 3 ;(A)-(B)3,1,3,2,3,1,2,3 .2.设有限集合 A,|A|=n,则|(AA)|=.22n3.设集合 A=a,b,B=1,2,则从 A 到 B 的所有映射是 1=(a,1),(b,1),2=(a,2),(b,2),3=(a,1),(b,2),4=(a,2),(b,1),其中双射的是 3,4 .4.已知命题公式 G(PQ)R，则 G 的主析取范式是 (P QR)5.设 G 是完全二叉树，G 有 7 个点，其中 4 个叶点，则 G 的总度数为 12 ，分枝点数为 3 .6 设 A、B 为两个集合,A=1,2,4,B=3,4,则从 AB 4 ;AB1,2,3,4;AB 1,2 .7.设 R 是集合 A 上的等价关系，则 R 所具有的关系的三个特性是 自反性,对称性 传递性 .8.设命题公式 G(P(QR)，则使公式 G 为真的解释有 (1,0,0),(1,0,1),(1,1,0)9.设集合 A1,2,3,4,A 上的关系 R1=(1,4),(2,3),(3,2),R2=(2,1),(3,2),(4,3),则R1R2=(1,3),(2,2),(3,1),R2R1=(2,4),(3,3),(4,2)_ R12=(2,2),(3,3).10.设有限集 A,B，|A|=m,|B|=n,则|(AB)|=.nm211 设 A,B,R 是三个集合，其中 R 是实数集，A=x|-1x1,xR,B=x|0 x 2,xR,则 A-B=-1=x0 ,B-A=x|1 x 6 (D)下午有会吗？5 设 I 是如下一个解释：Da,b,0 1 0 1b)P(b,a)P(b,b)P(a,),(aaP则在解释 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 设命题公式 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)以上答案都不对11 下列关于集合的表示中正确的为(B )。(A)aa,b,c(B)aa,b,c(C)a,b,c (D)a,ba,b,c12 命题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)9 条 (B)5 条 (C)6 条 (D)11 条.14.设 G 是 5 个顶点的完全图，则从 G 中删去(A )条边可以得到树.(A)6 (B)5 (C)10 (D)4.15.设图 G 的相邻矩阵为，则 G 的顶点数与边数分别为(D ).0110110101110110010111110123456离散数学试题及答案第 3 页 共 13 页(A)4,5 (B)5,6 (C)4,10 (D)5,8.三、计算证明题三、计算证明题1.设集合 A1,2,3,4,6,8,9,12，R 为整除关系。(1)画出半序集(A,R)的哈斯图；(2)写出 A 的子集 B=3,6,9,12的上界，下界，最小上界，最大下界；(3)写出 A 的最大元，最小元，极大元，极小元。解：（解：（1）124836129124836129（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 的关系矩阵.解：（解：（1）（2）1 2 3 4 1000110011101111RM 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)(x)(x)+3x/4+3,(4)(x)(x)/42x/4=x/2,(5)()+32x/4+3x/2+3.4.设 I 是如下一个解释：D=2,3,abf(2)f(3)P(2,2)P(2,3)P(3,2)P(3,3)离散数学试题及答案第 4 页 共 13 页32320011试求(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)=(P(2,2)P(3,2)(P(2,3)P(3,3)=(01)(01)=11=1.5.设集合 A1,2,4,6,8,12，R 为 A 上整除关系。(1)画出半序集(A,R)的哈斯图；(2)写出 A 的最大元，最小元，极大元，极小元；(3)写出 A 的子集 B=4,6,8,12的上界，下界，最小上界，最大下界.解：解：(1)(2)无最大元，最小元 1，极大元 8,12;极小元是 1.(3)B 无上界，无最小上界。下界 1,2;最大下界 2.6.设命题公式 G=(PQ)(Q(PR),求 G 的主析取范式。解：解：G=(PQ)(Q(PR)=(PQ)(Q(PR)=(PQ)(Q(PR)离散数学试题及答案第 5 页 共 13 页=(PQ)(QP)(QR)=(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)=(PQR)(PQR)(PQR)(PQR)(PQR)=m3m4m5m6m7=(3,4,5,6,7).7.(9 分)设一阶逻辑公式：G=(xP(x)yQ(y)xR(x)，把 G 化成前束范式.解：解：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.设 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）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)关系图:11.通过求主析取范式判断下列命题公式是否等价：(1)G=(PQ)(PQR)(2)H=(P(QR)(Q(PR)解：解：bacdr(R)bacds(R)bacdt(R)bacdr(R)bacdr(R)bacds(R)bacds(R)bacdt(R)bacdt(R)离散数学试题及答案第 6 页 共 13 页G(PQ)(PQR)(PQR)(PQR)(PQR)m6m7m3(3,6,7)H=(P(QR)(Q(PR)(PQ)(QR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)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).(1)试写出 R 和 S 的关系矩阵；(2)计算 RS,RS,R1,S1R1.解：解：(1)0000100001000101RM1000000011000010SM(2)RS(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)PRP(2)RPQ(1)(3)PQP离散数学试题及答案第 7 页 共 13 页(4)RQQ(2)(3)(5)QRQ(4)(6)RSP(7)QSQ(5)(6)(8)QSQ(7)2.设 A,B 为任意集合，证明：(A-B)-C=A-(BC).解：解：(A-B)-C=CBAII)()()()(CBACBACBAUUIII 3.(本题 10 分)利用形式演绎法证明：AB,CB,CD蕴涵 AD。解：解：(1)AD(附加)(2)ABP(3)BQ(1)(2)(4)CBP(5)BCQ(4)(6)CQ(3)(5)(7)CDP(8)DQ(6)(7)(9)ADD(1)(8)所以 AB,CB,CD蕴涵 AD.4.(本题 10 分)A,B 为两个任意集合，求证：A(AB)=(AB)B.解：解：4.A(AB)=A(AB)A(AB)离散数学试题及答案第 8 页 共 13 页(AA)(AB)(AB)(AB)AB而(AB)B=(AB)B=(AB)(BB)=(AB)=AB所以：A(AB)=(AB)B.参考答案参考答案一、填空题1.3;3,1,3,2,3,1,2,3.2.22n3.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).离散数学试题及答案第 9 页 共 13 页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)(2)B 无上界，也无最小上界。下界 1,3;最大下界是 3.(3)A 无最大元，最小元是 1，极大元 8,12,90+;极小元是 1.2.R=(1,1),(2,1),(2,2),(3,1),(3,2),(3,3),(4,1),(4,2),(4,3),(4,4).(1)(2)1000110011101111RM 3.(1)(x)(x)+32x+32x+3.(2)(x)(x)+3(x+3)+3x+6,(3)(x)(x)+3x/4+3,124836129124836129 1 2 3 4 离散数学试题及答案第 10 页 共 13 页(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,f(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.(1)(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)24168122416812离散数学试题及答案第 11 页 共 13 页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)关系图:11.G(PQ)(PQR)(PQR)(PQR)(PQR)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.13.(1)0000100001000101RM1000000011000010SM(2)RS(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蕴涵 QSbacdr(R)bacds(R)bacdt(R)bacdr(R)bacdr(R)bacds(R)bacds(R)bacdt(R)bacdt(R)离散数学试题及答案第 12 页 共 13 页(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)=A-(BC)3.证明：AB,CB,CD蕴涵 AD(1)AD(附加)(2)ABP(3)BQ(1)(2)(4)CBP(5)BCQ(4)(6)CQ(3)(5)(7)CDP(8)DQ(6)(7)(9)ADD(1)(8)所以 AB,CB,CD蕴涵 AD.5.证明：A(AB)=A(AB)A(AB)(AA)(AB)(AB)(AB)AB离散数学试题及答案第 13 页 共 13 页而(AB)B=(AB)B=(AB)(BB)=(AB)=AB所以：A(AB)=(AB)B.