离散数学第三章习题详细答案

1、精品资料3.9. 解:符号化：p : a是奇数.q : a是偶数.r : a能被2整除前提：（p？ r）,（q-r）结论：（q 一？ p）证明：方法1 （真值法）pqrp 一？ rq - r(p 一？ r) a (q 一 r)q-? p00011110011111011100110011111010101011111111010001110100由上表可知，没有出现合取式（p-? r） a （q-r）为真，结论（q-? p）为假的情况，因此推论正确。方法2 （等值演算法）(p 一？ r) a (q 一 r) 一 (q 一？ p)?(?p v ?r) a (?q r) (?q v ?p)? (p

2、 a r) v(qa?r) v?qv?p?(p a r) v? p) v (q a? r) v? q)? (r v? p) v(?rv?q)? ?p v(r v? r) v? q?1即证得该式为重言式，则原结论正确。方法3 (主析取范式法)(p 一？ r) a (q 一 r) 一 (q 一？ p)?(?p v ?r) a (?q 明一(?q v ?p)? (p a r) v(qa?r) v?qv?p?mo+ m i+ m 2+ m 3+ m 4+ m 5+ m 6+ m 7可知该式为重言式，则结论推理正确。3.10. 解：符号化：p : a是负数.q : b是负数.r ： a、b之积为负 前提

3、：r f(p a? q) v (?p a q)结论：？ r 一 (？p a ? q)方法1 (真值法)证明：pqr(p a?q) v (?p aq)(?pa?q)r一(pa?q) v (?p a q)?r(?p a? q)00001110010101010101010010101100010101101101110111110001由上表可知，存在rf(pa?q) v(?paq)为真，结论？ r-(?p a? q)为假的情况，因此推理不 正确。方法2 (主析取范式法)证明：(r 一(pa ?q) v (?p /q) 一(?一(?p a ?0)? (?r v(p a ?q) v (?p aq)

4、v (r v (?p a ?q)? r v (?p a ?q)?m o+m 2+m 4+m 6+m 7只含5个极小项，课件原始不是重言式，因此推理不正确3.11. 填充下面推理证明中没有写出的推理规则。解：析取三段论：析取三段论：假言推理3.12. 填充下面推理证明中没有写出的推理规则。解：化简规则：化简规则：假言推理：假言推理：假言推理：假言推理3.13. 证明：前提？(p-q)aq ? ?(? p vq)aq ? pa?qaq ? 0 为矛盾式，以(？84)八4)八8/4)八(r-s) - b.(b为任何结论)的推理的前件在任何赋值下均为假.无论结论如何，推理总正确3.14. 在自然推理系

5、统p中构造下面推理的证明(1)前提：p 一(q r), p, q结论：r v s(2)前提：p 一 q, ? (q a r), r结论：？ p前提：p 一 q结论：p 一(p a q)(4)前提:q - p, q ? s, s ? t, t a r 结论:p a q(5)前提：p-r, q-s, p a q结论:r a s(6)前提:? p v r, ? q v s, p a q 结论：t f (r v s)(1)证明： p - (q-r)p q-rqr r v s(2)证明： ？(q八r)?q v ?rr？q p f q ?p前提引入前提引入假言推理 前提引入假言推理附加律前提引入置换前提引

6、入析取三段论前提引入拒取式(3)证明：pfq前提引入？ p vq置换(? p沟)a (?p v p) 置换 ？ p v (p a q) 置换 p f(p a q) 置换(4)证明：s?t前提引入 (s -t)a (t-s)置换t -s化简t ar前提引入t化简s假言推理q?s前提引入 (s-q)a(qs)置换 s-q化简q假言推理11qfp前提引入12p11假言推理13p a q。12合取证明：p frq -sp八qpqrsr as前提引入前提引入前提引入化简化简假言推理假言推理合取(6)证明：t？ p v r p a qpr r v s附加前提引入前提引入前提引入化简析取三段论附加3.15.

7、在自然推理系统 p中用附加前提法证明卜面各推理(1)前提：p f (q - r), s - p, q 结论：s - r(2)前提：(p v q) (r a s), (s v t)- 结论：p - u证明：s附加前提引入sfp前提引入p假言推理p- (q-r)前提引入qfr假言推理q前提引入r假言推理(2)证明：p附加前提引入pvq附加 (p vq) f(r a s)前提引入3)r a s假言推理s化简s v t附加(s v t)- u前提引入u假言推理3.16. 在自然推理系统p 中用归谬法证明下面推理(1)前提：p ? q, ? r v q, r a? s 结论 : ? p(2)前提：p v

8、q, pfr, q - s 结论:r v s (1)证明 : p结论否定引入p f ? q 前提引入 ? q假言推理? r q前提引入 ? r 析取三段论ra ? s前提引入 r 化简？r a合取(2)证明 : ? (r p v q p fr qfs r v s ? (r为矛盾式, 由归谬法可知 , 推理正确 .s) 结论否定引入前提引入前提引入前提引入构造性二难a (r v s)合取3.17. 在自然推理系统p 中构造下面推理的证明 :只要 a 曾到过受害者房间并且 11 点以前没用离开, a 就犯了谋杀罪. a 曾到过受害者房间 . 如果 a 在 11 点以前离开, 看门人会看到他. 看门

9、人没有看到他. 所以 a 犯了谋杀罪解：令 p: a 曾到过受害者房间 ; q: a 在 11 点以前离开了 ; r: a 就犯了谋杀罪; s: 看门人看到a.前提：(p a ? q) - r, p, q - s, ? s.结论 : r.证明 : ? s前提引入qfs前提引入 ? q拒取 p前提引入 pa? q 合取(p a ?q)f r前提引入 r假言推理3.18. 在自然推理系统p 中构造下面推理的证明 .(1) 如果今天是星期六 , 我们就要到颐和园或圆明园去玩. 如果颐和园游人太多 , 我们就不去颐和园玩. 今天是星期六. 颐和园游人太多 . 所以我们去圆明园玩.(2) 如果小王是理科学生, 他的数学成绩一定很好. 如果小王不是文科生, 他必是理科生. 小王的数学成绩不好. 所以小王是文科学生.解：(1) 令 p: 今天是星期六; q: 我们要到颐和园玩; r: 我们要到圆明园玩; s: 颐和园游人太多 .前提：p - (q v r), s f ? q, p, s.结论 : r.证明： p前提引入 pf (qvr)前提引入 qvr 假