西南科技大学2010-2011-2学期
《课程名称》本科期末考试试卷（B 卷）
一、 （10分）求p →((p→q) ∧┐(┐q ∨┐p)) 的主析取范式和主合取范式（不能采用真值表技术）。
二、 （10分）将下述命题符号化并证明推理是正确的。
前提：（a ）如果今天是星期六，我们就要到西湖或大清谷去玩。
（b ）如果西湖游人太多，我们就不到西湖去玩。 （c ）今天是星期六。 （d ）西湖游人太多。
结论：我们到大清谷去玩。
令p ：今天是星期六,q: 我们到西湖去玩,r:我们到大清谷去玩,s:西湖游人多
三、 （12分）运用推理规则证明:
（1） （6分）(P∧Q)→R，┌R∨S ，┌S ⇒┌P∨┌Q
（2） （6分）∀x(P(x)→Q(x))，∃yP(y) ⇒ ∃yQ(y)
四、 （10分）所有的主持人都很有风度。李明是个学生并且是个节目主持人。因此有些学生很有风度。
请用谓词逻辑中的推理理论证明上述推理。令H(x):x是主持人，F(x):x有风度，S(x):x 是学生，c: 李明。（个体域：所有人的集合）
五、 （10分）设集合A={a,b,c,d,e}，R 是A 上的关系R={,,, ,, }
(1) 画出R 的关系图
(2) 写出R 的关系矩阵
(3) 求R 的传递闭包的关系矩阵M(t(R))
六、 （10分）对集合A={1,2,3,4,6,12}，是偏序集，其中 是A 上的整除关系。画出该偏序集的哈
斯图，并指出A 的最大元、最小元、极大元、极小元。
七、 （10分）判断下图是否是欧拉图和哈密顿图，并说明理由。
八、 (14分) 用Dijkstra 算法求下图所示带权图中v1到其余各顶点的最短路径。要求写出计算过程。
九、 （14分）画出带权 30,20,10,30,70,60,50 的最优二元树 T，并计算它的权值 W(T)。
西南科技大学2010-2011-2学期
《课程名称》本科期末考试试卷（B 卷）
一、 （10分）求p →((p→q) ∧┐(┐q ∨┐p)) 的主析取范式和主合取范式（不能采用真值表技术）。
二、 （10分）将下述命题符号化并证明推理是正确的。
前提：（a ）如果今天是星期六，我们就要到西湖或大清谷去玩。
（b ）如果西湖游人太多，我们就不到西湖去玩。 （c ）今天是星期六。 （d ）西湖游人太多。
结论：我们到大清谷去玩。
令p ：今天是星期六,q: 我们到西湖去玩,r:我们到大清谷去玩,s:西湖游人多
三、 （12分）运用推理规则证明:
（1） （6分）(P∧Q)→R，┌R∨S ，┌S ⇒┌P∨┌Q
（2） （6分）∀x(P(x)→Q(x))，∃yP(y) ⇒ ∃yQ(y)
四、 （10分）所有的主持人都很有风度。李明是个学生并且是个节目主持人。因此有些学生很有风度。
请用谓词逻辑中的推理理论证明上述推理。令H(x):x是主持人，F(x):x有风度，S(x):x 是学生，c: 李明。（个体域：所有人的集合）
五、 （10分）设集合A={a,b,c,d,e}，R 是A 上的关系R={,,, ,, }
(1) 画出R 的关系图
(2) 写出R 的关系矩阵
(3) 求R 的传递闭包的关系矩阵M(t(R))
六、 （10分）对集合A={1,2,3,4,6,12}，是偏序集，其中 是A 上的整除关系。画出该偏序集的哈
斯图，并指出A 的最大元、最小元、极大元、极小元。
七、 （10分）判断下图是否是欧拉图和哈密顿图，并说明理由。
八、 (14分) 用Dijkstra 算法求下图所示带权图中v1到其余各顶点的最短路径。要求写出计算过程。
九、 （14分）画出带权 30,20,10,30,70,60,50 的最优二元树 T，并计算它的权值 W(T)。