离散数学习题问题详解解析汇报.doc

离散数学习题答案习题一与答案：P14-1514、将如下命题符号化：5辛与末是兄弟解：设p：辛与末是兄弟，如此命题符号化的结果是p6王强与威都学过法语解：设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。习题二与答案：P385、求如下公式的主析取式，并求成真赋值：2解：原式，此即公式的主析取式，所以成真赋值为011，111。*6、求如下公式的主合取式，并求成假赋值：2解：原式，此即公式的主合取式，所以成假赋值为100。7、求如下公式的主析取式，再用主析取式求主合取式：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。如此前提：， 结论：证明： 前提引入 前提引入拒取式 前提引入合取引入 前提引入假言推理习题四与答案：P65-675、在一阶逻辑中将如下命题符号化：2有的火车比有的汽车快。解：设F(x)：x是火车，G(y)：y是汽车，H(x,y)：x比y快；如此命题符号化的结果是：3不存在比所有火车都快的汽车。解：方法一：设F(x)：x是汽车，G(y)：y是火车，H(x,y)：x比y快；如此命题符号化的结果是：或方法二：设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既不是永真式也不是矛盾式。此题答案不唯一，只要证明公式既不是永真式也不是矛盾式的每个解释合理即可。习题五与答案：P79-815、给定解释I如下：(a) 个体域D=3,4(b) (c) 试求如下公式在I下的真值：(1) 解：方法一：先消去存在量词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规如此假言推理习题六与答案P99-10028、化简下述集合公式：3解：30、设A,B,C代表任意集合，试判断下面命题的真假。如果为真，给出证明；如果为假，给出反例。6解：该命题为假，如果，如此，否如此，故为假。举反例如下：如此。8解：该命题为假，举反例如下：如果B，C都是A的子集，如此一定成立，但不一定成立，例如：，,，如此，但。33、证明集合恒等式：1证明：习题七与答案：P132-26 设，R为A上的关系，R的关系图如图7.13所示：1求的集合表达式；2求r(R), s(R), t(R)的集合表达式。解：1由R的关系图可得所以，可得；2，41、设A=1，2，3，4，R为上的二元关系，1证明R为等价关系；2求R导出的划分。1只需证明R具有自反性、对称性和传递性即可，证明过程如下：a任取，有，所以R具有自反性；b任取，假如，如此有，所以R具有对称性；c任取，假如且，如此有且，所以R具有传递性，综合abc可知：R为集合上的等价关系；2先求出集合的结果：再分别求集合各元素的等价类，结果如下：。等价关系R导出的划分就是集合A关于R的商集，而集合A关于R的商集是由R的所有等价类作为元素构成的集合，所以等价关系R导出的划分是：46、分别画出如下各偏序集的哈斯图，并找出A的极大元、极小元、最大元和最小元。1解：哈斯图如下：eabcdfA的极大元为e、f，极小元为a、f；A的最大元和最小元都不存在。*22、给定，A上的关系，试1画出R的关系图；2说明R的性质。2解：11342R的关系图中每个顶点都没有自环，所以R是反自反的，不是自反的； R的关系图中任意两个顶点如果有边的都是单向边，故R是反对称的，不是对称的； R的关系图中没有发生顶点x到顶点y有边、顶点y到顶点z有边，但顶点x到顶点z没有边的情况，故R是传递的。*48、设为偏序集，在集合上定义关系T如下：证明T为上的偏序关系。证明：1自反性：2反对称性：3传递性：综合123知T具有自反性、反对称性和传递性，故T为上的偏序关系。习题九与答案：P179-1808、12。解：1211、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.2。6、设L为格，且，证明。证明：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，所以任何元素皆有补元，是有补格；，所以对运算不满足分配律，所以不是分配格，所以不是布尔格；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都没有补元，所以不是有补格，所以不是布尔格。