资源描述：
《2010西南科技大学离散数学期末考试B卷答案.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、西南科技大学2010-2011-2学期《课程名称》本科期末考试试卷（B卷）参考答案及评分细则课程代码143990240命题单位计算机科学与技术学院：软件教研室一、（10分）求p→((p→q)∧┐(┐q∨┐p))的主析取范式和主合取范式（不能采用真值表技术）。解：p→((p→q)∧┐(┐q∨┐p))Û┐p∨((┐p∨q)∧(q∧p))Û┐p∨((┐p∧q∧p)∨(q∧q∧p))Û┐p∨(q∧p)Û(┐p∧(q∨┐q))∨(q∧p)Û(┐p∧q)∨(┐p∧┐q)∨(p∧q)Ûm1∨m0∨m3ÛS(0,1,3)（主析取范
2、式）（6分）所以主合取范式为p(2)ÛM2Û(┐p∨q)（主合取范式）（4分）评分说明：也可先求主合取范式，再求主析取范式。步骤酌情给分。二、（10分）将下述命题符号化并证明推理是正确的。前提：（a）如果今天是星期六，我们就要到西湖或大清谷去玩。（b）如果西湖游人太多，我们就不到西湖去玩。（c）今天是星期六。（d）西湖游人太多。结论：我们到大清谷去玩。令p：今天是星期六,q:我们到西湖去玩,r:我们到大清谷去玩,s:西湖游人多解：符号化（4分）前提：p→(q∨r),s→¬q,p,s2010-2011-2学期《离散数
3、学B》-B卷-参考答案第5页共5页结论：r证明：（6分）步骤断言根据（1）s→¬qP（2）sP（3）¬qT,（1）,（2）,假言推理（4）pP（5）p→(q∨r)P（6）q∨rT,（4）,（5）,假言推理（7）rT,（3）,（6）,析取三段论一、（12分）运用推理规则证明:（1）（6分）Ø┐A∨B,┐C→┐B,C→DÞA→D证明：步骤断言根据(1)AP,附加前提(2)┐A∨BP(3)BT,(1),(2),析取三段论(4)┐C→┐BP(5)B→CT,(4),逆反律(6)CT,(3),(5),假言推理(7)C→DP(8
4、)DT,(6),(7),假言推理(9)A→DCP,(1),(8)（2）（6分）∀x(P(x)→Q(x))，∃yP(y)Þ∃yQ(y)证明：步骤断言根据（1）∃yP(y)P（2）P(c)(1)，ES（3）∀x(P(x)→Q(x))P（4）P(c)→Q(c)（3），US（5）Q(c)T，(2),(4)，I（6）∃yQ(y)EG二、（10分）2010-2011-2学期《离散数学B》-B卷-参考答案第5页共5页所有的主持人都很有风度。李明是个学生并且是个节目主持人。因此有些学生很有风度。请用谓词逻辑中的推理理论证明上述推理
5、。令H(x):x是主持人，F(x):x有风度，S(x):x是学生，c:李明。（个体域：所有人的集合）解：符号化（4分）前提：∀x(H(x)→F(x)),S(c)∧H(c)结论:∃x(S(x)∧F(x))证明：（6分）步骤断言根据(1)∀x(H(x)→F(x))P(2)H(c)→F(x)(1),US(3)S(c)∧H(c)P(4)H(c)(3),I(5)F(c)(2),(4),I(6)S(c)(3),I(7)S(c)∧F(c)(5),(6),I(8)∃x(S(x)∧F(x))(7),EG一、（10分）设集合A={a,
6、b,c,d,e}，R是A上的关系R={,,,,,}(1)画出R的关系图（3分）(2)写出R的关系矩阵（3分）(3)求R的传递闭包的关系矩阵M(t(R))（4分）解：(1)(2)G(R)如下图所示(3)先求R的传递闭包t(R)，即t(R)=RÈR2ÈR3È…，得到2010-2011-2学期《离散数学B》-B卷-参考答案第5页共5页一、（10分）对集合A={1,2,3,4,6,12}，是偏序集，其中´是A上的整除关系。画出该偏序集的哈斯图，并指出A的
7、最大元、最小元、极大元、极小元。解：哈斯图如下图所示（6分）对于，12是最大元，也是唯一极大元。1是最小元，也是唯一的极小元。（4分）二、（10分）（1）因为奇度结点个数有多个，所以不是欧拉图。（4分）（2）若该图中存在哈密尔顿回路，则该回路组成的图中任何结点的度数均为2。因而结点1、2、3、4、5所关联的边均在回路中，于是在结点a、b、c、d、e处均应将不与1、2、3、4、5关联的边删除，而要删除与结点a、b、c、d、e关联的其他边，这样一来，图就不连通了，因而图中不存在哈密尔顿回路。所以不是哈密顿图。
8、（6分）三、(14分)用Dijkstra算法求下图所示带权图中v1到其余各顶点的最短路径。要求写出计算过程。2010-2011-2学期《离散数学B》-B卷-参考答案第5页共5页一、(14分)解：将权值按从小到大顺序排列：10,20,30,30,50,60,70(2分)，用Huffman算法求一棵最优树，见下图所示。(8分)权值W(T)=10*4+20*4+5
