离散数学第三章习题详细答案.doc
3、9解:符号化:p:a就是奇数、q:a就是偶数、 r:a能被2整除前提:(p¬r),(qr)结论:(q¬p)证明:方法1(真值法)pqrp¬rqr(p¬r)(qr)q¬p00011110011111011100110011111010101011111111010001110100由上表可知,没有出现合取式(p¬r)(qr)为真,结论(q¬p)为假得情况,因此推论正确。方法2(等值演算法)(p¬r)(qr) (q¬p)(¬p¬r)(¬qr) (¬q¬p)(pr) (q¬r) ¬q¬p(pr) ¬p)(q¬r) ¬q)(r¬p) (¬r¬q)¬p(r¬r) ¬q1即证得该式为重言式,则原结论正确。方法3(主析取范式法)(p¬r)(qr) (q¬p)(¬p¬r)(¬qr) (¬q¬p)(pr) (q¬r) ¬q¬pm0+ m1+ m2+ m3+ m4+ m5+ m6+ m7可知该式为重言式,则结论推理正确。3、10、 解:符号化:p:a就是负数、q:b就是负数、 r:a、b之积为负前提: r(p¬q) (¬pq)结论:¬r(¬p¬q)方法1(真值法)证明:pqr(p¬q) (¬pq)(¬p¬q)r(p¬q) (¬pq)¬r(¬p¬q)00001110010101010101010010101100010101101101110111110001由上表可知,存在r(p¬q) (¬pq)为真,结论¬r(¬p¬q)为假得情况,因此推理不正确。方法2(主析取范式法)证明:(r(p¬q) (¬pq) (¬r(¬p¬q)¬ (¬r(p¬q) (¬pq) (r(¬p¬q)r(¬p¬q)m0+m2+m4+m6+m7只含5个极小项,课件原始不就是重言式,因此推理不正确3、11、填充下面推理证明中没有写出得推理规则。解:析取三段论:析取三段论:假言推理3、12、 填充下面推理证明中没有写出得推理规则。解:化简规则:化简规则:假言推理:假言推理:假言推理:假言推理3、13、证明:前提¬(pq)q ¬(¬ pq)q p¬qq 0为矛盾式以(¬(pq)q)(pq)(rs) B、(B为任何结论)得推理得前件在任何赋值下均为假无论结论如何,推理总正确3、14、在自然推理系统 P 中构造下面推理得证明: (1)前提: p (q r), p, q结论: r s(2)前提: p q, ¬ (q r), r结论: ¬ p(3)前提: p q结论: p (p q) (4)前提: q p, qs, st, t r结论: p q(5)前提: p r, q s, p q结论: r s(6)前提: ¬ p r, ¬ q s, p q结论: t (r s)(1)证明: p (qr)前提引入p 前提引入qr 假言推理q 前提引入r 假言推理rs 附加律(2)证明: ¬ (q r)前提引入¬ q ¬ r 置换r 前提引入¬ q 析取三段论p q 前提引入¬ p 拒取式(3)证明: pq 前提引入¬ pq 置换 (¬ pq)(¬pp)置换¬ p(pq) 置换p(pq) 置换(4)证明: st 前提引入 (st)(ts)置换 t s 化简 t r 前提引入 t 化简 s 假言推理 qs 前提引入 (sq)(qs)置换 sq化简 q 假言推理11 qp 前提引入12 p 11 假言推理13 p q 12 合取(5)证明: p r前提引入q s前提引入p q前提引入p 化简q 化简r 假言推理s 假言推理r s 合取 (6)证明: t 附加前提引入¬ p r 前提引入 p q 前提引入p 化简 r 析取三段论r s 附加3、15、在自然推理系统 P 中用附加前提法证明下面各推理: (1)前提: p (q r), s p, q结论: s r(2)前提: (p q) (r s), (s t) u结论: p u (1)证明: s 附加前提引入s p 前提引入p 假言推理p(qr)前提引入q r 假言推理q 前提引入r 假言推理(2)证明: P 附加前提引入pq 附加(pq)(rs)前提引入r s 假言推理s 化简s t 附加(s t) u 前提引入u 假言推理3、16、在自然推理系统 P 中用归谬法证明下面推理: (1)前提: p ¬ q, ¬ r q, r ¬ s结论: ¬ p(2)前提: p q, p r, q s结论: r s (1)证明: P 结论否定引入p ¬ q 前提引入¬ q 假言推理 ¬ rq 前提引入¬ r 析取三段论 r¬ s 前提引入r 化简 ¬ rr 合取为矛盾式, 由归谬法可知, 推理正确、 (2)证明: ¬ (rs) 结论否定引入pq 前提引入pr 前提引入qs 前提引入rs 构造性二难¬ (rs)(rs)合取3、17、 在自然推理系统 P 中构造下面推理得证明: 只要 A 曾到过受害者房间并且 11 点以前没用离开, A 就犯了谋杀罪、 A 曾到过受害者房间、 如果 A 在11 点以前离开, 瞧门人会瞧到她、 瞧门人没有瞧到她、 所以 A 犯了谋杀罪、 解:令 p: A 曾到过受害者房间; q: A 在 11 点以前离开了; r: A 就犯了谋杀罪; s:瞧门人瞧到 A、 前提: (p¬q)r, p, qs, ¬ s、 结论: r、 证明: ¬ s 前提引入 qs 前提引入 ¬ q拒取 p 前提引入 p¬q合取 (p¬q)r前提引入 r 假言推理3、18、在自然推理系统 P 中构造下面推理得证明、 (1)如果今天就是星期六, 我们就要到颐与园或圆明园去玩、 如果颐与园游人太多, 我们就不去颐与园玩、 今天就是星期六、 颐与园游人太多、 所以我们去圆明园玩、 (2)如果小王就是理科学生, 她得数学成绩一定很好、 如果小王不就是文科生, 她必就是理科生、 小王得数学成绩不好、 所以小王就是文科学生、解:(1)令 p: 今天就是星期六; q: 我们要到颐与园玩; r: 我们要到圆明园玩; s:颐与园游人太多、 前提: p (qr), s¬ q, p, s、 结论: r、证明: p 前提引入 p (qr)前提引入 qr 假言推理 s 前提引入 s¬ q前提引入 ¬ q 假言推理 r 析取三段论(2) 令 p: 小王就是理科生, q: 小王就是文科生, r: 小王得数学成绩很好、 前提: p r, ¬ q p, ¬ r结论: q证明:p r 前提引入¬ r 前提引入¬ p 拒取式¬ q p前提引入q 拒取式
