离散数学试题及答案.pdf

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

1、 离散数学考试试题（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

2、)(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(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)

3、T(3)，US(5)S(c)T(4)，I(6)S(c)Y(c)T(2)(5)，I(7)xS(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(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，R4，R2 t(R)1iRi，。五、（10 分）R 是非空集合

4、 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对称，则x1nRyz(xnRzzRy)z(znRxyRz)y1nRx，所以1nR对称。因此，对任意正整数 n，nR对称。对任意的 x、yA，若 xt(R)y，则存在 m 使得 xRmy，于是有 yRmx，即有 yt(

5、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，b

6、nS，。因为 S 是有限集，所以必存在 ji，使得ibjb。令 pji，则jbpb*jb。所以对 qi，有qbpb*qb。因为 p1，所以总可找到 k1，使得 kpi。对于kpbS，有kpbpb*kpbpb*(pb*kpb)kpb*kpb。令 akpb，则aS 且 a*aa。八、（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*是

7、连通平面图 G的对偶图，则 G*G，于是|F|V*|V|，将其代入欧拉公式|V|E|F|2 得，|E|2(|V|1)。离散数学考试试题（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(

8、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(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(1

9、0)，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)|A

10、BC|(AB)|526，所以|(AB)|3。于是|ABC|12614653220，|CBA25205。故，不会打这三种球的共 5 人。四、（10 分）设 A1、A2和 A3是全集 U 的子集，则形如31iAi(Ai为 Ai或iA)的集合称为由 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

11、，所以 Uri 1si。任取两个非空小项 sp和 sq，若 spsq，则必存在某个 Ai和iA分别出现在 sp和 sq中，于是 spsq。综上可知，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 是传递的。六、（15 分）若 G 为连通平面图，则 nmr2，其中，n、m、r 分别为 G 的结点数、边数

12、和面数。证明 对 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

13、)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 且

14、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。所

15、以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。发到哪？给个邮箱啊一、填空 20%（每小题 2 分）1设 （N：自然数集，E+正偶数）则 。2A，B，C 表示三个集合，文图中阴影部分的集合表达式为 。3设 P，Q 的真值为 0，R，S 的真值为 1，则 的真值=。4公式 的主合取范式为 。5

16、若解释 I 的论域 D 仅包含一个元素，则 在 I 下真值为 。6设 A=1，2，3，4，A 上关系图为 则 R2=。7设 A=a，b，c，d，其上偏序关系 R 的哈斯图为 则 R=。8图 的补图为 。9设 A=a，b，c，d，A 上二元运算如下：*a b c d a b c d a b c d b c d a c d a b d a b c 那么代数系统的幺元是 ，有逆元的元素为 ，它们的逆元分别为 。10下图所示的偏序集中，是格的为 。二、选择 20%（每小题 2 分）1、下列是真命题的有（）A ；B；C ；D 。2、下列集合中相等的有（）A4，3；B，3，4；C4，3，3；D 3，4。3

17、、设 A=1，2，3，则 A 上的二元关系有（）个。A 23；B 32 ；C ；D 。4、设 R，S 是集合 A 上的关系，则下列说法正确的是（）A若 R，S 是自反的，则 是自反的；B若 R，S 是反自反的，则 是反自反的；C若 R，S 是对称的，则 是对称的；D若 R，S 是传递的，则 是传递的。5、设 A=1，2，3，4，P（A）（A 的幂集）上规定二元系如下 则 P（A）/R=（）AA；BP(A)；C1，1，2，1，2，3，1，2，3，4；D，2，2，3，2，3，4，A 6、设 A=，1，1，3，1，2，3则 A 上包含关系“”的哈斯图为（）7、下列函数是双射的为（）Af:I E,f(

18、x)=2x；Bf:N N N,f(n)=；Cf:R I,f(x)=x；Df:I N,f(x)=|x|。（注：I整数集，E偶数集，N自然数集，R实数集）8、图 中 从 v1 到 v3 长度为 3 的通路有（）条。A 0；B 1；C 2；D 3。9、下图中既不是 Eular 图，也不是 Hamilton 图的图是（）10、在一棵树中有 7 片树叶，3 个 3 度结点，其余都是 4 度结点则该树有（）个 4 度结点。A1；B2；C3；D4。三、证明 26%1、R 是集合 X 上的一个自反关系，求证：R 是对称和传递的，当且仅当 和在 R 中有在 R 中。（8 分）2、f 和 g 都是群到的同态映射，

19、证明是的一个子群。其中 C=(8 分)3、G=(|V|=v，|E|=e)是每一个面至少由 k（k 3）条边围成的连通平面图，则，由此证明彼得森图（Peterson）图是非平面图。（11 分）四、逻辑推演 16%用 CP 规则证明下题（每小题 8 分）1、2、五、计算 18%1、设集合 A=a，b，c，d上的关系 R=,用矩阵运算求出 R 的传递闭包 t(R)。（9 分）2、如下图所示的赋权图表示某七个城市 及预先算出它们之间的一些直接通信线路造价，试给出一个设计方案，使得各城市之间能够通信而且总造价最小。（9 分）试卷一答案：一、填空 20%（每小题 2 分）1、0，1，2，3，4，6；2、；

20、3、1；4、；5、1；6、,；7、,IA ；8、9、a；a,b,c,d；a,d,c,d；10、c;二、选择 20%（每小题 2 分）题目 1 2 3 4 5 6 7 8 9 10 答案 C D B、C C A D C A D B A 三、证明 26%1、证：“”若 由 R 对称性知，由 R 传递性得 “”若，有 任意 ，因 若 所以 R 是对称的。若，则 即 R 是传递的。2、证，有 ，又 是 的子群。3、证：设 G 有 r 个面，则，即 。而 故 即得 。（8 分）彼得森图为，这样 不成立，所以彼得森图非平面图。（3 分）二、逻辑推演 16%1、证明：P（附加前提）TI P TI TI TI P TI CP 2、证明 P（附加前提）US P US TI UG CP 三、计算 18%1、解：，t(R)=,2、解：用库斯克（Kruskal）算法求产生的最优树。算法略。结果如图：树权 C(T)=23+1+4+9+3+17=57 即为总造价。面给出证明:(1)Some x is Y(x)P (2)Y(c)(1)T(1)，ES (3)Some(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)(Every)S(x)Y(x)T(6),EG