离散数学习题答案（耿素云屈婉玲）离散数学习题答案习题二及答案：（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∨∨?∧解：公式的真值表如下：由真值表可以看出成真赋值的情况有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⑤⑥假言推理习题五及答案：（P80-81）15、在自然推理系统Nξ中，构造下面推理的证明：（3）前提：(()())xFxGx?∨，()xGx??结论：()xFx?证明：①()xGx??前提引入②()xGx??①置换③()Gc?②UI规则④(()())xFxGx?∨前提引入⑤()()FcGc∨④UI规则⑥()Fc③⑤析取三段论⑦()xFx?⑥EG规则22、在自然推理系统Nξ中，构造下面推理的证明：（2）凡大学生都是勤奋的。晓山不勤奋。所以晓山不是大学生。解：设F(x)：x为大学生，G(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⑦⑨假言推理习题七及答案：（P132-）22、给定{}1,2,3,4A=，A上的关系{}1,3,1,4,2,3,2,4,3,4R=，试（1）画出R的关系图；（2）说明R的性质。解：（1）●●（2）R...
