离散数学屈婉玲版第一章部分习题汇总.doc

《离散数学屈婉玲版第一章部分习题汇总.doc》由会员分享，可在线阅读，更多相关《离散数学屈婉玲版第一章部分习题汇总.doc（16页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第一章习题1.1&1.2 判断以下语句是否为命题,假设是命题请指出是简单命题还是复合命题.并将命题符号化,并讨论它们的真值.(1) 2是无理数.是命题,简单命题.p:2是无理数.真值:1(2) 5能被2整除. 是命题,简单命题.p:5能被2整除.真值:0(3) 现在在开会吗不是命题.(4) x+50.不是命题.(5) 这朵花真好看呀!不是命题. (6) 2是素数当且仅当三角形有3条边. 是命题,复合命题.p:2是素数.q:三角形有3条边.pq真值:1 (7) 雪是黑色的当且仅当太阳从东方升起. 是命题,复合命题.p:雪是黑色的.q:太阳从东方升起. pq真值:0 (8) 2021年10月1日天

2、气晴好. 是命题,简单命题.p:2021年10月1日天气晴好.真值唯一. (9) 太阳系以外的星球上有生物. 是命题,简单命题.p:太阳系以外的星球上有生物.真值唯一. (10) 小李在宿舍里. 是命题,简单命题.P:小李在宿舍里.真值唯一. (11) 全体起立! 不是命题. (12) 4是2的倍数或是3的倍数.q真值:1 (13) 4是偶数且是奇数.q真值:0 (14) 李明与王华是同学. 是命题,简单命题.p: 李明与王华是同学.真值唯一. (15) 蓝色和黄色可以调配成绿色. 是命题,简单命题.p: 蓝色和黄色可以调配成绿色.真值:11.3 判断以下各命题的真值.(1)假设 2+2=4,

3、那么 3+3=6.(2)假设 2+2=4,那么 3+36.(3)假设 2+24,那么 3+3=6.(4)假设 2+24,那么 3+36.(5)2+2=4当且仅当3+3=6.(6)2+2=4当且仅当3+36.(7)2+24当且仅当3+3=6.(8)2+24当且仅当3+36.答案: 设p:2+2=4,q:3+3=6,那么p,q都是真命题.(1)pq,真值为1.(2)pq,真值为0.(3)pq,真值为1.(4)pq,真值为1.(5)pq,真值为1.(6)pq,真值为0.(7)pq,真值为0.(8)pq,真值为1.14将以下命题符号化，并讨论其真值。 1如果今天是1号，那么明天是2号。 p:今天是1号

4、。 q:明天是2号。 符号化为：pq 真值为：1 2如果今天是1号，那么明天是3号。 p:今天是1号。 q:明天是3号。 符号化为：pq 真值为：0将以下命题符号化。12是偶数又是素数。2小王不但聪明而且用功。3虽然天气很冷，老王还是来了。4他一边吃饭，一边看电视。5如果天下雨，他就乘公共汽车上班。6只有天下雨，他才乘公共汽车上班。7除非天下雨，否那么他不乘公共汽车上班。(意思为：如果他乘公共汽车上班，那么天下雨或如果不是天下雨，那么他就不乘公共汽车上班)8不经一事，不长一智。答案：1设p：2是偶数，q：2是素数。符号化为：pq 2设p：小王聪明，q：小王用功。符号化为：pq 3设p：天气很冷

5、，q：老王来了。符号化为：pq 4设p：他吃饭,q：他看电视。符号化为：pq 5设p：天下雨，q：他乘公共汽车。符号化为：pq 6设p：天下雨，q：他乘公共汽上班。符号化为：qp 7设p：天下雨，q：他乘公共汽车上班。符号化为：qp或qp8设p：经一事，q：长一智。符号化为：pq设p,q的真值为0；r,s的真值为1，求以下各命题公式的真值。1p(qr)2(pr)(ps)3(p(qr)(pq)(rs)4(p(q(rp) (rs) 解：1 p(qr)pqrqrp(qr) 00100(2) (pr)(ps) pqrsprpps(pr)(ps)00110110(3)(p(qr)(pq)(rs)pqrs

6、qrp(qr)pqrs(pq)(rs)(p(qr)(pq)(rs)0011100101 (4) (p(q(rp) (rs)pqrsprpq(rp)(p(q(rp)(rs)(p(q(rp) (rs)001111111117 判断以下命题公式的类型。1p(pqr) 解：pqrpqpqrp(pqr)000001001011010111011111100111101111110111111111由真值表可知，该命题公式为重言式。2p p p ppp pp p p01111001由真值知命题公式的类型是：重言式3(qp)ppqqpqp(qp)p00100010101010011100此命题公式是矛盾式。

7、 (4)(pq) (qp) 解:其真值表为:pqpqpqqp(pq)(qp)0011111011011110010011100111由真值表观察,此命题为重言式. (5)( pq) (qp) 解:其真值表为:pqppqqp(pq)(qp)001011011111100111110100 由真值表观察,此命题为非重言式的可满足式.7pp(qq) r)解：pqrppqqr(qq) rpp(qq) r)00010100001100000101010001110000100101001011000011010101111000结论：此命题为矛盾式1.7(8) (p q)(pq).p q(pq)(pq)

8、(pq)(p q)(pq)0 010110 101011 001011 11100由此可以知道，上式为非重言式的可满足式.(9) ()()() 解:pA0001111100111111010100110111111110001001101010111101000111111111该命题为永真式10pqrs解：pqrspqpqrpqrs0000010000101100100100011011010010101011000110110011111111111111110110110110011001011001100101011010111111000101 结论：此命题为非重言式可满足式1.8

9、用等值演算法证明以下等值式1pq(pq) p证明：pq(pq) 分配律p(qq) 排中律p1 (同一律)p 3p q ( ( p q ) ( p q ) ) 证明：p q ( ( p q ) (q p ) ) ( ( p q ) ( q p ) ) ( p q ) ( q p ) ( p q ) ( q p ) ( ( p q ) q ) ( (p q ) p ) ( ( p q ) ( q q ) ) ( ( p p ) ( q p) ) ( p q ) 1) (1 ( q p) ) ( p q ) ( q p) ( p q ) ( p q ) 1.9 用等值演算法判断以下公式的类型。 1p

10、qp.解：1pqppqp 蕴含等值式pqp 德摩根律pqp 双重否认律 ppq 交换律0q 矛盾律0 零律即原式为矛盾式.(2) (pq) (qp)(pq)解：(pq) (qp)(pq)(pq) (pq)(pq) (pq) (pq) (pq)(Pq) (pq)(pq) (pq) 1即(pq) (qp)(pq)是重言式。 (3) (pq)(qp). 解：(pq)(qp) (pq) (qp) (pq) (qp) (p(pq) (q(qp) ( (pp)q) (qq)p (pq) (pq) (pq)或 (pq)(qp) (pq) (qp) (pq) (qp) (pq) qp结合律 pq 吸收律结论：

11、该公式为可满足式。1.12(1)求下面命题公式的主析取范式、主合取范式、成真赋值、成假赋值。 (p(qr)pqr(p(qr)(pqr) (p(qr) (pqr) (pq) (pr)(pqr) (pq)(rr) (pr)(qq) (pqr) (pqr)(pqr)(pqr) (pqr) (pqr) (pqr)(pqr) (pqr) (pqr) (pqr) (pqr)(pqr) (pqr)m0m1m2m7(0,1,2,7)故 其主析取范式为 (p(qr)pqr(0,1,2,7)由最小项定义可知道原命题的成真赋值为(0,0,0) (0,1,0) (0,0,1) (1,1,1)成假赋值为(0,1,1)(

12、1,0,0)(1,0,1)(1,1,0)由主析取范式和主合取范式的关系即可知道 主合取范式为 (p(qr)pqr(3,4,5,6)3pqq r解：pqq rpqqrpqqr0既pqq r是矛盾式。pqq r的主合取范式为M0 M1 M2 M3 M4 M5 M6 M7， 成假赋值为：000，001，010，011，100，101，11113.通过求主析取范式判断以下各组命题公式是否等值。 1p(qr); q(pr). 解：p(qr) p (qr) p (qr) pqr (p(qq)(rr)(pp)q(rr)(pp)(qq) r) (pqr) (pqr) (pqr) (pqr) (pqr) (pq

13、r) (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) (pq) (pq)m1m0m2(0,1,2)(pq)处原为(qp)，不是极小项 令A = pqB= (pq)C=(pq) (pq) (pq)D = pq那么B*=(pq) ? pq=D且A?B?C所以D?A*?C*C* = (pq)(pq)(pq)?0，1，2?(3)所以!?某勘探队有3名队员，有一天取得一块矿样，3人判断如下：甲说：这不是铁，也不是铜；乙说：这不是铁，是锡；

14、丙说：这不是锡，是铁；经实验室鉴定后发现，其中一人两个判断都正确，一个人判对一半，另一个人全错了。根据以上情况判断矿样的种类。解：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) (pq) (pr) 6)丙全对，乙对一半，甲全错：(rp) (pr)(pr) (pq) 那么1(pqpr

15、rp) (pqprrp) 000(pqrppr)(pqrppr) 000(prpqrp) prqprp (pqr) 0pqrprrppqprrppq 000(rppqpr) (rppqpr)0(pqr) pqr(rpprpq) (rp prpq)000所以pqrpqr而这块矿石不可能既是铜又是锡，所以只能是判断以下推理是否正确，先将命题符号化，再写出前提和结论，让后进展判断。3 如果今天是1号，那么明天是5号。今天是1号，所以明天是5号。 p：今天是1号 q：明天是5号 解：前提：pq ,p 结论：q 推理的形式构造为：(pq)p)q 证明：pq 前提引入 p 前提引入 q 假言推理此命题是正

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) qp qp此式子为非重言式的可满足式，故不可以判断其正确性所以此推理不正确3如果今天是1号，那么明天是5号，明天不是5号，所以今天不是1号。解：p:今天1号.q:明天是5号.(pq)q)p前提:pq,q.结论: p.证明:pq 前提引入q 前提引入p 拒取式推理正

17、确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,st,tr. 结论：pqsr.证明：1) tr；前提引入2) t ；1)的化简3) st；前

18、提引入4)st(ts); 3)的置换5) ts 4)的化简6) s； 2),5)的假言推理7) qs；前提引入8) (qs)(sq)；7)置换9) sq 8)的化简10) q；6),9)的假言推理11) qp；前提引入12) p；10),11)的假言推理13r 1)的化简14) pqsr 6),10),12),13)的合取所以推理正确。118 如果他是理科学生，他必学好数学。如果他不是文科学生，他必是理科学生。他没学好数学。所以它是文科学生。判断上面推理是否正确，并证明你的结论。解：p:他是理科学生 q:他学好数学 r:他是文科学生 前提：pq ，rp ，q结论：r p 前提引入 pq 前提引

19、入 p 拒取式 rp 前提引入 r 拒取式1.19 给定命题公式如下：p(qr)。 求命题公式的主析取范式、主合取范式、成真赋值、成假赋值。解： p(qr) ( p(qq)(rr)(qr)(pp) (pqr)(pqr)(pqr)(pqr)(pqr)(pqr) m7m6m5vm4m6m2 m7m6m5vm4m2 (2、4、5、6、7) p(qr) (0、1、3) 既010、100、101、110、111是成真赋值， 000、001、011是成假赋值1.20 给定命题公式如下：pqr。 求命题公式的主析取范式、主合取范式、成真赋值、成假赋值。解： pqr (pq)r(pq)(rr)(pp)(qq)

20、r)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)m7m6m7m5m3m1 m7m6 m5m3m1(1、3、5、6、7)pqr (0、2、4)既001、011、101、110、111是成真赋值， 000、010、100是成假赋值。例题例1.25 给定命题公式如下，用等值演算判断公式类型(1)(pq) (pq) 解： (pq) (pq) pq pq (pp) (qq) 11 1 所以为重言式2(pq) (pq)(qp) 解：(pq) (pq)(qp) (pq) (q) (pq)(pq)(pq)(pq) (pq)(pq) (pq) (pq) (pq) (qp) (pq) (qp) (

21、pq) (qp) (pq) (pq) (qp) (qp) (1 (qp)(1(qp) 1 1 1 所以此式是重言式(红色字体局部可删去)3 (pq)q解： (pq)q(pq)q (pq)qp(qq) p00由上使等值演算结果可知：此式为矛盾式。(4) (pp)q0q(0q)(q0)(0q)(q0)1qq由此结果可得此式为：非重言式的可满足式 5p(pq);解：p(pq)p( pq)p pq 1q1所以该命题公式是重言式。6pp(qq)r)10r10100所以为矛盾式 (7)(pq)p)?p解: (pq)p) ?p ?(pqp) ?p ?(pq) p) ?p?(pq) p?p?p?p?(pp)(pp) 等价等值式?pp 等幂律?pp 蕴涵等值式?1所以该式为重言式例1.25 第8题 pq(pq)(pq)p)(pqq) (pp)(qp)(pq)(qq)p(pq)(pq)p(pq)p或pq(pq)p(qq) p1p为可满足式 (9) (pqr) ?(pqr)?(pq) r) ?(pqr)?(pq)r) ?(pqr) ?(pqr) ?(pqr)?(pqr)(pqr)(pqr)(pqr)?(pqr)(pqr)?(pqr)(pqr)?1 所以该式为重言式10pqr解： 是非重言式的可满足式，因为000是其成假赋值，111是其成真赋值。