7、求下列公式的主析取范式，再用主析取范式求主合取范式。 （1）(p?q)?r 解
答
：
(p?q)?r(已经是析取范式)?(p?q?(?r?r))?((?p?p)?(?q?q)?r)?(p?q??r)?(p?q?r)?(?p??q?r)?(?p?q?r)?(p??q?r)?(p?q?r)?(?p??q?r)?(?p?q?r)?(p??q?r)?(p?q??r)?(p?q?r)?m1?m3?m5?m6?m7?M0?M2?M4
8、求下列公式的主合取范式，再用主合取范式求主析取范式。 （2）(p?q)?r 解答：
(p?q)?r?((p?q)?(q?p))?r?((?p?q)?(?q?p))?r??((?p?q)?(?q?p))?r?((p??q)?(q??p))?r?(p?q?r)?(p??p?r)?(?q?q?r)?(?q??p?r)?(p?q?r)?(?q??p?r)?(p?q?r)?(?p??q?r)?M0?M6?m1?m2?m3?m4?m5?m713、已知公式A含3个命题变项p,q,r，并且它的成假赋值为010，011，110，111，求A的主析取范式和主合取范式。 解答：成真赋值为000,001,100,101 所以主析取范式为m0?m1?m4?m5 而主合取范式为M2?M3?M6?M7 15、用主析取范式判断下列公式是否等值。 （2）?(p?q)和?(p?q) 解答：
?(p?q)??p??q?(?p?(?q?q))?((?p?p)??q)
?(?p??q)?(?p?q)?(?p??q)?(p??q)?(?p??q)?(?p?q)?(p??q)?m0?m1?m2?(p?q)??p??q ?m0所以两式并不等值。
18、将下列公式化成与之等值且仅含有{?,?}中联结词的公式 （3）(p?(q?r))?p 解答：
(p?(q?r))?p?(?p?(q?r))?p??p?p?(q?r)?129、在某班班委成员的选举中，已知王小红、李强、丁金生3位同学被选进了班委会。该班的的甲、乙、丙3位同学预言：
甲说：王小红为班长，李强为生活委员； 乙说：丁金生为班长，王小红为生活委员。 丙说：李强为班长，王小红为学习委员。
班委会分工名单公布后发现，甲乙丙三人都恰好猜对了一半。问王小红、李强、丁金生各任何职？（用等值演算求解） 解答：命题符号化：
p:王小红为班长；q:李强为生活委员；r:丁金生为班长；s:王小红为生活委员；
u:李强为班长；v:王小红为学习委员。
设A1:p??q；A2:?p?q；B1:r??s；B2:?r?s；C1:u??v；C2:?u?v； 由题意可知：
p?r?0;p?s?0;p?u?0;p?v?0;q?s?0;q?u?0;r?u?0;s?v?0所以A1?B1?0;A1?B2?0;A1?C1?0;A1?C2?0;A2?B2?0;A2?C1?0;
B1?C1?0,B2?C2?0
所以
(A1?A2)?(B1?B2)?(C1?C2)?(A1?B1?C1)?(A1?B1?C2)?(A1?B2?C1)?(A1?B2?C2)?(A2?B1?C1)?(A2?B1?C2)?(A2?B2?C1)?(A2?B2?C2) ?0?0?0?0?0?(A2?B1?C2)?0?0?A2?B1?C2所以选举结果为：李强为生活委员；丁金生为班长；王小红为学习委员。
30、某公司要从赵、钱、孙、李、周5名新毕业的大学生中选派一些人出国学习。选派必须满足条件：
（1）若赵去，钱也去； （2）李、周两人中必有一人去； （3）钱、孙两人中去且仅去一人； （4）孙、李两人同去或同不去； （5）若周去，则赵、钱也同去。
用等值演算法分析该公司该如何选派他们出国。 解答：命题符号化：
p:赵去；q:钱去；r:孙去；s:李去；t:周去。
所满足的条件即为
（1）若赵去，钱也去：p?q； （2）李、周两人中必有一人去：s?t；
（3）钱、孙两人中去且仅去一人：(q??r)?(?q?r)； （4）孙、李两人同去或同不去：(r?s)?(?r??s)； （5）若周去，则赵、钱也同去：t?(p?q)。 将所有条件进行合取，然后求其主析取范式
(p?q)?(s?t)?((q??r)?(?q?r))?((r?s)?(?r??s))?(t?(p?q))
?(?p??q?r?s??t)?(p?q??r??s?t)（过程省略）
所以最终方案有两套：
（1）赵钱周不去，孙李去；（2）赵钱周去，孙李不去。
P50:习题三
9、用3种方法（真值表、等值演算、主析取范式）证明下面推理是正确的。
若a是奇数，则a不能被2整除。若a是偶数，则a能被2整除。因此，如果a是偶数，则a不是奇数。
解答：命题符号化：p:a为奇数；q:a为偶数；r:a能被2整除 推理的形式结构：
前提：p??r；q?r；q 结论：?q
推理的形式结构的另外一种描述：
(p??r)?(q?r)?q??p
证明：（1）真值表法： p q r ?p ?r 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 1 1 1 1 0 0 0 0 1 0 1 0 1 0 1 0 p??r 1 1 1 1 1 0 1 0 q?r (p??r)?(q?r)?q 1 1 0 1 1 1 0 1 0 0 0 1 0 0 0 0 (p??r)?(q?r)?q??p 1 1 1 1 1 1 1 1 所以(p??r)?(q?r)?q??p为永真式；推理(p??r)?(q?r)?q??p是正确的。
（2）等值演算：
(p??r)?(q?r)?q??p?(?p??r)?(?q?r)?q??p??((?p??r)?(?q?r)?q)??p?((p?r)?(q??r)??q)??p?(p?r)?(q??r)??q??p?((p?r)??p)?((q??r)??q)?((p??p)?(r??p))?((q??q)?(?r??q))?(1?(r??p))?(1?(?r??q))?(r??p)?(?r??q)?(r??p)?(?r??q)?r??r??p??q?1（3）主析取范式
(p??r)?(q?r)?q??p?(?p??r)?(?q?r)?q??p??((?p??r)?(?q?r)?q)??p?((p?r)?(q??r)??q)??p?(p?r)?(q??r)??q??p?(p?(?q?q)?r)?((?p?p)?q??r)?((?p?p)??q?(?r?r))?(?p?(?q?q)?(?r?r))........?m0?m1?m2?m3?m4?m5?m6?m7
12、填充下面推理证明中没有写出的推理规则。 前提：p?(q?r)，q?(r?s) 结论：(p?q)?s 证明： ①p?q ②p ③q
附加前提引入 ①化简 ①化简 前提引入 ②④假言推理 ③⑤假言推理 前提引入 ③⑦假言推理 ⑥⑧假言推理
④p?(q?r) ⑤q?r ⑥r
⑦q?(r?s) ⑧r?s ⑨s
14、在自然推理系统P中构造下面推理的证明： （2）前提：p?q,?(q?r),r
结论：?p 证明： ①?(q?r) ②?q??r ③r
前提引入 ①置换 前提引入 ②③析取三段论 前提引入 ④⑤拒取式
④?q ⑤p?q ⑥?p
（4）前提：q?p,q?s,s?t,t?r
结论：p?q 证明： ①t?r ②t ③r
前提引入 ①化简 ①化简 前提引入
④s?t
⑤(s?t)?(t?s) ④置换 ⑥t?s ⑦q?s
⑤化简 前提引入
⑧(q?s)?(s?q) ⑦置换
离散数学及其应用数理逻辑部分课后习题答案
