离散数学试题及答案508.pdf

《离散数学试题及答案508.pdf》由会员分享，可在线阅读，更多相关《离散数学试题及答案508.pdf（17页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第 1 页 共 17 页 离散数学试题及答案 一、填空题 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)|=_2(n2)_.3.设集合 A=a,b,B=1,2,那么从 A 到 B 的所有映射是_A1=(a,1),(b,1),A2=(a,2),(b,2),A3=(a,1),(b,2),A4=(a,2),(b,1),_ _,其中双射的是_A3,A4_.4.命题公式 G(PQ)R，那么 G 的主析取范式是_PQR(m5)_.5.设 G 是完全二叉树，G 有 7 个点，其中 4 个

2、叶点，那么 G 的总度数为_12_，分枝点数为_3_.6 设 A、B 为两个集合,A=1,2,4,B=3,4,那么从 AB_4_;AB_1,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),R1=(2,1),(3,2),(4,3),那么 R1R2=_(1,3),(2,2),(3,1)_,R2R1=_(2,4

3、),(3,3),(4,2)_,R12=_(2,2),(3,3)_.10.设有限集 A,B，|A|=m,|B|=n,那么|(AB)|=_2(m*n)_.11 设 A,B,R 是三个集合，其中 R 是实数集，A=x|-1x1,xR,B=x|0 x 2,xR,那么A-B=_x|-1 x 0,x R_,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.假设供选择答案中的

4、数值表示一个简单图中各个顶点的度，能画出图的是(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 )。1 2 3 4 5 6 第 3 页 共 17 页 (A)GH (B)HG (C)GH (D)以上都不是.9 设 A,B 为集合，当(D )时 ABB.(A)AB (B)A

5、B (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,c 12 命题xG(x)取真值 1 的充分必要条件是(A ).(A)对任意 x，G(x)都取真值 1.(B)有一个 x0，使 G(x0)取真值 1.(C)有某些 x，使 G(x0)取真值 1.(D)以上答案都不对.13.设 G 是连通平面图，有 5 个顶点，6 个面

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 的相邻矩阵为0110110101110110010111110，那么 G 的顶点数与边数分别为(D ).(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)的哈斯图；124836129 第 4 页 共 17 页(2)写出 A 的子集 B=3,6,9,12的上界，

7、下界，最小上界，最大下界；B 无上界，也无最小上界。下界 1,3;最大下界是 3.(3)写出 A 的最大元，最小元，极大元，极小元。A 无最大元，最小元是 1，极大元 8,12,90+;极小元是 1.2.设集合 A1,2,3,4，A 上的关系 R(x,y)|x,yA 且 x y,求 (1)画出 R 的关系图；1 2 3 4 (2)写出 R 的关系矩阵.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)

8、(x)+3x/4+3,(4)(x)(x)/42x/4=x/2,(5)()+32x/4+3x/2+3.4.设 I 是如下一个解释：D=2,3,第 5 页 共 17 页 a b f(2)f(3)P(2,2)P(2,3)P(3,2)P(3,3)3 2 3 2 0 0 1 1 试求(1)P(a,f(a)P(b,f(b);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).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

9、,4,6,8,12，R 为 A 上整除关系。(1)画出半序集(A,R)的哈斯图；2416812(2)写出 A 的最大元，最小元，极大元，极小元；第 6 页 共 17 页 无最大元，最小元 1，极大元 8,12;极小元是 1.(3)写出 A 的子集 B=4,6,8,12的上界，下界，最小上界，最大下界.B 无上界，无最小上界。下界 1,2;最大下界 2.6.设命题公式 G=(PQ)(Q(PR),求 G 的主析取范式。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

10、)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)；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)画出 r(R),s(R),t(

11、R)的关系图.bacdr(R)bacds(R)bacdt(R)第 7 页 共 17 页 11.通过求主析取范式判断以下命题公式是否等价：(1)G=(PQ)(PQR)(2)H=(P(QR)(Q(PR)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.设 R 和 S 是集合 Aa,b,c,d上的关系，其中 R(a,a),(a,c),(b,c),(c,d),S(a,b

12、),(b,c),(b,d),(d,d).(1)试写出 R 和 S 的关系矩阵；0000100001000101RM 1000000011000010SM (2)计算 RS,RS,R1,S1R1.第 8 页 共 17 页 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。证明：PQ,RS,PR蕴涵 QS(1)PR P(2)RP Q(1)(3)PQ P(4)RQ Q(2)(3)(5)QR

13、 Q(4)(6)RS P(7)QS Q(5)(6)(8)QS Q(7)2.设 A,B 为任意集合，证明：(A-B)-C=A-(BC).证明：(A-B)-C=(AB)C =A(BC)=A(BC)=A-(BC)第 9 页 共 17 页 3.(此题 10 分)利用形式演绎法证明：AB,CB,CD蕴涵 AD。证明：AB,CB,CD蕴涵 AD(1)A D(附加)(2)AB P(3)B Q(1)(2)(4)CB P(5)BC Q(4)(6)C Q(3)(5)(7)CD P(8)D Q(6)(7)(9)AD D(1)(8)所以 AB,CB,CD蕴涵 AD.4.(此题 10 分)A,B 为两个任意集合，求证：

14、A(AB)=(AB)B.证明：A(AB)=A(AB)A(AB)(AA)(AB)(AB)(AB)AB 而(AB)B 第 10 页 共 17 页=(AB)B=(AB)(BB)=(AB)=AB 所以：A(AB)=(AB)B.离散数学试题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 必须

15、同时成立。因此(ACD)(BC)(CD)(A(C D)(CD)(BC)(CD)(A(C D)(CD)(BC)(BD)C(CD)(ABC)(ABD)(AC)(ACD)第 11 页 共 17 页(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 分在谓词逻辑中构造下面推理的证明：某学术会议的每个成员都是专家并且是工人，有些成员是青年人，所以，有些成员是青年专家。解：论域：所有人的集合。S

16、(x)：x是专家；W(x)：x是工人；Y(x)：x是青年人；那么推理化形式为：x(S(x)W(x)，xY(x)x(S(x)Y(x)下面给出证明：(1)xY(x)P(2)Y(c)T(1)，ES(3)x(S(x)W(x)P(4)S(c)W(c)T(3)，US(5)S(c)T(4)，I(6)S(c)Y(c)T(2)(5)，I(7)x(S(x)Y(x)T(6)，EG 三、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(x

17、BxA)第 12 页 共 17 页(BA)。四、15 分设 A1，2，3，4，5，R 是 A 上的二元关系，且 R，求 r(R)、s(R)和 t(R)。解 r(R)RIA，s(R)RR1，R2，R3，R4，R2 t(R)1iRi，。五、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

18、)z(zRxyRz)yR2x，所以 R2对称。假设nR对称，那么 x1nRyz(xnRzzRy)z(znRxyRz)y1nRx，所以1nR对称。因此，对任意正整数 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，那么

19、f(x)y1，f(x)y2。因为 f：AB是函数，那么 y1y2。所以 f1是单射。综上可得，f1：BA 是双射。第 13 页 共 17 页 七、10 分设是一个半群，如果 S 是有限集，那么必存在 aS，使得 a*aa。证明 因为是一个半群，对任意的 bS，由*的封闭性可知，b2b*bS，b3b2*bS，bnS，。因为 S 是有限集，所以必存在 ji，使得ibjb。令 pji，那么jbpb*jb。所以对 qi，有qbpb*qb。因为 p1，所以总可找到 k1，使得 kpi。对于kpbS，有kpbpb*kpbpb*(pb*kpb)kpb*kpb。令 akpb，那么aS 且 a*aa。八、20

20、分 1假设 G 是连通的平面图，且 G 的每个面的次数至少为 l(l3)，那么 G 的边数 m 与结点数 n 有如下关系：m2ll(n2)。证明 设 G 有 r 个面，那么 2mriifd1)(lr。由欧拉公式得，nmr2。于是，m2ll(n2)。2设平面图 G是自对偶图，那么|E|2(|V|1)。证明 设 G*是连通平面图 G的对偶图，那么 G*G，于是|F|V*|V|，将其代入欧拉公式|V|E|F|2 得，|E|2(|V|1)。第 14 页 共 17 页 离散数学试题B 卷及答案 一、10 分证明(PQ)(PR)(QS)SR 证明 因为 SRRS，所以，即要证(PQ)(PR)(QS)RS。

21、(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)第 15 页 共 17 页 B(x)。(1)x(P(

22、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(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 人

23、会打排球，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，|CBA25205。故，不会打这三种球的共 5 人。四、10 分设 A1、A2和 A3是全集 U 的子集，那么形如31iAi(Ai为 Ai或iA)的集合称为由

24、A1、A2和 A3产生的小项。试证由 A1、A2和 A3所产生的所有非空小项的集合构成全集 U 的一个划分。证明 小项共 8 个，设有 r 个非空小项 s1、s2、sr(r8)。对任意的 aU，那么 aAi或 aiA，两者必有一个成立，取 Ai为包含元素 a 的 Ai或iA，那么 a31iAi，即有 ari 1si，于是 Uri 1si。又显然有ri 1siU，所以 Uri 1si。任取两个非空小项 sp和 sq，假设 spsq，那么必存在某个 Ai和iA分别出现在 sp和 sq中，于是第 16 页 共 17 页 spsq。综上可知，s1，s2，sr是 U 的一个划分。五、15 分设 R 是

25、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 是传递的。六、15 分假设 G 为连通平面图，那么 nmr2，其中，n、m、r 分别为 G 的结点数、边数和面数。证明 对 G 的边数 m 作归纳法。当 m0 时，由于 G 是连通图，所以 G 为平凡图，此时 n1，r1，结论自然成立。假设对边数小于 m 的连通平面图结论成立。下面考虑连通平面图 G 的边数

26、为 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：

27、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 中惟一的元素。第 17 页 共 17 页 综上可知，fg 是 A 到 C

28、的函数。(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。所以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。