2010西南科技大学离散数学期末考试B卷答案

2010-2011-2学期《离散数学B》-B卷-参考答案第1页共5页西南科技大学2010-2011-2学期《课程名称》本科期末考试试卷（B卷）参考答案及评分细则一、（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(0,1,3)（主析取范式）（6分）所以主合取范式为(2)M2(┐p∨q)（主合取范式）（4分）评分说明：也可先求主合取范式，再求主析取范式。步骤酌情给分。二、（10分）将下述命题符号化并证明推理是正确的。前提：（a）如果今天是星期六，我们就要到西湖或大清谷去玩。（b）如果西湖游人太多，我们就不到西湖去玩。（c）今天是星期六。（d）西湖游人太多。结论：我们到大清谷去玩。令p：今天是星期六,q:我们到西湖去玩,r:我们到大清谷去玩,s:西湖游人多解：符号化（4分）前提：p→(q∨r),s→¬q,p,s课程代码143990240命题单位计算机科学与技术学院：软件教研室2010-2011-2学期《离散数学B》-B卷-参考答案第2页共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)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卷-参考答案第3页共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,b,c,d,e}，R是A上的关系R={a,b,b,c,c,d,d,c,b,e,e,e}(1)画出R的关系图（3分）(2)写出R的关系矩阵（3分）(3)求R的传递闭包的关系矩阵M(t(R))（4分）解：(1)0100000101()000100010000001MR(2)G(R)如下图所示abcde(3)先求R的传递闭包t(R)，即t(R)=RR2R3…，得到2010-2011-2学期《离散数学B》-B卷-参考答案第4页共5页0111100111(())001100011000001MtR六、（10分）对集合A={1,2,3,4,6,12}，A,是偏序集，其中是A上的整除关系。画出该偏序集的哈斯图，并指出A的最大元、最小元、极大元、极小元。解：哈斯图如下图所示（6分）1246231对于A,，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关联的其他边，这样一来，图就不连通了，因而图中不存在哈密尔顿回路。所以不是哈密顿图。（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+50*3+30*3+30*3+60*2+70*2=710(4分)