发布时间 : 星期三 文章离散数学及其应用数理逻辑部分课后习题答案更新完毕开始阅读
所以
所以选举结果为：李强为生活委员；丁金生为班长；王小红为学习委员。
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)。 将所有条件进行合取，然后求其主析取范式 （过程省略）
所以最终方案有两套：
（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
推理的形式结构的另外一种描述： 证明：（1）真值表法：
0 0 0 0 0 1 1 1 1 0 1 1 1 1 0 0 1 1 0 0 1 1 1 1 1 1 0 0 1 1 0 1 0 1 0 1 1 1 0 0 0 0 1 0 1 0 1 0 1 1 1 0 1 0 0 1 1 1 0 1 0 1 0 0 0 0 1 1 1 1 1 1 所以(p??r)?(q?r)?q??p为永真式；推理(p??r)?(q?r)?q??p是正
确的。
（2）等值演算： （3）主析取范式
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) ⑦置换 ⑨s?q ⑩t
⑧化简
⑥⑨假言三段论 ②⑩假言推理 前提引入
11○12假言推理 ○12○13合取 ○
?q
11q ○
12q?p ○13○
p
⑨
p?q
15、在自然推理系统P中用附加前提法证明下面推理： （1）前提：p?(q?r),s?p,q
结论：s?r 证明： ①s
附加前提引入 前提引入 ①②假言推理 前提引入 ③④假言推理 前提引入 ⑤⑥假言推理
②s?p ③
p
④p?(q?r) ⑤q?r ⑥q ⑦r
16、在自然推理系统P中用归谬法证明下面推理： （1）前提：
p?q,p?r,q?s
结论：r?s 证明： ①?(r?s) ②?r??s ③?s
结论否定引入 ①置换 ②化简
④?r ⑤
②化简 前提引入
p?r
⑥q?s ⑦?p ⑧?q
前提引入
④⑤拒取式 ③⑥拒取式 ⑦⑧合取 ⑨置换 前提引入
⑨?p??q ⑩?(p?q)
11○
p?q
11矛盾。 ⑩○
17：在自然推理系统P中构造下面推理的证明：
只要A曾到过受害者房间并且11点以前没有离开，A就是谋杀嫌疑犯。A曾到过受害者房间。如果A在11点以前离开，看门人会看见过他。看门人没有看见他。所以，A是谋杀嫌疑犯。 解答：
（1） 命题符号化：
p:A曾到过受害者房间；q:A在11点以前离开；
r: A就是谋杀嫌疑犯；s:看门人会看见过A；
（2） 推理的形式结构：
前提：(p??q)?r;p;q?s;?s 结论：r （3） 证明
①?s
前提引入
②q?s ③?q ④⑤
前提引入
①②拒取式 前提引入 ③④合取 前提引入 ⑤⑥假言推理。
p
p??q
⑥(p??q)?r ⑦r
P63:习题四
5、在一阶逻辑中讲下列命题符号化。 （3）不存在比所有火车都快的汽车。 （4）凡是汽车就比火车慢是不对的。
解答：F(x):x为火车；G(y)：y为汽车；H(x,y)：y比x快。
（3）?(?y?x(G(y)?F(x)?H(x,y))) （4）??y?x(G(y)?F(x)?H(y,x))
6、将下列命题符号化，个体域为实数集合R，并指出各命题的真值。