西南科技大学2010-2011-2学期
《离散数学A》本科期末考试试卷（B卷）
参考答案及评分细则
课程代码 1 4 3 9 9 0 2 3 0 命题单位 计算机科学与技术学院：软件工程系 一、判断题（本大题共10个小题，每小题2分，共20分）将每小题的判断结果写在答题纸上，正确的写“正确”，错误的写“错误”。 1. “3+3=6”,不是命题。（错误）
2. 命题公式（P??Q?Q）是偶然式。（正确）
3. 若B中不含有x，则?x（A(x)?B）??xA(x)?B。（错误） 4. 如果论述域是{a，b}，则?xR(x) ?R(a)?R(b)。（错误） 5. 若集合A的基数|A|=5，则A的幂集的基数|?(A)|=32。（正确） 6. 设A是一个集合，则A?A=?。（错误）
7. 设R是非空集合A上的二元关系，则R的传递闭包t(R)=R?R0。（错误） 8. 所有欧拉图的顶点次（度）数一定是偶数。（正确）
9. 无向图G是二部图当且仅当G中所有回路的长度均为偶数。（正确） 10. K5、K3,3都是非平面图。（正确）
二、简单计算题（本大题共10个小题，每小题3分，共30分）将每小题的计算结果写在答题纸上。 1. 设P：我有时间；Q：我去镇上，用逻辑符合写出命题“只有我有时间，我才去镇上。”。 答案：Q?P
2. 对命题公式：P?（Q??R）??P?Q化为仅含?和?的等价表达式。 答案：?（P?Q）
3. 设S(x)：x是火车，L(x)：x是卡车，F(x,y)：x比y快。在谓词逻辑中符号化命题“所有火车都比所有卡车快”。
答案：?x(S(x)→?y(L(y) ∧F（x , y）) 4. 求谓词公式?xP(x)??xQ(x)的前束范式。 答案：?x?y(P(x)?Q(x))
2010-2011-2学期
《离散数学B》-B卷-参考答案 第 1 页 共 5 页
5. 在一个班级50个学生中，有26人在第一次考试中得到A，21人在第二次考试中得到A，假如17人两次考试都没有得到A，问有多少学生在两次考试中都得到A？ 答案：14人。
6. 假设A是n个元素的有限集合，有多少个元素在A上的最小等价关系中？ 答案：n个。
7. 二元关系的关系图如下图所示，则R具有哪些特性（性质）？
答案：R是反自反的、对称的。
8. 一颗树有两个顶点的度数为2，一个顶点的度数为3，三个顶点的度数为4，问它有几个度数为1的顶点？ 答案：9个。
9. 无向连通图G如下所示，则该图的最小生成树的权是多少？
答案：15
10. 对下图所标记二叉树，写出按中序周游的结果。
答案：dbheiafcg
2010-2011-2学期
《离散数学B》-B卷-参考答案 第 2 页 共 5 页
三、应用题（本大题共4个小题，每小题8分，共32分）将每小题的求解或证明过程写在答题纸上。 1. 求命题公式：(?P?Q)?(?Q?P)的主析取范式和主合取范式。
答案：用等值演算法、真值表法均可，根据解题过程及答案正确与否酌情给分。 主吸取范式为：(P?Q)?(?P??Q)?(?P?Q)=?(0,2,3) 主合取范式为：P??Q
2. 设A={a,b,c,d}，?1、?2、?3是A上的划分，?1={{a,b},{c,d}}，?2={{a},{b},{c},{d}}，?3={{a,b,c,d}}，试求：
（1）?1所诱导出的等价关系的序偶。
答案：{
（2）写出偏序集合<{?1,?2,?3}，细分>的“细分”关系元素，并画出该偏序集合的哈斯图。 答案：“细分”关系={,,,,,} 哈斯图为：
（3）求集合{?1,?2,?3}的最大元、最小元、极大元、极小元。 答案：最大元为?3，最小元为?2，极大元为?3，极小元为?2。 3. 有向图G如下图所示。
(1) 用邻接矩阵求G中v1到v4长度为3和4的路径各有几条？
2010-2011-2学期
《离散数学B》-B卷-参考答案 第 3 页 共 5 页
?0?0A???0??0答案：因为G的邻接矩阵为：
?0?0???0??0101?011??101??100?
12??03?0422?(4)?A???0312???01??01，
23?13??23??22?
A(2)所以，
111??02?01201?(3)?A???02111???011??02 ，
故，G中v1到v4长度为3的路径为2条，长度为4的路径为3条。 (2) 求G的可达性矩阵。
?0?02A???0??0答案：因为：111??0?0101?3?A???0111???011??0 ，111??0?0111?4?A???0111???101??0，111?111??111??111?。
111?111??111??111?
?0?0234P?A?A?A?A???0??0G的可达矩阵为：
4. 证明：在有6个顶点，12条边的连通平面简单图中，每个区域用3条边围成。
证明：n=6，m=12，由欧拉公式得面数k=8。若有区域是用＞3条边围成的，则有2m＞3k，即24＞24，从而导致矛盾。这说明每个区域用3条边围成。
四、应用题（本大题共2个小题，每小题9分，共18分）将每小题的求解或证明过程写在答题纸上。 (1) 将下列推理符号化并给出形式证明：
每个学术会的成员都是工人并且是专家，有些成员是青年人，所以有的成员是青年专家。 证明：首先将命题符号化，个体域为全总个体域。
F(x)：x是学术会成员。 G(x)：x是专家。 H(x)：x是工人。 R(x)：x是青年人。。则该推理的形式结构为：
?x(F(x)?H(x)?G(x))，?x(F(x)?R(x))??x(F(x)?R(x)?G(x))。 ① ?x(F(x)?R(x)) P
② F(c)?R(c) T， ①，ES ③ ?x(F(x)?H(x)?G(x)) P ④ F(x)?H(x)?G(x) T，③，US
2010-2011-2学期
《离散数学B》-B卷-参考答案
第 4 页 共 5 页
相关推荐：
loading