离散数学习题答案

离散数学习题答案习题一及答案：（P14-15）14、将下列命题符号化：（5）李辛与李末是兄弟解：设p：李辛与李末是兄弟，则命题符号化的结果是p（6）王强与刘威都学过法语解：设p：王强学过法语；q：刘威学过法语；则命题符号化的结果是pq（9）只有天下大雨，他才乘班车上班解：设p：天下大雨；q：他乘班车上班；则命题符号化的结果是qp（11）下雪路滑，他迟到了解：设p：下雪；q：路滑；r：他迟到了；则命题符号化的结果是()pqr15、设p：2+3=5.q：大熊猫产在中国.r：太阳从西方升起.求下列复合命题的真值：（4）()(())pqrpqr解：p=1，q=1，r=0，()(110)1pqr，(())((11)0)(00)1pqr()(())111pqrpqr19、用真值表判断下列公式的类型：（2）()ppq解：列出公式的真值表，如下所示：pqpq()pp()ppq001111011010100101110001由真值表可以看出公式有3个成真赋值，故公式是非重言式的可满足式。20、求下列公式的成真赋值：（4）()pqq解：因为该公式是一个蕴含式，所以首先分析它的成假赋值，成假赋值的条件是：()10pqq00pq所以公式的成真赋值有：01，10，11。习题二及答案：（P38）5、求下列公式的主析取范式，并求成真赋值：（2）()()pqqr解：原式()pqqrqr()ppqr()()pqrpqr37mm，此即公式的主析取范式，所以成真赋值为011，111。*6、求下列公式的主合取范式，并求成假赋值：（2）()()pqpr解：原式()()pprpqr()pqr4M，此即公式的主合取范式，所以成假赋值为100。7、求下列公式的主析取范式，再用主析取范式求主合取范式：（1）()pqr解：原式()(()())pqrrppqqr()()()()()()pqrpqrpqrpqrpqrpqr()()()()()pqrpqrpqrpqrpqr13567mmmmm，此即主析取范式。主析取范式中没出现的极小项为0m，2m，4m，所以主合取范式中含有三个极大项0M，2M，4M，故原式的主合取范式024MMM。9、用真值表法求下面公式的主析取范式：（1）()()pqpr解：公式的真值表如下：pqrppqpr()()pqpr00010000011011010110101111111000101101010111001011110101由真值表可以看出成真赋值的情况有7种，此7种成真赋值所对应的极小项的析取即为主析取范式，故主析取范式1234567mmmmmmm习题三及答案：（P52-54）11、填充下面推理证明中没有写出的推理规则。前提：,,,pqqrrsp结论：s证明：①p前提引入②pq前提引入③q①②析取三段论④qr前提引入⑤r③④析取三段论⑥rs前提引入⑦s⑤⑥假言推理15、在自然推理系统P中用附加前提法证明下面推理：（2）前提：()(),()pqrsstu结论：pu证明：用附加前提证明法。①p附加前提引入②pq①附加③()()pqrs前提引入④rs②③假言推理⑤s④化简⑥st⑤附加⑦()stu前提引入⑧u⑥⑦假言推理故推理正确。16、在自然推理系统P中用归谬法证明下面推理：（1）前提：pq，rq，rs结论：p证明：用归谬法①p结论的否定引入②pq前提引入③q①②假言推理④rq前提引入⑤r③④析取三段论⑥rs前提引入⑦r⑥化简⑧rr⑤⑦合取由于0rr，所以推理正确。17、在自然推理系统P中构造下面推理的证明：只要A曾到过受害者房间并且11点以前没离开，A就是谋杀嫌犯。A曾到过受害者房间。如果A在11点以前离开，看门人会看见他。看门人没有看见他。所以，A是谋杀嫌犯。解：设p：A到过受害者房间，q：A在11点以前离开，r：A是谋杀嫌犯，s：看门人看见过A。则前提：()pqr，p，qs，s结论：r证明：①qs前提引入②s前提引入③q①②拒取式④p前提引入⑤pq③④合取引入⑥()pqr前提引入⑦r⑤⑥假言推理习题四及答案：（P65-67）5、在一阶逻辑中将下列命题符号化：（2）有的火车比有的汽车快。解：设F(x)：x是火车，G(y)：y是汽车，H(x,y)：x比y快；则命题符号化的结果是：(()()(,))xyFxGyHxy（3）不存在比所有火车都快的汽车。解：方法一：设F(x)：x是汽车，G(y)：y是火车，H(x,y)：x比y快；则命题符号化的结果是：(()(()(,)))xFxyGyHxy或(()(()(,)))xFxyGyHxy方法二：设F(x)：x是火车，G(y)：y是汽车，H(x,y)：x比y快；则命题符号化的结果是：(()(()(,)))xGxyFyHxy或(()(()(,)))xyGxFyHxy9、给定解释I如下：(a)个体域为实数集合R。(b)特定元素0a。(c)函数(,),,fxyxyxyR。(d)谓词(,):,(,):,,FxyxyGxyxyxyR。给出以下公式在I下的解释，并指出它们的真值：（2）(((,),)(,))xyFfxyaGxy解：解释是：(0)xyxyxy，含义是：对于任意的实数x，y，若x-y=0则xy。该公式在I解释下的真值为假。14、证明下面公式既不是永真式也不是矛盾式：（1）(()(()(,)))xFxyGyHxy解：取解释I如下：个体域为全总个体域，()Fx：x是兔子，()Gy：y是乌龟，(,)Hxy：x比y跑得快，则该公式在解释I下真值是1；取解释'I如下：(,)Hxy：x比y跑得慢，其它同上，则该公式在解释'I下真值是0；故公式（1）既不是永真式也不是矛盾式。此题答案不唯一，只要证明公式既不是永真式也不是矛盾式的每个解释合理即可。习题五及答案：（P79-81）5、给定解释I如下：(a)个体域D={3,4}(b)():(3)4,(4)3fxff(c)(,):(3,3)(4,4)0,(3,4)(4,3)1FxyFFFF试求下列公式在I下的真值：(1)(,)xyFxy解：方法一：先消去存在量词(,)((,3)(,4))xyFxyxFxFx((3,3)(3,4))((4,3)(4,4))FFFF(01)(10)115、在自然推理系统N中，构造下面推理的证明：（3）前提：(()())xFxGx，()xGx结论：()xFx证明：①()xGx前提引入②()xGx①置换③()Gc②UI规则④(()())xFxGx前提引入⑤()()FcGc④UI规则⑥()Fc③⑤析取三段论⑦()xFx⑥EG规则*22、在自然推理系统N中，构造下面推理的证明：（2）凡大学生都是勤奋的。王晓山不勤奋。所以王晓山不是大学生。解：设F(x)：x为大学生，G(x)：x是勤奋的，c：王晓山则前提：(()())xFxGx，()Gc结论：()Fc证明：①(()())xFxGx前提引入②()()FcGc①UI规则③()Gc前提引入④()Fc②③拒取式25、在自然推理系统N中，构造下面推理的证明：每个科学工作者都是刻苦钻研的，每个刻苦钻研而又聪明的人在他的事业中都将获得成功。王大海是科学工作者，并且是聪明的。所以，王大海在他的事业中将获得成功。（个体域为人类集合）解：设F(x)：x是科学工作者，G(x)：x是刻苦钻研的，H(x)：x是聪明的，I(x)：x在他的事业中获得成功，c：王大海则前提：(()())xFxGx，(()()())xGxHxIx，()()FcHc结论：()Ic证明：①()()FcHc前提引入②()Fc①化简③()Hc①化简④(()())xFxGx前提引入⑤()()FcGc④UI规则⑥()Gc②⑤假言推理⑦()()GcHc③⑥合取引入⑧(()()())xGxHxIx前提引入⑨()()()GcHcIc⑧UI规则⑩()Ic⑦⑨假言推理习题六及答案（P99-100）28、化简下述集合公式：（3）(())(())(())(())ABCABCABCABC解：(())(())(())(())ABCABCABCABC()()ABABA30、设A,B,C代表任意集合，试判断下面命题的真假。如果为真，给出证明；如果为假，给出反例。（6）()ABAB解：该命题为假，()ABABA，如果BA，则BAB，否则BAB，故BAB为假。举反例如下：{1,2},{1,3},AB则(){3}ABAB。（8）ABACBC解：该命题为假，举反例如下：如果B，C都是A的子集，则ABAC一定成立，但BC不一定成立，例如：{1,2}A，{1}B,{2}C，则ABACA，但BC。33、证明集合恒等式：（1）()ABABA证明：()ABA()()ABAA()ABABBA习题七及答案：（P132-135）26设1,2,3,4,5,6A，R为A上的关系，R的关系图如图7.13所示：（1）求23,RR的集合表达式；（2）求r(R),s(R),t(R)的集合表达式。解：（1）由R的关系图可得1,5,2,5,3,1,3,3,4,5R所以23,1,3,3,3,5RRR，323,1,3,3,3,5RRR，可得3,1,3,3,3,5,n=2nR当；（2）Ar(R)=RI1,5,2,5,3,1,3,3,4,5,1,1,2,2,4,4,5,5,6,6，1()R1,5,5,1,2,5,5,2,3,1,1,3,3,3,4,5,5,4sRR232()RR...R1,5,2,5,3,1,3,3,3,5,4,5tRRR41、设A={1，2，3，4}，R为AA上的二元关系，,,,abcdAA，,,abRcdabcd（1）证明R为等价关系；（2）求R导出的划分。（1）只需证明R具有自反性、对称性和传递性即可，证明过程如下：（a）任取,abAA，有abab，,,abRab，所以R具有自反性；（b）任取,,,abcdAA，若,,abRcd，则有abcd，cdab，,,cdRab，所以R具有对称性；（c）任取,,,,,abcdefAA，若,,abRcd且,,cdRef，则有abcd且cdef，abef，,,abRef，所以R具有传递性，综合（a）（b）（c）可知：R为集合AA上的等价关系；（2）先求出集合AA的结果：{1,1,1,2,1,3,1,4,2,1,2,2,2,3,2,4,3,1,3,2,3,3,3,4,4,1,4,2,4,3,4,4}AA再分别求集合AA各元素的等价类，结果如下：[1,1]{1,1},R[1,2][2,1]{1,2,2,1},RR1243[1,3][2,2][3,1]{1,3,2,2,3,1},RRR[1,4][2,3][3,2][4,1