离散数学期末考试试题(配答案).doc

: .
广东技术师范学院
模拟试题
科 目：离散数学
考试形式：闭卷 考试时间: 120 分钟
系别、班级： 姓名： 学号：
一．填空题（每小题2分，共10分）
1. 谓词公式的前束范式是__ ∃x∃y¬P(x)∨Q(y) __________。
2. 设全集则A∩B =__{2}__，_{4,5}____，
__ {1,3,4,5} _____
3. 设，则__ {{c},{a,c},{b,c},{a,b,c}} __________，_____Φ_______。
4. 在代数系统（N，+）中，其单位元是0，仅有 _1___ 有逆元。
5．如果连通平面图G有个顶点，条边，则G有___e+2-n____个面。
二．选择题（每小题2分，共10分）
1. 与命题公式等价的公式是（ ）
（A） （B） （C） （D）
2. 设集合,A上的二元关系不具备关系( )性质
（A） (A)传递性 (B)反对称性 (C)对称性 (D)自反性
3. 在图中,结点总度数与边数的关系是( )
(A) (B) (C)(D)
4. 设D是有n个结点的有向完全图,则图D的边数为( )
(A) (B) (C) (D)
5. 无向图G是欧拉图,当且仅当( )
(A) G的所有结点的度数都是偶数 (B)G的所有结点的度数都是奇数
(C)G连通且所有结点的度数都是偶数 (D) G连通且G的所有结点度数都是奇数。
三．计算题（共43分）
1. 求命题公式的主合取范式与主析取范式。（6分）
解：主合取方式：p∧q∨r⇔(p∨q∨r)∧(p∨¬q∨r)∧(¬p∨q∨r)= ∏
主析取范式：p∧q∨r⇔(p∧q∧r) ∨(p∧q∧¬r) ∨(¬p∧q∧r) ∨(¬p∧¬q∧r) ∨(p∧¬q∧r)= ∑
2. 设集合上的二元关系R的关系矩阵为,求的关系矩阵，并画出R，的关系图。（10分）
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. 试判断是否为格？说明理由。（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，≤）是格。
（注：什么是格？）