离散数学习题答案(耿素云屈婉玲)离散数学习题答案习题二及答案:(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...