最新离散数学期末考试试题(配答案)

广东技术师范学院

模拟试题

科 目：离散数学

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

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

一．填空题（每小题2分，共10分）

1. 谓词公式 xP(x) xQ(x)的前束范式是__ x y¬P(x)∨Q(y) __________。 2. 设全集E 1,2,3,4,5 ,A 1,2,3 ,B 2,5 ,则A∩ _{4,5}____，

3. 设A a,b,c ,B a,b ，则 (A) (B) __ {{c},{a,c},{b,c},{a,b,c}} __________，

(B) (A) _____Φ_______。

4. 在代数系统（N，+）中，其单位元是0，仅有 5．如果连通平面图G有n个顶点，e条边，则G有___e+2-n____个面。

二．选择题（每小题2分，共10分）

1. 与命题公式P (Q R)等价的公式是（ ）

（A）(P Q) R （B）(P Q) R （C）P (Q R) （D）P (Q R) 2. 设集合A a,b,c ,A上的二元关系R a,a , b,b 不具备关系( )性质

（A） (A)传递性 (B)反对称性 (C)对称性 (D)自反性

3. 在图G V,E 中,结点总度数与边数的关系是( ) (A)deg(vi) 2E (B) deg(vi) E(C)

deg(v) 2E(D) deg(v) E

i

i

v V

v V

4. 设D是有n个结点的有向完全图,则图D的边数为( ) (A)n(n 1) (B)n(n 1) (C)n(n 1)/2 (D)n(n 1)/2

5. 无向图G是欧拉图,当且仅当( )

(A) G的所有结点的度数都是偶数 (B)G的所有结点的度数都是奇数

(C)G连通且所有结点的度数都是偶数 (D) G连通且G的所有结点度数都是奇数。

三．计算题（共43分）

1. 求命题公式p q r的主合取范式与主析取范式。（6分）

解：主合取方式：p∧q∨r (p∨q∨r)∧(p∨¬q∨r)∧(¬p∨q∨r)= ∏0.2.4

主析取范式：p∧q∨r (p∧q∧r) ∨(p∧q∧¬r) ∨(¬p∧q∧r) ∨(¬p∧¬q∧r) ∨(p∧¬q

∧r)= ∑1.3.5.6.7

1 1

2. 设集合A a,b,c,d 上的二元关系R的关系矩阵为MR

0 0

r(R),s(R),t(R)的关系矩阵，并画出R，r(R),s(R),t(R)的关系图。（10分）

0000100

0 1 ,求0 1

3 无向图G有12条边，G中有6个3度结点，其余结点的度数均小于3，问G中至少有多少个

结点？（10分）

解：∵G（V,E），| E |=V，d（Vi）<3,

设至少有x个节点，由握手定理得：

2×12=∑d（Vi）<6×3+(x-6)×3

2<(x-6) =＞ x>8

故G中至少有9个节点。

4 求下面两个图的最小生成树。（12分）

5. 试判断(z, )是否为格？说明理由。（5分）

解：（Z,≤）是格，理由如下：

对于任意a∈Z，a≤a成立，满足自反性；

对于任意a∈Z，b∈Z，若a≤b且b≤a，则a=b，满足反对称性； 对于任意a，b，c∈Z，若a≤b，b≤c，则a≤c，满足传递性；

而对于任意a，b∈Z，a≤b，b为最小上界，a为最大下界，故（Z，≤）是格。

（注：什么是格？

）

四．证明题（共37分）

1. 用推理规则证明A B,( B C) C, ( A D) D。（10分）

证明： 编号

公式

依据

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