离散数学习题答案及解析[耿素云屈婉玲].doc

离散数学习题答案习题二及答案：〔P385、求下列公式的主析取范式,并求成真赋值：〔2解：原式,此即公式的主析取范式,所以成真赋值为011,1116、求下列公式的主合取范式,并求成假赋值：〔2解：原式,此即公式的主合取范式,所以成假赋值为1007、求下列公式的主析取范式,再用主析取范式求主合取范式：〔1解：原式,此即主析取范式主析取范式中没出现的极小项为,,,所以主合取范式中含有三个极大项,,,故原式的主合取范式9、用真值表法求下面公式的主析取范式：〔1解：公式的真值表如下：00010000011011010110101111111000101101010111001011110101由真值表可以看出成真赋值的情况有7种,此7种成真赋值所对应的极小项的析取即为主析取范式,故主析取范式习题三及答案：〔P52-5411、填充下面推理证明中没有写出的推理规则前提：结论：s证明：① p 前提引入②前提引入③ q ①②析取三段论④前提引入⑤ r ③④析取三段论⑥前提引入⑦ s ⑤⑥假言推理15、在自然推理系统P中用附加前提法证明下面推理：〔2前提：结论：证明：用附加前提证明法。

① p 附加前提引入②①附加③前提引入④②③假言推理⑤s④化简⑥⑤附加⑦前提引入⑧ u ⑥⑦假言推理故推理正确16、在自然推理系统P中用归谬法证明下面推理：〔1前提：,,结论：证明：用归谬法① p 结论的否定引入② 前提引入③ ①②假言推理④ 前提引入⑤ ③④析取三段论⑥ 前提引入⑦ r ⑥化简⑧ ⑤⑦合取由于,所以推理正确17、在自然推理系统P中构造下面推理的证明：只要A曾到过受害者房间并且11点以前没离开,A就是谋杀嫌犯A曾到过受害者房间如果A在11点以前离开,看门人会看见他看门人没有看见他所以,A是谋杀嫌犯解：设p：A到过受害者房间,q：A在11点以前离开,r：A是谋杀嫌犯,s：看门人看见过A则前提：,,, 结论：证明：① 前提引入② 前提引入③ ①②拒取式④ 前提引入⑤ ③④合取引入⑥ 前提引入⑦ ⑤⑥假言推理习题五及答案：〔P80-8115、在自然推理系统中,构造下面推理的证明：〔3前提：, 结论：证明：① 前提引入② ①置换③ ②UI规则④ 前提引入⑤ ④UI规则⑥ ③⑤析取三段论⑦ ⑥EG规则22、在自然推理系统中,构造下面推理的证明：〔2凡大学生都是勤奋的。

王晓山不勤奋所以王晓山不是大学生解：设F：x为大学生,G：想是勤奋的,c：王晓山则前提：, 结论：证明：① 前提引入② ①UI规则③ 前提引入④ ②③拒取式25、在自然推理系统中,构造下面推理的证明：每个科学工作者都是刻苦钻研的,每个刻苦钻研而又聪明的人在他的事业中都将获得成功王大海是科学工作者,并且是聪明的所以,王大海在他的事业中将获得成功〔个体域为人类集合解：设F：x是科学工作者,G：x是刻苦钻研的,H：x是聪明的,I：x在他的事业中获得成功,c：王大海则前提：,, 结论：证明：①前提引入②①化简③①化简④前提引入⑤④UI规则⑥ ②⑤假言推理⑦ ③⑥合取引入⑧ 前提引入⑨ ⑧UI规则⑩ ⑦⑨假言推理习题七及答案：〔P132-13522、给定,A上的关系,试〔1画出R的关系图；〔2说明R的性质2解：1〔1● ●● ●34〔2R的关系图中每个顶点都没有自环,所以R是反自反的,不是自反的； R的关系图中任意两个顶点如果有边的都是单向边,故R是反对称的,不是对称的； R的关系图中没有发生顶点x到顶点y有边、顶点y到顶点z有边,但顶点x到顶点z没有边的情况,故R是传递的。

26 设,R为A上的关系,R的关系图如图7.13所示：〔1求的集合表达式；〔2求r, s, t的集合表达式解：〔1由R的关系图可得所以,,可得；〔2,46、分别画出下列各偏序集的哈斯图,并找出A的极大元、极小元、最大元和最小元〔1解：哈斯图如下：eabcdA的极大元为e、极小元为a；A的最大元为e、最小元为a48、设为偏序集,在集合上定义关系T如下：证明T为上的偏序关系证明：〔1自反性：〔2反对称性：〔3传递性：综合〔1〔2〔3知T满足自反性、反对称性和传递性,故T为上的偏序关系习题九及答案：〔P179-1808、〔1〔2解：〔1〔211、〔3；解：〔3由*运算的定义可知：,16、习题十一及答案：〔P218-2191、图11.11给出了6个偏序集的哈斯图判断其中哪些是格如果不是格,说明理由解：〔a、〔c、〔f是格；因为任意两个元素构成的集合都有最小上界和最大下界；〔b不是格,因为{d,e}的最大下界不存在；〔d不是格,因为{b,c}的最小上界不存在；〔e不是格,因为{a,b}的最大下界不存在2、下列各集合低于整除关系都构成偏序集,判断哪些偏序集是格〔1L={1,2,3,4,5}；〔2L={1,2,3,6,12}；解：画出哈斯图即可判断出：〔1不是格,〔2是格。

4、设L是格,求以下公式的对偶式：〔2解：对偶式为：,参见P208页定义11.29、针对图11.11中的每个格,如果格中的元素存在补元,则求出这些补元解：〔a图：a,d互为补元,其中a为全下界,d为全上界,b和c都没有补元；〔c图：a,f互为补元,其中a为全下界,f为全上界,c和d的补元都是b和e,b和e的补元都是c和d；〔f图：a,f互为补元,其中a为全下界,f为全上界,b和e互为补元,c和d都没有补元10、说明图11.11中每个格是否为分配格、有补格和布尔格,并说明理由解：〔a图：是一条链,所以是分配格,b和c都没有补元,所以不是有补格,所以不是布尔格；〔c图：a,f互为补元,c和d的补元都是b和e,b和e的补元都是c和d,所以任何元素皆有补元,是有补格；,所以对运算不满足分配律,所以不是分配格,所以不是布尔格；〔f图：经过分析知图〔f对应的格只有2个五元子格：L1={a,c,d,e,f}, L2={a,b,c,d,f}画出L1和L2的哈斯图可知L1和L2均不同构于钻石格和五角格,根据分配格的充分必要条件〔见P213页的定理11.5得图〔f对应的格是分配格；c和d都没有补元,所以不是有补格,所以不是布尔格。