离散数学(屈婉玲版)第一章~习题.doc
|第一章习题 1.1 q(pr).解：p(qr) p (qr) p (qr) pqr (p(qq)(rr)(pp)q(rr)(pp)(q q) r) (pqr) (pqr) (pqr) (pqr) (p qr) (pqr) (pq r)(0,1,2,3,4,5,7)|q(pr) q (pr) pqr (0,1,2,3,4,5,7)所以两式等值。 （2） pq (pq) (p(qq)(q(pp) (pq)(pq) (qp) (pq) (pq) (p q) (pq) m 1 m 0 m 2 (0,1,2) (pq)处原为(qp)，不是极小项令A = pq B= (pq) C=(pq) (pq) (pq) D = pq 则B*=(pq) pq=D 且ABC 所以DA*C* C* = (pq)(pq)(pq) （0，1，2）(3) 所以! 1.15某勘探队有3名队员，有一天取得一块矿样，3人判断如下： 甲说：这不是铁，也不是铜； 乙说：这不是铁，是锡； 丙说：这不是锡，是铁； 经实验室鉴定后发现，其中一人两个判断都正确，一个人判对一 半，另一个人全错了。根据以上情况判断矿样的种类。 解：p：是铁 q：是铜 r：是锡由题意可得共有6种情况： 1)甲全对，乙对一半，丙全错：(pq) (pr)|(pr) (rp) 2)甲全对，丙对一半，乙全错：(pq) （rp） (rp)）(pr) 3)乙全对，甲对一半，丙全错：（pr）(pq) ( qp) (rp) 4)乙全对，丙对一半，甲全错：（pr）(rp) (rp) (pq) 5)丙全对，甲对一半，乙全错：(rp) ( (pq) (p q) (pr) 6)丙全对，乙对一半，甲全错：(rp) (pr) (pr) (pq) 则1 (pqprrp) (pqprrp) 000 (pqrppr)(pqrpp r) 00 0 (prpqrp) （prqpr p） (pqr) 0pqr （prrppq）（prrppq） 000 (rppqpr) (rppqpr)0(pqr) pqr (rpprpq) (rp prpq)000 所以（pqr）（pq r） 而这块矿石不可能既是铜又是锡，所以只能是 1.16判断下列推理是否正确，先将命题符号化，再写出前提和结论， 让后进行判断。 3 如果今天是1号，则明天是5号。今天是1号，所以明天是5|号。p：今天是1号 q：明天是5号解：前提：pq ,p结论：q推理的形式结构为：(pq)p)q证明： pq 前提引入 p 前提引入 q 假言推理此命题是正确命题 1.16（2） 判断下列推理是否正确，先将命题符号化再写出前提和结论，然 后进行判断如果今天是1号，则明天是5号。明天是5号，所以今天是1号。解 设p: 今天是1号,q: 明天是5号,则该推理可以写为 ( (pq)q)p 前提 pq，q 结论 p 判断 证明( (pq)q)p ( (pq)q)p( pq)qp ( pq) qp (pq) qpqp 此式子为非重言式的可满足式，故不可以判断其正确性 所以此推理不正确 1.16（3）如果今天是1号，则明天是5号，明天不是5号，所以今天|不是1号。 解：p:今天1号. q:明天是5号. (pq)¬q)¬p 前提:pq,¬q. 结论: ¬p. 证明:pq 前提引入 ¬q 前提引入 ¬p 拒取式 推理正确 1.17(1)前提：（pq）,qr,r 结论：p. 证明：qr 前提引入r 前提引入q 析取三段论 (pq) 前提引入pq 置换p 析取三段论 即推理正确。 （2）前提：p(qs),q, pr结论：r s.证明： pr 前提引入 r 附加前提引入 p 析取三段论 p(qs) 前提引入 qs 假言推理 q 前提引入 s 假言推理 由附加前提证明法可知，结论正确。(3): 前提: pq.结论: p(pq). 证明: pq. 前提引入|p 附加前提引入q 假言推理 pq 合取引入规则 （4）前提：qp,qs,s t,tr.结论：pqsr. 证明：1) tr；前提引入 2) t ；1)的化简 3) st；前提引入 4)（st） (ts); 3)的置换 5) ts 4)的化简 6) s； 2),5)的假言推理 7) qs；前提引入 8) (q s)(sq)；7)置换 9) sq 8)的化简 10) q；6),9)的假言推理 11) qp；前提引入 12) p；10),11)的假言推理 13）r 1)的化简 14) pqsr 6),10),12),13)的合取 所以推理正确。 118 如果他是理科学生，他必学好数学。如果他不是文科学生， 他必是理科学生。他没学好数学。所以它是文科学生。 判断上面推理是否正确，并证明你的结论。 解：p:他是理科学生 q:他学好数学 r:他是文科学生 前提：pq ，rp ，q 结论：r p 前提引入 pq 前提引入 p 拒取式 rp 前提引入 r 拒取式 1.19 给定命题公式如下：p(qr)。求命题公式的主析取范式、主合取范式、成真赋值、成假|赋值。 解： p(qr)( pqq)(rr)(qr)(pp)pqr)pqr)(pqr)(pqr)(p qr)(pqr)m 7 m 6 m 5 vm 4 m 6 m 2m 7 m 6 m 5 vm 4 m 22、4、5、6、7p(qr) 0、1、3既010、100、101、110、111是成真赋值，000、001、011是成假赋值 1.20 给定命题公式如下：（pq）r。求命题公式的主析取范式、主合取范式、成真赋值、成假 赋值。 解： （pq）r(pq)r (pq)(rr)(pp)(qq)r) (p qr)(pqr)(pqr)(pq r)(pqr)(pq r) m 7 m 6 m 7 m 5 m 3 m 1 m 7 m 6m 5 m 3 m 1 1、3、5、6、7 （pq）r 0、2、4 既001、011、101、110、111是成真赋值，000、010、100是成假赋值。 例题 例1.25 给定命题公式如下，用等值演算判断公式类型 (1)(pq) (pq)|解： (pq) (pq) pq pq (pp) (qq) 111所以为重言式 （2）(pq) (pq)(qp)解：(pq) (pq)(qp) (p q) ( q) (p q)(p q)(pq)(p q) (pq)(p q) ¬(pq) (pq)¬(pq) (qp) (pq) (qp) (¬(pq) ¬ (qp) (pq) (¬(pq) ¬ (qp) (qp) (1¬ (qp)(1(qp)1 11所以此式是重言式(红色字体部分可删去) （3） (pq)q 解： (pq)q( pq)q (pq)q p( qq) p00 由上使等值演算结果可知：此式为矛盾式。 (4) (pp) q 0 q (0q)(q0) (0q) ( q0) 1 q q 由此结果可得此式为：非重言式的可满足式（5）p(p q); 解：p(pq)|p ( pq) （ p p）q 1 q 1 所以该命题公式是重言式。 （6） （pp）(qq)r) 1（0r） 10 10 0 所以为矛盾式(7)(pq)p)p 解: (pq)p) p(（pq）p) p(pq) p) p (p q) pp p p (pp)(pp) 等价等值式 pp 等幂律 pp 蕴涵等值式 1 所以该式为重言式 例1.25 第（8）题 （pq）(pq) (pq)p)(（pq）q) (pp)(qp)(pq)(qq) p(pq)(pq) p(pq) p 或（pq）(pq) p(qq) p1|p 为可满足式(9) (pqr) (pqr) (pq) r) (pqr) (pq)r) (pqr) ( p qr) (pqr) ( pqr)(pqr)( pqr)(p qr) ( p qr)(pqr) (pqr)(pqr) 1所以该式为重言式 （10） （pq）r 解： 是非重言式的可满足式，因为000是其成假赋值，111是其 成真赋值。
