离散数学期末考试试题(配答案)[1]

模拟试题

科 目：离散数学

考试形式：闭卷 考试时间: 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∩B =__{2}__，A_{4,5}____，

AB__ {1,3,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，仅有 _1___ 有逆元。 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

iivVvV4. 设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的所有结点的度数都是奇数

第 1 页 共 5 页

(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12. 设集合Aa,b,c,d上的二元关系R的关系矩阵为MR00r(R),s(R),t(R)的关系矩阵，并画出R，r(R),s(R),t(R)的关系图。（10分）

0000010001,求01

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

第 2 页 共 5 页

解：∵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，≤）是格。

（注：什么是格？

第 3 页 共 5 页

）

四．证明题（共37分）

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

证明： 编号 （1） （2） （3） （4） （5） （6） （7） （8）

公式 （¬B∨C）∧¬C ¬B∨C，¬C ¬B A→B ¬A ¬（¬A∧D） A∨¬D ¬D 依据 前提 （1） （2） （3） （3）（4） 前提 （6） （5）（6）

2. 设R是实数集，f:RRR,f(a,b)ab，g:RRR,g(a,b)ab。求证：f和g都是满射，但不是单射。（10分）

证明：要证f是满射，即∀y∈R,都存在（x1，x2）∈R×R，使f（x1，x2）=y，而f（x1，x2）=x1+x2，可取x1=0，x2=y，即证得；

再证g是满射，即∀y∈R，,都存在（x1，x2）∈R×R，使g（x1，x2）=y，而g（x1，x2）=x1x2，可取x1=1，x2=y，即证得；

最后证f不是单射，f（x1，x2）=f（x2，x1）取x1≠x2，即证得，同理：g（x1，x2）=g（x2，x1），取x1≠x2，即证得。

3. 无向图G有9个结点，每个结点的度数不是5就是6，求证：G中至少有5个6度结点或6个5度结点。（10分）

第 4 页 共 5 页

证明：设G中至多有4个6度结点且5个5度结点， ∴d（Vi）=49不是偶数， 故它不是一个图，矛盾。 （下面只供参考，个人答案）

4. 设平面上有100个点，期中任意两点间的距离至少是1，则最多有300对点距离恰好为1。（7分）

证明：设任意两点间的读书和恰好为1，则满足： ∑d（Vi）=2e d（Vi）≤6 ∴6×100≥2e e≤300

故最多只有300条边，即300对点距离恰好为1.

第 5 页 共 5 页