《离散数学模拟题一套及答案.pdf》由会员分享，可在线阅读，更多相关《离散数学模拟题一套及答案.pdf（6页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1/61/6 离散数学考试（试题及答案）一、（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
2、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(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
3、(c)T(3)，US(5)S(c)T(4)，I(6)S(c)Y(c)T(2)(5)，I 2/62/6(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(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，。五、（1
4、0 分）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对称，则 x1nRyz(xnRzzRy)z(znRxyRz)y1nRx，所以1nR对称。因此，对任意正整数 n，nR对称。对任意的 x、yA，若 xt(R)y，则存在 m 使得 xRmy，于是有
5、 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*
6、bS，b3b2*bS，bnS，。因为 S 是有限集，所以必存在 ji，使得ibjb。令 pji，则jbpb*jb。所以对 qi，有qb3/63/6 pb*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 个面，则 2mlr。由欧拉公式得，nmr2。于是，m2ll(n2)。（2）设平面图 G是自对偶图，则|E|2(
7、|V|1)。证明 设 G*是连通平面图 G的对偶图，则 G*G，于是|F|V*|V|，将其代入欧拉公式|V|E|F|2 得，|E|2(|V|1)。4/64/6 离散数学考试试题（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 分）根据推理理论证明：每个考生或者勤奋或者聪明，所有勤奋的人都将有所作为，但并非所有考生都将有所
8、作为，所以，一定有些考生是聪明的。设 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(8)P(a)(A(a)B(a)T(7)，US(9)A(a)B(a)T(8)(5)，I(10)x(A(x
9、)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 5/65/6 三、（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。因为
10、|(AC)B|(AB)(BC)|(AB)|(BC)|ABC|(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
11、 1si，于是 Uri 1si。又显然有ri 1siU，所以 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 为连通平面图，则
12、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，n
13、2m2r22，从而(n1n2)(m1m2)(r1r2)4，n(m1)(r1)4，即 nmr2。若 e 不为割边，则 nn，mm1，rr1，由归纳假设有 nmr2，从而 n(m1)r12，即 nmr2。由数学归纳法知，结论成立。七、（10 分）设函数 g：AB，f：BC，则：6/66/6(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，
14、使得、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。所以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。