离散数学习题三 含答案

11、填充下面推理证明中没有写出的推理规则。 前提：pq,qr,rs,p 结论：s

证明：① p 前提引入 ②pq 前提引入

③ q （①②析取三段论） ④qr 前提引入

⑤ r （③④析取三段论） ⑥rs 前提引入

⑦ s （⑤⑥假言推理）

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 （⑥⑧假言推理） 13、前提：(pq)q,pq,rs

结论1：r 结论2：s 结论3：rs

（1）证明从此前提出发，推出结论1，结论2，结论3的推理都是正确的。 （2）证明从此前提出发，推任何结论的推理都是正确的。 证明：（1）①(((pq)q)(pq)(rs))r

((pq)q)(pq)(rs))r1

②(((pq)q)(pq)(rs))s

((pq)q)(pq)(rs))s1

③(((pq)q)(pq)(rs))(rs)

((pq)q)(pq)(rs))rs1

即结论1，结论2，结论3的推理都是正确的。

（2）((pq)q)(pq)(rs)

((pq)q)(pq)(rs)(pqq)(pq)(rs) 0(pq)(rs)0

即推任何结论的推理都是正确的。

14、在自然推理系统P中构造下面推理的证明： （1）前提：p(qr)，p,q 结论：rs

证明：①p(qr) 前提引入 ② p 前提引入 ③ (qr) ① ②假言推理

④ q 前提引入 ⑤ r ③ ④假言推理 ⑥ rs ⑤ 附加律

15、在自然推理系统P中用附加前提法证明下面的推理： 前提：p(qr)，sp,q

结论：sr 证明：

① s 附加前提引入 ② sp 前提引入 ③ p ① ②假言推理 ④ p(qr) 前提引入 ⑤ qr ③ ④假言推理 ⑥ q 前提引入

⑦ r ⑤ ⑥假言推理 即根据附加前提证明法，推理正确。

16、在自然推理系统P中用归谬法证明下面的推理： 前提：pq，qr,qs 结论：rs 证明：

① (rs) 结论否定引入 ② pq 前提引入 ③ qr 前提引入 ④ qs 前提引入

⑤ rs ② ③ ④构造性二难 ⑥ (rs)(rs) ① ⑤ 合取

因为⑥为矛盾式即推理正确

17、在自然推理系统P中构造下面推理的证明：

只要A曾到过受害者房间并且11点以前没离开，A就是谋杀嫌犯。A曾到过受害者房间，如果A在11点以前离开，看门人会看见他。看门人没有看见他。所以，A是谋杀嫌犯。

答：令p: A到过受害者房间 q: A在11点以前离开 r: A是谋杀嫌犯 s: 看门人看见过A 前提：(pq)r,p,qs,s 结论：r

证明：① qs 前提引入 ② s 前提引入 ③ q ① ②拒取式 ④ p 前提引入 ⑤ pq ③ ④合取 ⑥ (pq)r 前提引入 ⑦ r ⑤ ⑥假言推理

1114490009 张梦婷