离散数学习题答案(耿素云屈婉玲)

《离散数学习题答案(耿素云屈婉玲)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、离散数学习题答案习题二及答案：（P38）5、求下列公式的主析取范式，并求成真赋值：（2）解：原式，此即公式的主析取范式，所以成真赋值为011，111。6、求下列公式的主合取范式，并求成假赋值：（2）解：原式，此即公式的主合取范式，所以成假赋值为100。7、求下列公式的主析取范式，再用主析取范式求主合取范式：（1）解：原式，此即主析取范式。主析取范式中没出现的极小项为，，，所以主合取范式中含有三个极大项，，，故原式的主合取范式。9、用真值表法求下面公式的主析取范式：（1）解：公式的真值表如下：000100000110110101101011111110001011010

2、10111001011110101由真值表可以看出成真赋值的情况有7种，此7种成真赋值所对应的极小项的析取即为主析取范式，故主析取范式习题三及答案：（P52-54）11、填充下面推理证明中没有写出的推理规则。前提：结论：s证明：①p前提引入②前提引入③q①②析取三段论④前提引入⑤r③④析取三段论⑥前提引入⑦s⑤⑥假言推理15、在自然推理系统P中用附加前提法证明下面推理：（2）前提：结论：证明：用附加前提证明法。①p附加前提引入②①附加③前提引入④②③假言推理⑤s④化简⑥⑤附加⑦前提引入⑧u⑥⑦假言推理故推理正确。16、在自然推理系统P中用归谬法证明下面推理：（1）前提

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

4、5、在自然推理系统中，构造下面推理的证明：（3）前提：，结论：证明：①前提引入②①置换③②UI规则④前提引入⑤④UI规则⑥③⑤析取三段论⑦⑥EG规则22、在自然推理系统中，构造下面推理的证明：（2）凡大学生都是勤奋的。王晓山不勤奋。所以王晓山不是大学生。解：设F(x)：x为大学生，G(x)：想是勤奋的，c：王晓山则前提：，结论：证明：①前提引入②①UI规则③前提引入④②③拒取式25、在自然推理系统中，构造下面推理的证明：每个科学工作者都是刻苦钻研的，每个刻苦钻研而又聪明的人在他的事业中都将获得成功。王大海是科学工作者，并且是聪明的。所以，王大海在他的事业中将获得成功。

5、（个体域为人类集合）解：设F(x)：x是科学工作者，G(x)：x是刻苦钻研的，H(x)：x是聪明的，I(x)：x在他的事业中获得成功，c：王大海则前提：，，结论：证明：①前提引入②①化简③①化简④前提引入⑤④UI规则⑥②⑤假言推理⑦③⑥合取引入⑧前提引入⑨⑧UI规则⑩⑦⑨假言推理习题七及答案：（P132-135）22、给定，A上的关系，试（1）画出R的关系图；（2）说明R的性质。2解：1（1）●●●●34（2）R的关系图中每个顶点都没有自环，所以R是反自反的，不是自反的；R的关系图中任意两个顶点如果有边的都是单向边，故R是反对称的，不是对称的；R的关系图中没有发生顶点

6、x到顶点y有边、顶点y到顶点z有边，但顶点x到顶点z没有边的情况，故R是传递的。26设，R为A上的关系，R的关系图如图7.13所示：（1）求的集合表达式；（2）求r(R),s(R),t(R)的集合表达式。解：（1）由R的关系图可得所以，，可得；（2），46、分别画出下列各偏序集的哈斯图，并找出A的极大元、极小元、最大元和最小元。（1）解：哈斯图如下：eabcdA的极大元为e、极小元为a；A的最大元为e、最小元为a。48、设为偏序集，在集合上定义关系T如下：证明T为上的偏序关系。证明：（1）自反性：（2）反对称性：（3）传递性：综合（1）（2）（3）知T满足自反性、反对

7、称性和传递性，故T为上的偏序关系。习题九及答案：（P179-180）8、（1）（2）。解：（1）（2）11、（3）；解：（3）由*运算的定义可知：，16、习题十一及答案：（P218-219）1、图11.11给出了6个偏序集的哈斯图。判断其中哪些是格。如果不是格，说明理由解：（a）、（c）、（f）是格；因为任意两个元素构成的集合都有最小上界和最大下界；（b）不是格，因为{d,e}的最大下界不存在；（d）不是格，因为{b,c}的最小上界不存在；（e）不是格，因为{a,b}的最大下界不存在。2、下列各集合低于整除关系都构成偏序集，判断哪些偏序集是格。（1）