离散数学期末考试试题（配答案）模拟题2

模拟题2

广东技术师范学院

模拟试题

科 目：离散数学

考试形式：闭卷 考试时间: 120 分钟

系别、班级： 姓名： 学号：

一、填空20%（每空2分）：

1．若对命题P赋值1，Q赋值0，则命题P?Q（?表示双条件）的真值为 0 。

2．命题“如果你不看电影，那么我也不看电影”（P：你看电影，Q：我看电影）的符号化为 ?P→?Q 3．公式?(P?Q)?(P??(Q??S))的对偶公式为___?（P∧Q）∨（P∧?（Q∨?S））____。

4．图 的对偶图为

5.若关系R是等价关系，则R满足______自反性，对称性，传递性_____________________________。 6．代数系统?A,??是群，则它满足____结合律，有幺元 ，每个元素都有递元______。 7．若连通平面图G??V,E?共有r个面，其中V?v,E?e，则它满足的Euler公式为_____v-e+r=2__。

8. n个结点的无向完全图Kn的边数为 n（n-1）/2 ，欧拉图的充要条件是 顶点都是偶顶点且是连通的 。

9. 设I为整数集合，R={| x≡y（mod3）}，则[1]=___ {??，-2,1,4，??}____ 。

10．代数系统?A,?,??是环，若对运算“· ”还满足a，b∈R，使得a?b≠0，可换，含幺元 则?A,?,??是整环。 二、选择10%（每小题2分）

1

1．集合A?{xx?2n,n?N}对（ ）运算封闭。

A、加法； B、减法； C、乘法； D、x?y 。

2．设I为整数集合，m是任意正整数，Zm是由模m的同余类组成的同余类集合，在Zm上定义

运算[i]?[j]?[(i?j)modm]，则代数系统?Zm,?m?最确切的性质是 ）。 A、封闭的代数系统； B、半群； C、幺元； D、群。

3．设?N,??是偏序格，其中N是自然数集合，“≤”是普通的数间“小于等于” 关系，则

?a,b?N有a?b?（ ）。

A、a ； B、b ； C、max(a，b) ； D、min(a，b)。

4．连通非平凡的无向图G有一条欧拉回路当且仅当图G ( )。

A、只有一个奇度结点； B、只有两个奇度结点； C、只有三个奇度结点； D、没有奇度结点。 5．设无向图G??V,E?是连通的且V?n,E?m 若（ ）则G是树。

A、m=n+1 ； B、n=m+1 ； C、m?3n?6 ； D、n?3m?6 。 三、12%符号化语句：“有些病人相信所有的医生，但是病人都不相信骗子，所以医生都不是骗子”。并推证其结论。

解: 设A(x):x是病人，B(x):x是医生，C(x):x是骗子，D(x,y):x相信y 前提：?(x)(A(X)∧(?y)(B(y)→D(x,y))) (?x)(?y)(A(x)∧((y)→?D(x,y)) 结论：(?x)(B(x)→?C(x))

制表如下： 编号 公式 依据 （1） (?x)(A(x)∧(?y)(B(y)→D(x,y))) 前提 （2） A(a)∧(?y)(B(y)→D(a,y)) (1),Es （3） A(a),(?y)(B(y)→D(a,y)) (2) （4） (?x)(?y)(A(x)∧C(y)→?D(x,y)) 前提 （5） (?y)(A(a)∧C(y)→?D(a,y)) (4),Us （6） A(a)→(?y)(C(y)?D(a,y)) (5) （7） (?y)((C(y)→?D(a,y)) (3)(6) （8） B(d)→D(a,d) (3),Us （9） C(e)→?D(a,e) (7),Us （10） B(d)→?C(e) (8)(9) （11） (?x)(B(x)→?C(x)) (10),UG

2

四、8%：设A?{x1,x2,x3,x4,x5}，偏序集?A,R?的Hass图为

求 ① A中最小元与最大元； ② {x3,x4,x5}的上界和上确界，下界和下确界。 解：（1）A中最小元：没有；

最大元： x1

（2）上界x1 x3

上确界 x3 下界无 下确界无

（注：离散数学及应用（温武）127页概念，自己去研究）

五、8%：求集合An??x0?x?

??1??(n?1,2,3,?)的并与交。 n?

（注：写这个还真麻烦，丑，呃??）

六、15% 已知某树有2个2度结点、3个3度结点、4个4度结点，问有几个叶子点（无其它度数点）

解：设共有k个叶子点，总边数为x，则 2+3+4+k=x+1

2×2＋3×3＋4×4＋k=2x

解得：k=13，x=21

3

七、8% 若图G不连通，则G的补图G是连通的。

证明：G不连通，则G的连通分支有G1，G2，Gm,(m≥2) 在补图非G中找两个顶点，u，v有两种情况：

①u，v落在G的不同连通分支中，u∈Gi，v∈Gj，i≠j； (u,v)是补图非G的一条边，故u，v连通。

②u，v都在Gi中，则找另一个连通分支Gj，在Gj找任意一个顶点w，(u,w),(w,v)是G的边，则u，v在补图非G边连通。

八、10% 求图中的一棵最小生成树。

解：

九、9% 若集合Ｘ＝｛（１，２），（３，４），（５，６），??｝

4

2

R?{??x1,y1?,?x2,y2??|x1?y2?x2?y1}

1、证明R是X上的等价关系。 2、求出X关于R的商集。

证明：

1.①自反性?（x1，y1）∈x，由于x1+y1=y1+x1，所以＜（x1，y1），（x1，y1）＞∈R ②对称性?＜（x1，y1），（x2，y2）＞∈R,要证明＜（x2，y2），（x1，y1）＞∈R 因为x1+y2=x2+y1及①自反性，可得:x2+y1=x1+y2 所以具有对称性。

③传递性 ?＜（x1，y1），（x2，y2）＞∈R , ?＜（x2，y2），(x3,y3) ＞∈R

x1+y2=y1+x2

x2+y3=y2+x3 因为①②可得：x1+y3=y1+x3

2. X关于R的商集：x/R={[(1,2)]}

5

本文来源：https://www.bwwdw.com/article/8g2v.html