离散数学试题及答案.pdf

第 1 页 共 18 页离散数学试题及答案离散数学试题及答案一、填空题一、填空题 1 设集合 A,B，其中 A1,2,3,B=1,2,则 A-B_;(A)-(B)_.2.设有限集合 A,|A|=n,则|(AA)|=_.3.设集合 A=a,b,B=1,2,则从 A 到 B 的所有映射是_ _,其中双射的是_.4.已知命题公式 G(PQ)R，则 G 的主析取范式是_.5.设 G 是完全二叉树，G 有 7 个点，其中 4 个叶点，则 G 的总度数为_，分枝点数为_.6 设 A、B 为两个集合,A=1,2,4,B=3,4,则从 AB_;AB_;AB _.7.设 R 是集合 A 上的等价关系，则 R 所具有的关系的三个特性是_,_,_.8.设命题公式 G(P(QR)，则使公式 G 为真的解释有_，_,_.9.设集合 A1,2,3,4,A 上的关系 R1=(1,4),(2,3),(3,2),R1=(2,1),(3,2),(4,3),则R1R2=_,R2R1=_,R12=_.10.设有限集 A,B，|A|=m,|B|=n,则|(AB)|=_.11 设 A,B,R 是三个集合，其中 R 是实数集，A=x|-1x1,xR,B=x|0 x 6 (D)下午有会吗？5 设 I 是如下一个解释：Da,b,0 1 0 1b)P(b,a)P(b,b)P(a,),(aaP则在解释 I 下取真值为 1 的公式是().(A)xyP(x,y)(B)xyP(x,y)(C)xP(x,x)(D)xyP(x,y).6.若供选择答案中的数值表示一个简单图中各个顶点的度，能画出图的是().(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 是().123456第 3 页 共 18 页(A)恒真的 (B)恒假的 (C)可满足的 (D)前束范式.8 设命题公式 G(PQ)，HP(QP)，则 G 与 H 的关系是()。(A)GH (B)HG (C)GH (D)以上都不是.9 设 A,B 为集合，当()时 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 具有()。(A)自反性 (B)传递性(C)对称性 (D)以上答案都不对11 下列关于集合的表示中正确的为()。(A)aa,b,c (B)aa,b,c(C)a,b,c (D)a,ba,b,c12 命题xG(x)取真值 1 的充分必要条件是().(A)对任意 x，G(x)都取真值 1.(B)有一个 x0，使 G(x0)取真值 1.(C)有某些 x，使 G(x0)取真值 1.(D)以上答案都不对.13.设 G 是连通平面图，有 5 个顶点，6 个面，则 G 的边数是().(A)9 条 (B)5 条 (C)6 条 (D)11 条.14.设 G 是 5 个顶点的完全图，则从 G 中删去()条边可以得到树.(A)6 (B)5 (C)10 (D)4.15.设图 G 的相邻矩阵为，则 G 的顶点数与边数分别为().0110110101110110010111110(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的上界，下界，最小上界，最大下界；第 4 页 共 18 页(3)写出 A 的最大元，最小元，极大元，极小元。2.设集合 A1,2,3,4，A 上的关系 R(x,y)|x,yA 且 x y,求(1)画出 R 的关系图；(2)写出 R 的关系矩阵.3.设 R 是实数集合，,是 R 上的三个映射，(x)=x+3,(x)=2x,(x)x/4,试求复合映射，,，.4.设 I 是如下一个解释：D=2,3,abf(2)f(3)P(2,2)P(2,3)P(3,2)P(3,3)32320011试求(1)P(a,f(a)P(b,f(b);(2)xy P(y,x).5.设集合 A1,2,4,6,8,12，R 为 A 上整除关系。(1)画出半序集(A,R)的哈斯图；(2)写出 A 的最大元，最小元，极大元，极小元；(3)写出 A 的子集 B=4,6,8,12的上界，下界，最小上界，最大下界.6.设命题公式 G=(PQ)(Q(PR),求 G 的主析取范式。7.(9 分)设一阶逻辑公式：G=(xP(x)yQ(y)xR(x)，把 G 化成前束范式.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)的关系图.11.通过求主析取范式判断下列命题公式是否等价：(1)G=(PQ)(PQR)(2)H=(P(QR)(Q(PR)第 5 页 共 18 页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.利用形式演绎法证明：PQ,RS,PR蕴涵 QS。2.设 A,B 为任意集合，证明：(A-B)-C=A-(BC).3.(本题 10 分)利用形式演绎法证明：AB,CB,CD蕴涵 AD。4.(本题 10 分)A,B 为两个任意集合，求证：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).10.2mn.11.x|-1x 0,xR;x|1 x 2,xR;x|0 x1,xR.12.12;6.第 6 页 共 18 页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 第 7 页 共 18 页(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)24168122416812第 8 页 共 18 页=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)关系图: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)bacdr(R)bacds(R)bacdt(R)bacdr(R)bacdr(R)bacds(R)bacds(R)bacdt(R)bacdt(R)第 9 页 共 18 页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蕴涵 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)第 10 页 共 18 页=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.4.证明：A(AB)=A(AB)A(AB)(AA)(AB)(AB)(AB)AB而(AB)B=(AB)B=(AB)(BB)=(AB)第 11 页 共 18 页=AB所以：A(AB)=(AB)B.离散数学试题（离散数学试题（A A 卷及答案）卷及答案）一、（10 分）某项工作需要派 A、B、C 和 D 4 个人中的 2 个人去完成，按下面 3 个条件，有几种派法？如何派？(1)若 A 去，则 C 和 D 中要去 1 个人；(2)B 和 C 不能都去；(3)若 C 去，则 D 留下。解 设 A：A 去工作；B：B 去工作；C：C 去工作；D：D 去工作。则根据题意应有：ACD，(BC)，CD 必须同时成立。因此(ACD)(BC)(CD)(A(C D)(CD)(BC)(CD)(A(C D)(CD)(BC)(BD)C(CD)(ABC)(ABD)(AC)(ACD)(C DBC)(C DBD)(C DC)(C DCD)(CDBC)(CDBD)(CDC)(CDCD)FF(AC)FF(C DB)FF(CDB)F(CD)F(AC)(BC D)(CDB)(CD)(AC)(BC D)(CD)T故有三种派法：BD，AC，AD。二、（15 分）在谓词逻辑中构造下面推理的证明：某学术会议的每个成员都是专家第 12 页 共 18 页并且是工人，有些成员是青年人，所以，有些成员是青年专家。解：论域：所有人的集合。()：是专家；()：是工人；()：是青年人；SxxWxxYxx则推理化形式为：()()，()()()xSxWxxYxxSxYx下面给出证明：(1)()PxYx(2)(c)T(1)，ESY(3)()()PxSxWx(4)(c)(c)T(3)，USSW(5)(c)T(4)，IS(6)(c)(c)T(2)(5)，ISY(7)()()T(6)，EGxSxYx三、（10 分）设 A、B 和 C 是三个集合，则 AB(BA)。证明：ABx(xAxB)x(xBxA)x(xAxB)x(xBxA)x(xAxB)x(xBxA)x(xAxB)x(xAxB)(x(xAxB)x(xAxB)(x(xAxB)x(xBxA)(BA)。四、（15 分）设 A1，2，3，4，5，R 是 A 上的二元关系，且R，求 r(R)、s(R)和 t(R)。解 r(R)RIA，s(R)RR1，R2，R3，第 13 页 共 18 页R4，R2t(R)Ri，。五、（10 分）R 是非空集合 A 上的二元关系，若 R 是对称的，则 r(R)和 t(R)是对称的。证明 对任意的 x、yA，若 xr(R)y，则由 r(R)RIA得，xRy 或 xIAy。因 R 与 IA对称，所以有 yRx 或 yIAx，于是 yr(R)x。所以 r(R)是对称的。下证对任意正整数 n，Rn对称。因 R 对称，则有 xR2yz(xRzzRy)z(zRxyRz)yR2x，所以 R2对称。若对nR称，则 xyz(xzzRy)z(zxyRz)yx，所以对称。因此，对任意1nRnRnR1nR1nR正整数 n，对称。nR对任意的 x、yA，若 xt(R)y，则存在 m 使得 xRmy，于是有 yRmx，即有 yt(R)x。因此，t(R)是对称的。六、（10 分）若 f：AB 是双射，则 f1：BA 是双射。证明 因为 f：AB 是双射，则 f1是 B 到 A 的函数。下证 f1是双射。对任意 xA，必存在 yB 使 f(x)y，从而 f1(y)x，所以 f1是满射。对任意的 y1、y2B，若 f1(y1)f1(y2)x，则 f(x)y1，f(x)y2。因为 f：AB是函数，则 y1y2。所以 f1是单射。综上可得，f1：BA 是双射。七、（10 分）设是一个半群，如果 S 是有限集，则必存在 aS，使得a*aa。证明 因为是一个半群，对任意的 bS，由*的封闭性可知，b2b*bS，b3b2*bS，bnS，。因为 S 是有限集，所以必存在 ji，使得。令 pji，则*。所以ibjbjbpbjb对 qi，有*。qbpbqb第 14 页 共 18 页因为 p1，所以总可找到 k1，使得 kpi。对于S，有kpb*(*)*。kpbpbkpbpbpbkpbkpbkpb令 a，则 aS 且 a*aa。kpb八、（20 分）（1）若 G 是连通的平面图，且 G 的每个面的次数至少为 l(l3)，则G 的边数 m 与结点数 n 有如下关系：m(n2)。2ll证明 设 G 有 r 个面，则 2mlr。由欧拉公式得，nmr2。于是，riifd1)(m(n2)。2ll（2）设平面图 G是自对偶图，则|E|2(|V|1)。证明 设 G*是连通平面图 G的对偶图，则 G*G，于是|F|V*|V|，将其代入欧拉公式|V|E|F|2 得，|E|2(|V|1)。第 15 页 共 18 页离散数学试题（离散数学试题（B B 卷及答案）卷及答案）一、（10 分）证明(PQ)(PR)(QS)SR证明 因为 SRRS，所以，即要证(PQ)(PR)(QS)RS。(1)R 附加前提(2)PR P(3)P T(1)(2)，I(4)PQ P(5)Q T(3)(4)，I(6)QS P(7)S T(5)(6)，I(8)RS CP(9)SR T(8)，E二、（15 分）根据推理理论证明：每个考生或者勤奋或者聪明，所有勤奋的人都将有所作为，但并非所有考生都将有所作为，所以，一定有些考生是聪明的。设 P(e)：e 是考生，Q(e)：e 将有所作为，A(e)：e 是勤奋的，B(e)：e 是聪明的，个体域：人的集合，则命题可符号化为：x(P(x)(A(x)B(x)，x(A(x)Q(x)，x(P(x)Q(x)x(P(x)B(x)。(1)x(P(x)Q(x)P(2)x(P(x)Q(x)T(1)，E(3)x(P(x)Q(x)T(2)，E(4)P(a)Q(a)T(3)，ES(5)P(a)T(4)，I(6)Q(a)T(4)，I(7)x(P(x)(A(x)B(x)P第 16 页 共 18 页(8)P(a)(A(a)B(a)T(7)，US(9)A(a)B(a)T(8)(5)，I(10)x(A(x)Q(x)P(11)A(a)Q(a)T(10)，US(12)A(a)T(11)(6)，I(13)B(a)T(12)(9)，I(14)P(a)B(a)T(5)(13)，I(15)x(P(x)B(x)T(14)，EG三、（10 分）某班有 25 名学生，其中 14 人会打篮球，12 人会打排球，6 人会打篮球和排球，5 人会打篮球和网球，还有 2 人会打这三种球。而 6 个会打网球的人都会打另外一种球，求不会打这三种球的人数。解 设 A、B、C 分别表示会打排球、网球和篮球的学生集合。则：|A|12，|B|6，|C|14，|AC|6，|BC|5，|ABC|2，|(AC)B|6。因为|(AC)B|(AB)(BC)|(AB)|(BC)|ABC|(AB)|526，所以|(AB)|3。于是|ABC|12614653220，25205。故，不|CBA会打这三种球的共 5 人。四、（10 分）设 A1、A2和 A3是全集 U 的子集，则形如Ai(Ai为 Ai或)的集合称为由31iiAA1、A2和 A3产生的小项。试证由 A1、A2和 A3所产生的所有非空小项的集合构成全集 U 的一个划分。证明 小项共 8 个，设有 r 个非空小项 s1、s2、sr(r8)。对任意的 aU，则 aAi或 a，两者必有一个成立，取 Ai为包含元素 a 的 Ai或，则iAiAaAi，即有 asi，于是 Usi。又显然有siU，所以 Usi。31iri 1ri 1ri 1ri 1任取两个非空小项 sp和 sq，若 spsq，则必存在某个 Ai和分别出现在 sp和 sq中，于是iAspsq。综上可知，s1，s2，sr是 U 的一个划分。五、（15 分）设 R 是 A 上的二元关系，则：R 是传递的R*RR。证明 (5)若 R 是传递的，则R*Rz(xRzzSy)xRccSy，由 R 是传递的得xRy，即有R，所以 R*RR。反之，若 R*RR，则对任意的 x、y、zA，如果 xRz 且 zRy，则R*R，于是有R，即有 xRy，所以 R 是传递的。第 17 页 共 18 页六、（15 分）若 G 为连通平面图，则 nmr2，其中，n、m、r 分别为 G 的结点数、边数和面数。证明 对 G 的边数 m 作归纳法。当 m0 时，由于 G 是连通图，所以 G 为平凡图，此时 n1，r1，结论自然成立。假设对边数小于 m 的连通平面图结论成立。下面考虑连通平面图 G 的边数为 m 的情况。设 e 是 G 的一条边，从 G 中删去 e 后得到的图记为 G，并设其结点数、边数和面数分别为n、m和 r。对 e 分为下列情况来讨论：若 e 为割边，则 G有两个连通分支 G1和 G2。Gi的结点数、边数和面数分别为 ni、mi和 ri。显然 n1n2nn，m1m2mm1，r1r2r1r1。由归纳假设有n1m1r12，n2m2r22，从而(n1n2)(m1m2)(r1r2)4，n(m1)(r1)4，即 nmr2。若 e 不为割边，则 nn，mm1，rr1，由归纳假设有 nmr2，从而n(m1)r12，即 nmr2。由数学归纳法知，结论成立。七、（10 分）设函数 g：AB，f：BC，则：(1)fg 是 A 到 C 的函数；(2)对任意的 xA，有 fg(x)f(g(x)。证明 (1)对任意的 xA，因为 g：AB 是函数，则存在 yB 使g。对于 yB，因 f：BC 是函数，则存在 zC 使f。根据复合关系的定义，由g 和f 得g*f，即fg。所以 DfgA。对任意的 xA，若存在 y1、y2C，使得、fgg*f，则存在 t1使得g 且f，存在 t2使得g 且f。因为 g：AB 是函数，则t1t2。又因 f：BC 是函数，则 y1y2。所以 A 中的每个元素对应 C 中惟一的元素。综上可知，fg 是 A 到 C 的函数。(2)对任意的 xA，由 g：AB 是函数，有g 且 g(x)B，又由 f：BC 是函数，得f，于是g*ffg。又因 fg 是 A 到 C 的函数，则可写为 fg(x)f(g(x)。八、（15 分）设是的子群，定义 R|a、bG 且 a1*bH，则 R是 G 中的一个等价关系，且aRaH。证明 对于任意 aG，必有 a1G 使得 a1*aeH，所以R。若R，则 a1*bH。因为 H 是 G 的子群，故(a1*b)1b1*aH。所以第 18 页 共 18 页R。若R，R，则 a1*bH，b1*cH。因为 H 是 G 的子群，所以(a1*b)*(b1*c)a1*cH，故R。综上可得，R 是 G 中的一个等价关系。对于任意的 baR，有R，a1*bH，则存在 hH 使得 a1*bh，ba*h，于是 baH，aRaH。对任意的 baH，存在 hH 使得 ba*h，a1*bhH，R，故 aHaR。所以，aRaH。