离散数学习题答案(同名3671)

离散数学习题答案习题一及答案：（P14-15）14、将下列命题符号化：（5）李辛与李末是兄弟解：设p：李辛与李末是兄弟，则命题符号化的结果是p（6）王强与刘威都学过法语解：设p：王强学过法语；q：刘威学过法语；则命题符号化的结果是（9）只有天下大雨，他才乘班车上班解：设p：天下大雨；q：他乘班车上班；则命题符号化的结果是（11）下雪路滑，他迟到了解：设p：下雪；q：路滑；r：他迟到了；则命题符号化的结果是15、设p：2+3=5.q：大熊猫产在中国.r：太阳从西方升起.求下列复合命题的真值：（4）解：p=1，q=1，r=0，，19、用真值表判断下列公式的类型：（2）解：列出公式的真值表，如下所示：001111011010100101110001由真值表可以看出公式有3个成真赋值，故公式是非重言式的可满足式。20、求下列公式的成真赋值：（4）解：因为该公式是一个蕴含式，所以首先分析它的成假赋值，成假赋值的条件是：所以公式的成真赋值有：01，10，11。习题二及答案：（P38）5、求下列公式的主析取范式，并求成真赋值：（2）解：原式，此即公式的主析取范式，所以成真赋值为011，111。6、求下列公式的主合取范式，并求成假赋值：（2）解：原式，此即公式的主合取范式，所以成假赋值为100。7、求下列公式的主析取范式，再用主析取范式求主合取范式：（1）解：原式，此即主析取范式。主析取范式中没出现的极小项为，，，所以主合取范式中含有三个极大项，，，故原式的主合取范式。9、用真值表法求下面公式的主析取范式：⑤③④合取引入⑥前提引入⑦⑤⑥假言推理习题四及答案：（P65-67）5、在一阶逻辑中将下列命题符号化：（2）有的火车比有的汽车快。解：设F(x)：x是火车，G(y)：y是汽车，H(x,y)：x比y快；则命题符号化的结果是：（3）不存在比所有火车都快得汽车。解：设F(x)：x是汽车，G(y)：y是火车，H(x,y)：x比y快；则命题符号化的结果是：或9、给定解释I如下：(a)个体域为实数集合R。(b)特定元素。(c)函数。(d)谓词。给出以下公式在I下的解释，并指出它们的真值：（2）解：解释是：，含义是：对于任意的实数x，y，若x-y=0则x<y。该公式在I解释下的真值为假。14、证明下面公式既不是永真式也不是矛盾式：（1）解：取解释如下：个体域为全总个体域，：x是兔子，：y是乌龟，：x比y跑得快，则该公式在解释I下真值是1；取解释如下：：x比y跑得慢，其它同上，则该公式在解释下真值是0；故公式（1）既不是永真式也不是矛盾式。此题答案不唯一，只要证明公式既不是永真式也不是矛盾式的每个解释合理即可。习题五及答案：（P80-81）15、在自然推理系统中，构造下面推理的证明：（3）前提：，结论：证明：①前提引入②①置换③②UI规则④前提引入⑤④UI规则⑥③⑤析取三段论⑦⑥EG规则22、在自然推理系统中，构造下面推理的证明：（2）凡大学生都是勤奋的。王晓山不勤奋。所以王晓山不是大学生。解：设F(x)：x为大学生，G(x)：x是勤奋的，c：王晓山则前提：，结论：证明：①前提引入②①UI规则③前提引入④②③拒取式25、在自然推理系统中，构造下面推理的证明：每个科学工作者都是刻苦钻研的，每个刻苦钻研而又聪明的人在他的事业中都将获得成功。王大海是科学工作者，并且是聪明的。所以，王大海在他的事业中将获得成功。（个体域为人类集合）解：设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）21●●●●3434（2）R的关系图中每个顶点都没有自环，所以R是反自反的，不是自反的；R的关系图中任意两个顶点如果有边的都是单向边，故R是反对称的，不是对称的；R的关系图中没有发生顶点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）解：哈斯图如下：eeabcdfA的极大元为e、f，极小元为a、f；A的最大元和最小元都不存在。48、设为偏序集，在集合上定义关系T如下：证明T为上的偏序关系。证明：（1）自反性：（2）反对称性：（3）传递性：综合（1）（2）（3）知T具有自反性、反对称性和传递性，故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）L={1，2，3，4，5}；（2）L={1，2，3，6，12}；解：画出哈斯图即可判断出：（1）不是格，（2）是格。4、设L是格，求以下公式的对偶式：（2）解：对偶式为：，参见P208页定义11.2。9、针对图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，所以任何元素皆有补元，是有补格；，所以对运算不满足分配律，所以不是分配格，